Thread: Sorting Algorithm Help

  1. #1
    Registered User
    Join Date
    Apr 2007
    Posts
    46

    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. #2
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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 might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Registered User
    Join Date
    Apr 2007
    Posts
    46
    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. #5
    Registered User
    Join Date
    Apr 2007
    Posts
    46
    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. #6
    Registered User
    Join Date
    Apr 2007
    Posts
    46

    Question

    hmmm

  7. #7
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by cjwenigma View Post
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  8. #8
    Registered User
    Join Date
    Apr 2007
    Posts
    46
    Sorry I wasn't trying to bump it.. I forgot to put a Question Mark.


    Thanks for the help man!

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. *Help*in sorting and searching algorithm
    By yuentong in forum C++ Programming
    Replies: 1
    Last Post: 03-07-2009, 10:43 AM
  2. Efficient Sorting Algorithm
    By GCNDoug in forum C++ Programming
    Replies: 10
    Last Post: 11-13-2008, 09:06 AM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. which sorting algorithm for GBs of data?
    By Sargnagel in forum C Programming
    Replies: 4
    Last Post: 06-05-2003, 08:43 AM