-
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;
}
-
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).
-
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.
-
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!
-
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;
}
-
-
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
-
Sorry I wasn't trying to bump it.. I forgot to put a Question Mark.
Thanks for the help man!
-
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.
