[SOLVED] What is this sorting algorithm? (or a new one?)

boraalper4 · 2013-08-11 14:09:53

Hello everyone!

Just before starting, i apologize for my grammar mistakes.

I found a new sorting algorithm but i'm not sure if i really found it. There are too many sorting algorithms and mine is a really simple one; so, i belive that it can be found years ago.
I searched popular sorting algorithms, but none of the them is the answer.

Here is algorithm:

* Search the numbers between brackets
  [24 12 12 55 64 18 32 31]

* Find smallest one
  [24 12 12 55 64 18 32 31]
         ^S

* Swap the first item between brackets with smallest one
  [12 12 24 55 64 18 32 31]

* Find largest one 
  [12 12 24 55 64 18 32 31]
               ^L

* Swap the last item between brackets with largest one
  [12 12 24 55 31 18 32 64]

* Move brackets by one.
  12[12 24 55 31 18 32]64

* Continue from step one until the array is sorted

/* rottsort
   Copyright (c) 2013  Bora M. Alper
*/

#include <stdio.h>

void print_array (const int *array, const int length);
int rottsort_swap (int *x, int *y);
void rottsort (int *array, const int length);
int rottsort_largest (const int *array, const int start, const int end);
int rottsort_smallest (const int *array, const int start, const int end);

void print_array (const int *array, const int length) {
	int i;
	
	for (i=0; i < length; ++i)
		printf ("%d ", array[i]);
	
	putchar ('\n');
}

int main (void) {
	int array[] = {24, 12, 12, 55, 64, 18, 32, 31};
	
	print_array(array, 8);
	rottsort(array, 8);
	print_array(array, 8);
	
	return 0;
}

int rottsort_swap (int *x, int *y) {
	const int temp = *x;
	
	*x = *y;
	*y = temp;
}

void rottsort (int *array, const int length) {
	int i, largest_pos, smallest_pos;
	
	for (i=0; i < length/2; ++i) {
		largest_pos = rottsort_largest(array, i, length-1-i);
		rottsort_swap(&(array[largest_pos]), &(array[length-1-i]));
		
		smallest_pos = rottsort_smallest(array, i, length-1-i);
		rottsort_swap(&(array[smallest_pos]), &(array[i]));
	}
	
}

int rottsort_largest (const int *array, const int start, const int end) {
	int i, largest_pos = start;
	
	for (i=start; i <= end; ++i)
		if (array[i] >= array[largest_pos])
			largest_pos = i;
	
	return largest_pos;
}

int rottsort_smallest (const int *array, const int start, const int end) {
	int i, smallest_pos = start;
	
	for (i=start; i <= end; ++i)
		if (array[i] <= array[smallest_pos])
			smallest_pos = i;
			
	return smallest_pos;
}

P.S.: If this is a new sorting algorithm, i name it as "rottsort". :)

Last edited by boraalper4 (2013-08-11 19:08:17)

Trilby · 2013-08-11 14:29:02

Because you already have two variables for largets and smallest, there is no reason to loop through the whole list twice to get each. Loop through the list (or list subset) once, and in each loop check if the current item is smaller than smallest_pos or larger than largest_pos.

This will increase efficiency by a factor of two.

As written I believe it'd be less efficient than even a simple bubble sort. With the above revision it may be comparable to a bubble sort.

boraalper4 · 2013-08-11 14:55:38

Trilby wrote:

Because you already have two variables for largets and smallest, there is no reason to loop through the whole list twice to get each. Loop through the list (or list subset) once, and in each loop check if the current item is smaller than smallest_pos or larger than largest_pos.
This will increase efficiency by a factor of two.
As written I believe it'd be less efficient than even a simple bubble sort. With the above revision it may be comparable to a bubble sort.

Thanks for quick answer and advice. :) I will try to do that. When i'm done, i will post the new code.
————
Code is tested on codepad. (I edited the code on my phone so, sorry for formatting)

/* rottsort
   Copyright (c) 2013  Bora M. Alper
*/

#include <stdio.h>

void print_array (const int *array, const int length);
int rottsort_swap (int *x, int *y);
void rottsort (int *array, const int length);
void rottsort_find (int *smallest_pos, int *largest_pos, const int *array, const int start, const int end);

void print_array (const int *array, const int length) {
	int i;
	
	for (i=0; i < length; ++i)
		printf ("%d ", array[i]);
	
	putchar ('\n');
}

int main (void) {
	int array[] = {24, 12, 12, 55, 64, 18, 32, 31};
	
	print_array(array, 8);
	rottsort(array, 8);
	print_array(array, 8);
	
	return 0;
}

int rottsort_swap (int *x, int *y) {
	const int temp = *x;
	
	*x = *y;
	*y = temp;
}

void rottsort (int *array, const int length) {
	int i, largest_pos, smallest_pos;
	
	for (i=0; i < length/2; ++i) {
		rottsort_find (&smallest_pos, &largest_pos, array, i, length-1-i);

		rottsort_swap(&(array[largest_pos]), &(array[length-1-i]));

		if (smallest_pos == length-1-i)
			smallest_pos = largest_pos;

		rottsort_swap(&(array[smallest_pos]), &(array[i]));
	}
	
}

void rottsort_find (int *smallest_pos, int *largest_pos, const int *array, const int start, const int end) {
	int i;
	
	*smallest_pos = start;
	*largest_pos = start;

	for (i=start; i <= end; ++i) {
		if (array[i] >= array[*largest_pos])
			*largest_pos = i;
		
		if (array[i] <= array[*smallest_pos])
			*smallest_pos = i;
	}
}

Last edited by boraalper4 (2013-08-11 15:21:48)

aspidites · 2013-08-11 18:32:37

Seems like selection sort, except that you are swapping at both ends instead of just the bottom.

boraalper4 · 2013-08-11 19:07:35

aspidites wrote:

Seems like selection sort, except that you are swapping at both ends instead of just the bottom.

Exactly. Now, i'm reading about selection sort on Wikipedia and i found it: Cocktail Sort.

The algorithm differs from a bubble sort in that it sorts in both directions on each pass through the list.

Thank you all for your helps :)

Arch Linux

#1 2013-08-11 14:09:53

[SOLVED] What is this sorting algorithm? (or a new one?)

#2 2013-08-11 14:29:02

Re: [SOLVED] What is this sorting algorithm? (or a new one?)

#3 2013-08-11 14:55:38

Re: [SOLVED] What is this sorting algorithm? (or a new one?)

#4 2013-08-11 18:32:37

Re: [SOLVED] What is this sorting algorithm? (or a new one?)

#5 2013-08-11 19:07:35

Re: [SOLVED] What is this sorting algorithm? (or a new one?)

Board footer