Thread: QuickSort Problem

  1. #1
    Registered User
    Join Date
    Feb 2013
    Posts
    33

    QuickSort Problem

    I'm currently doing a quick sort on a multidimensional array with a bunch of words in it. When it prints out, it's just completely out of order and I thought I was sure that what I did was correct. Do you see any errors that I could've made??

    Code:
    void quickSort(char newList[][20], int low, int high){ //passed it correctly
    
        //these are indexes only
        int i = low;
        int j = high;
        int mid = ((low+high)/2);
        char pivot[20];
        strcpy(pivot, newList[mid]);
        char temp[20];
    
        //partition
        while(i<=j){ // while (i<=j)
            while(strcmp(newList[i], pivot) == -1){ //while (i<pivot)
                i++;
            }
            while(strcmp(newList[j], pivot) == 1){ //while (j>pivot)
                j--;
            }
            //SWAP
            if(i<=j){
                strcpy(temp, newList[i]);
                strcpy(newList[i], newList[j]);
                strcpy(newList[j], temp);
                i++;
                j--;
            }
        }
    
        //recursion
        if(strcmp(newList[low],newList[j]) == -1){
            quickSort(newList, low, j);
        }
        if(strcmp(newList[i],newList[high]) == -1){
            quickSort(newList, i, high);
        }
    }

  2. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    Enough code to help us test would be nice. A main function that reads words from a file, and a small example file that demonstrates the problem would be great.

    EDIT: You don't need to do exactly that, but you must have some way to test this if you know it's broken. Give us what you have that will allow us to test.
    Last edited by anduril462; 02-13-2013 at 06:01 PM.

  3. #3
    Registered User
    Join Date
    Feb 2013
    Posts
    33
    Oops you're right. Give me a minute and I'll post it.

  4. #4
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    Also, this function is recursive, so where's your base case? What stops it from recursing forever, or until high or low has a bogus value?

  5. #5
    Registered User
    Join Date
    Feb 2013
    Posts
    33
    Here's a mini version of my main function...


    Code:
    #include <stdio.h>
    #include <string.h>
    
    int main(int argc, const char *argv[]){
    
        char newList[20][20];
        strcpy(newList[0], "hello");
        strcpy(newList[1], "adam");
        strcpy(newList[2], "banana");
        strcpy(newList[3], "dog");
        strcpy(newList[4], "cheese");
        strcpy(newList[5], "worm");
        strcpy(newList[6], "ruler");
        strcpy(newList[7], "water");
        strcpy(newList[8], "oval");
        strcpy(newList[9], "stinky");
    
    
    
    
        printf("UNSORTED:\n");
        for(int i=0; i<10; i++){
            printf("%s\n", newList[i]);
        }
    
        quickSort(newList, 0, 9);
    
        printf("\n\nSORTED:\n");
        for(int i=0; i<10; i++){
            printf("%s\n", newList[i]);
        }
        return 0;
    }

  6. #6
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    I should have mentioned too, it would be helpful if you could post exactly how it doesn't work. Does it not compile? If so, please copy-paste any error messages or warning form your compiler exactly as they appear, with line numbers. Does it crash? Does it give incorrect output? If so, provide the sample input, the output you expect and the output you actually get.

    Just remember that for the future, I'm pretty sure your only problem is what I mentioned in post #4.

  7. #7
    Registered User
    Join Date
    Feb 2013
    Posts
    33
    I've noticed though that the only thing that got swapped was "cheese" and "hello".

    EXPECTED OUTPUT
    adam
    banana
    cheese
    dog
    hello
    oval
    ruler
    stinky
    water
    worm

    ACTUAL OUTPUT
    cheese
    adam
    banana
    dog
    hello
    oval
    ruler
    water
    worm
    stinky
    Last edited by ChickenChowMinh; 02-13-2013 at 06:38 PM.

  8. #8
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Add this, a new line 10, (push the others down 1 line):
    Code:
    if(lo == hi) return;
    This is just a suggestion, but your while(i<=j) causes i to be compared to j, before the REAL values has been found for i and j.

    I use
    Code:
    do {    //code always executes at least one time
        while ... etc. increment i
        while ... etc. decrement j
       if(i<=j) {
          swap i and j
          ++i
          --j
       }
    }while(i<=j);
    which works fine.

  9. #9
    Registered User
    Join Date
    Feb 2013
    Posts
    33
    nothing happened

  10. #10
    Registered User
    Join Date
    Feb 2013
    Posts
    33
    Okay I'm getting a bit closer now lol. Here's what I have..

    EXPECTED OUTPUT
    adam
    banana
    cheese
    dog
    hello
    oval
    ruler
    stinky
    water
    worm

    ACTUAL OUTPUT
    adam
    banana
    cheese
    dog
    hello
    worm
    ruler
    water
    oval
    stinky


    Code:
    void quickSort(char a[][20], int low, int high){ //passed it correctly
    
        int l = low;
        int h = high;
    
        int pivot = low;
    
        if(high-low >= 1){
            char pivotWord[20];
            strcpy(pivotWord,a[pivot]);
    
            do{
                while((strcmp(a[l],pivotWord)== -1) || (strcmp(a[l],pivotWord)== 0) && l<=high && h>l){
                    l++;
                }
                while((strcmp(a[h],pivotWord)== 1) && h>=low && h>=1){
                    h--;
                }
                if(h>l){
                    char temp[20];
                    strcpy(temp, a[l]);
                    strcpy(a[l], a[h]);
                    strcpy(a[h], temp);
                }
            }
            while(h>l);
    
            char temp[20];
            strcpy(temp, a[h]);
            strcpy(a[h], a[pivot]);
            strcpy(a[pivot], temp);
        }
    
        if(strcmp(a[low],a[h]) == -1){
            quickSort(a, low, h);
        }
        if(strcmp(a[l],a[high]) == -1){
            quickSort(a, l, high);
        }
    
    }
    Last edited by ChickenChowMinh; 02-13-2013 at 08:11 PM.

  11. #11
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Compare it to this:

    Code:
    #include <stdio.h>
    #include <string.h>
    
    void quicksort(char newList[][20], int lo, int hi);
    
    int main(void) {
       int i; 
       char newList[10][20];
        strcpy(newList[0], "hello");
        strcpy(newList[1], "adam");
        strcpy(newList[2], "banana");
        strcpy(newList[3], "dog");
        strcpy(newList[4], "cheese");
        strcpy(newList[5], "worm");
        strcpy(newList[6], "ruler");
        strcpy(newList[7], "water");
        strcpy(newList[8], "oval");
        strcpy(newList[9], "stinky");
     
       for(i=0;i<10;i++)
          printf("%s\n",newList[i]);
    
       quicksort(newList,0,9);
       printf("\n\n");
       for(i=0;i<10;i++)
          printf("%s\n",newList[i]);
    
    
       return 0;
    }
    void quicksort(char newList[][20], int lo, int hi) {
       int i=lo; // even=0;
       int j=hi;
       if(lo == hi) return;
       char pivot[20],temp[20];
       strcpy(pivot,newList[(lo+hi)/2]); 
       
      // Split the array into two parts 
       do {    
          while (strcmp(newList[i], pivot) < 0) i++;
          while (strcmp(newList[j], pivot) > 0) j--;
          if (i<=j) {  
             strcpy(temp,newList[i]);
             strcpy(newList[i],newList[j]);
             strcpy(newList[j],temp);
             ++i;
             --j;
          }
       } while(i<=j);
      
       //printf("lo:%d  j:%d  i:%d  hi:%d \n",lo,j,i,hi); //Sleep(20);
       if (lo < j) quicksort(newList,lo, j); 
       if (i < hi) quicksort(newList,i, hi); 
    
    }

  12. #12
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    Code:
    while((strcmp(a[l],pivotWord)== -1)
    while((strcmp(a[h],pivotWord)== 1)
    if(strcmp(a[low],a[h]) == -1){
    if(strcmp(a[l],a[high]) == -1){
    Read the docs for strcmp, it is only guaranteed to return values greater than, less than or equal to zero. There is no guarantee that it will be +/- 1, so you should change == -1 to < 0 and == 1 to > 0. This technically could be part of your problem, but it is unlikely.

  13. #13
    Registered User
    Join Date
    Feb 2013
    Posts
    33
    Wow that works perfectly. Thank you so much!

  14. #14
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    You have zeroed in on a problem or feature, with a lot of sorting algorithms. They're a bit "brittle". Change one thing the wrong way and wooot! you're toast!

    And you're welcome.

  15. #15
    Registered User
    Join Date
    Feb 2013
    Posts
    33
    The one thing I'd like to see is if I could sort a list of words with different cases and numbers :X I'm gonna make a few changes to see if I can implement that!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Randomized Quicksort problem
    By Grigoris Savvas in forum C Programming
    Replies: 2
    Last Post: 04-06-2012, 11:33 PM
  2. Quicksort-1000000-lines problem
    By gwmexod in forum C Programming
    Replies: 9
    Last Post: 06-15-2006, 03:01 AM
  3. Quicksort problem, now with clear code
    By rvanbeusichem in forum C Programming
    Replies: 1
    Last Post: 11-25-2004, 01:54 PM
  4. quicksort problem
    By spinner in forum C Programming
    Replies: 9
    Last Post: 05-04-2003, 02:02 PM
  5. Quicksort problem
    By Unregistered in forum C Programming
    Replies: 1
    Last Post: 04-17-2002, 08:23 AM