Losing number in quick sort

This is a discussion on Losing number in quick sort within the C Programming forums, part of the General Programming Boards category; I'm tinkering with a serial quick sort algorithm. Normally I use qsort() but I wanted to test this. Somehow I ...

  1. #1
    Registered User
    Join Date
    Mar 2012
    Posts
    110

    Losing number in quick sort

    I'm tinkering with a serial quick sort algorithm. Normally I use qsort() but I wanted to test this.

    Somehow I loose the highest number. I can't see where I drop it. If someone here could point it out...
    Code:
    // Help function to quicksort, leave them in front of qsort.
    void swap(float_t *left, float_t *right){
       float_t temp;
       temp = *left;
       *left = *right;
       *right = temp;
    }
    
    // Help function to quicksort, this works like a charm on random dist numbers.
    int pivot(int i, int j){
       return ((i+j)/2); 
    }
    
    // Quick sort..
    void quick_sort(float_t * array, int low, int high){
       int start, end, piv;
       float_t k;
    
    
      if (low < high){
         piv = pivot(low,high);
         swap(&array[low],&array[piv]);
         k = array[low];
         start = (low+1);
         end = high;
    
         while (start <= end)
         {
            while ((start <= high) && (array[start] <= k)){ start++; }
            while ((end >= low) && (array[end] > k)){ end--; }
            if (start < end){ swap(&array[start],&array[end]);}
         }
         swap(&array[low],&array[end]);
         quick_sort(array,low,(end-1));
         quick_sort(array,(end+1),high);
      }
    }

  2. #2
    Registered User
    Join Date
    May 2012
    Posts
    333
    I've tested it and I can't see anything wrong with it either.

    I suspect the bug is in your test code. It's very easy to mix up high, the maximum index, with N, the count, or high + 1.
    I'm the author of MiniBasic: How to write a script interpreter and Basic Algorithms
    Visit my website for lots of associated C programming resources.
    http://www.malcolmmclean.site11.com/www

  3. #3
    Registered User
    Join Date
    Mar 2012
    Posts
    110
    I think I know what I did. I allocated a N size array. When I call the function I did it like this q_sort(array, 0 , N); I guess it should be N-1.

    Thanks Malcolm for the input, it made me think twice about mixing up indexes.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Quick Sort
    By ramayana in forum C Programming
    Replies: 9
    Last Post: 06-17-2007, 05:54 PM
  2. Quick Sort or Merge Sort???
    By swanley007 in forum C++ Programming
    Replies: 6
    Last Post: 11-10-2005, 05:48 PM
  3. Quick sort VS Merge Sort
    By sachitha in forum Tech Board
    Replies: 7
    Last Post: 09-03-2004, 11:57 PM
  4. Quick Sort Help
    By NavyBlue in forum C Programming
    Replies: 1
    Last Post: 03-02-2003, 09:34 PM
  5. Shell Sort vs Heap Sort vs Quick Sort
    By mackol in forum C Programming
    Replies: 6
    Last Post: 11-22-2002, 07:05 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21