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);
    }
}

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.

Oops you're right. Give me a minute and I'll post it.

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?

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;
}

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.

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

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.

nothing happened

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);
    }

}

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); 

}

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.

Wow that works perfectly. Thank you so much!

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.

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!