# Sorting Algorithm Help

• 10-30-2007
cjwenigma
Sorting Algorithm Help
I'm writing my own sorting algorithm and needed some help. I want to write it in C++ but I'm not to sure how. Here is and example how I want it to work.

Step 1: 56712983 -> comparisons are made between first element and last then 2nd element to 2nd to last and so on.

Step 2: 36712985 -> now the elements are divided by two and both sides are compared like the step 1
3671 | 2985

Step 3: 1673 | 2895 -> now i want to divide both sides by two again and sort
16 | 73 | 28 | 95

Step 4: 16372859 -> now the elements are back together and I want to do the first step again.

Step 5: 15327869 -> now I finish off the sorting process with a bubble sort.

*note: If the array is an odd amount of elements I want the middle element to drop down. Also in step 3 I want to divide down to 2 or 3 elements depending on if its odd or even.

I know this sorting algorithm isn't really that great but I wanted to try and write my own so if I could get any ideas that'd be cool.. if not thats cool to!..haha

below is my bubble sort that I wrote in C++ which is my last step ..but i'm still not sure how to write the code to compare the first and last element as I showed in my steps then divide.

Code:

``` const int size = 1000; // this  is the array size int sortarray[size]; // this is the array which I'll use later int key = 0, j = 0; int main(){ srand(time(0)); // this part starts the random number generator for(int i = 0; i < size; i++){  // starts the for loop         sortarray[i] = (rand()%1000) + 1; // makes numbers between 1 through 20 %/returns remainder         cout<<sortarray[i]<<", "; } for(int i = 0; i < size; i++){ // starts the bubble sort         for(int j = size - 1; j > i; j--){ // starts the comparisons at the end of the array                 if(sortarray [j] < sortarray[j - 1]){ // checks the current element with the previous one                         key = sortarray[j]; // switches the elements if the conditions are met                         sortarray[j] = sortarray[j - 1];                         sortarray[j - 1] = key;                 }         } } // formats the output prints to screen cout<<endl<<endl; for(int i = 0; i < size; i++){  // prints the sorted array         cout<<sortarray[i]<<", "; } return 0; }```
• 10-30-2007
anon
The first step should be quite easy:
Code:

`for (int i = 0, j = size - 1; i != j; ++i, --j)`
To do the same thing on both halves make the whole function recursive. After you are done with step 1, make two recursive calls (for example by passing a range as start and end pointer):
Code:

```my_sort(array, array+middle); my_sort(array+middle, array+end);```
So altogether the whole thing might look like this:
Code:

```void special_sort(int* start, int* end); void presort(int* start, int* end); void bubble_sort(int* start, int* end); void presort(int* start, int* end) {     // do first step and call recursively:     presort(start, middle);     presort(middle, end); } void special_sort(int* start, int* end) {     presort(start, end);     bubble_sort(start, end); }```
However, I doubt this algorithm is very practical. If you want to explore more practical sorting algorithms look into selection sort or insertion sort (one of the fastest O(n*n) sorts and very useful to keep incoming data sorted).
• 10-30-2007
iMalc
I have implemented that algorithm, but instead of 'Bubble Sort' to finish it off it repeats the same thing again.
I called it 'Optimistic Sort' and it is O(n*logn*logn). You can find it from the link in my sig.
• 10-30-2007
cjwenigma
Wow thanks for your help guys..thats awesome. Now I just have to figure out how to exactly finish it off with the bubble sort without my code being to messy!
• 11-01-2007
cjwenigma
Ok so here's the code to my sorting algorithm..i still have problems. I can divide it once and sort them..but i also want to divide the lower and upper bounds down to two or three (if odd) numbers like I show above and I can't figure it out. My bubble sort isn't work also which at the end of the code. I think that the array is still split and the bubble isn't taking it. I show what each sort is doing so you can see... Can anyone help me?

Code:

``` #include<iostream> using namespace std; const int SIZE = 10; int split(int *array, int lower, int upper) {   int middle;   int temp;   int bound = (upper - lower) + 1;   cout << "lower bound --> " << lower << endl;   cout << "upper bound --> " << upper << endl;   if(bound >= 2 && bound < 4) {     middle = (upper + lower) / 2;     return split(array,lower,middle);     return split(array,middle+1,upper);   }   else {     for(int i=lower, j=upper; i<=j; i++, j--) {       if(array[i] > array[j]) {         temp = array[i];         array[i] = array[j];         array[j] = temp;       }     }   }   return 0; } int main() {   int sortarray[SIZE]; // array of elements to sort   int temp;            // temp placeholder   int middle;   srand(1000); // seed the random number generator   /* populate the array */   for (int i=0; i<SIZE; i++) {     sortarray[i] = (rand()%10) + 1;   }   /* output the populated array */   for (int i=0; i<SIZE; i++) {     cout << sortarray[i] << endl;   }   cout << endl;   /* initial sort */   for(int i=0, j=SIZE-1; i <= j; i++, j--) {     cout << sortarray[i] << "\t" << sortarray[j] << endl;     if (sortarray[i] > sortarray[j]) {       temp = sortarray[i];       sortarray[i] = sortarray[j];       sortarray[j] = temp;     }   }   /* output the populated array */   cout << endl;     for (int i=0; i<SIZE; i++) {     cout << sortarray[i] << endl;   }   /* split */   middle = (SIZE - 1) / 2;   cout << "The mid-point is " << middle << endl;   split(sortarray,0,middle);   split(sortarray,middle+1,SIZE-1);   /* output the populated array */   cout << endl;     for (int i=0; i<SIZE; i++) {     cout << sortarray[i] << endl;   }   cout<<endl; for(int i=0, j=SIZE-1; i <= j; i++, j--) {     cout << sortarray[i] << "\t" << sortarray[j] << endl;     if (sortarray[i] > sortarray[j]) {       temp = sortarray[i];       sortarray[i] = sortarray[j];       sortarray[j] = temp;     } } /* output the populated array */   cout << endl;     for (int i=0; i<SIZE; i++) {     cout << sortarray[i] << endl;   }   for(int i = 0; i < SIZE; i++){ // starts the bubble sort     for(int j = SIZE - 1; j > i; j--){ // starts the comparisons at the end of the array       if(sortarray [j] < sortarray[j - 1]){ // checks the current element with the previous one         key = sortarray[j]; // switches the elements if the conditions are met         sortarray[j] = sortarray[j - 1];         sortarray[j - 1] = key;       }     }   } /* output the populated array */   cout << endl;   for (int i=0; i<SIZE; i++) {     cout << sortarray[i] << endl;   }   return 0; }```
• 11-02-2007
cjwenigma
hmmm
• 11-02-2007
matsp
Quote:

Originally Posted by cjwenigma
hmmm

Bumping your thread is not considered "nice", but if you are fishing for comments, I'll give you some:
Code:

`  srand(1000); // seed the random number generator`
What's the purpose of this? Since the seed is a constant, it's really no better than the default seed you get from the C library itself.

Code:

```  if(bound >= 2 && bound < 4) {     middle = (upper + lower) / 2;     return split(array,lower,middle);     return split(array,middle+1,upper);   }```
Your compiler should say "unreachable code" on the second line there.
--
Mats
• 11-02-2007
cjwenigma
Sorry I wasn't trying to bump it.. I forgot to put a Question Mark.

Thanks for the help man!
• 11-02-2007
iMalc
Don't put any of the code for the sorting into main itself. All main should do is call a function once, and then the array should be sorted.

In split, you're trying to to the recursive calls before the end-to-end swapping is done. They should come after, unless you now want to compare the halves in a diferent manner.