1. ## 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;
}```

2. 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).

3. 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.

4. 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!

5. 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;
}```

6. hmmm

7. 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

8. Sorry I wasn't trying to bump it.. I forgot to put a Question Mark.

Thanks for the help man!

9. 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.