CODEWITHSUNDEEP
cquicksortstructure
PaeneInsula
PaeneInsula

Reputation: 2100

quickSort array of structures: incorrect sort

I'm having a problem with the following VS 2010 code. Am trying to sort an array of structures. The code compiles without errors, is very fast, but has a problem in that the sort result is incorrect.

I am sorting by the "zip" character string (for test purposes, NOT numerically, but by character compare). I have a version of this running using the standard lib qsort, but want to do some further fiddling so am writing my own.

 struct address {

  char name[40];
  char street[40];
  char city[20];
  char state[30];
  char zip[21];
};


void qs_struct(struct address items[], int left, int right)
{

  int i, j;
  char *x;
  struct address temp;

  i = left; 
  j = right;
  x = items[(left+right)/2].zip;

  do {
      while((strcmp(items[i].zip,x) < 0) && (i < right)){ i++;}
      while((strcmp(items[j].zip,x) > 0) && (j > left)) { j--;}

    if(i <= j) {
      temp = items[i];
      items[i] = items[j];
      items[j] = temp;
      i++; j--;
    }
  } while(i <= j);

  if(left < j) qs_struct(items, left, j);
  if(i < right) qs_struct(items, i, right);
}


void qx(struct address items[], int count)
{
  qs_struct(items,0,count-1);
}

void fillStructWithRandomDataForTest(struct address *addr, int i, int j)
{
    char temp[444];


            sprintf(temp, "%d%d", j +i, j*i);
            strcpy(addr->name, temp);
            sprintf(temp, "%d%d", j +i, j*i);
            strcpy(addr->street, temp);

            sprintf(temp, "%d%d", j +i, j*i);
            strcpy(addr->city, temp);
            sprintf(temp, "%d%d", j +i, j*i);
            strcpy(addr->state, temp);

            sprintf(temp, "%d%d", j +i, j*i);
            strcpy(addr->zip, temp);

}

 void xqs(void)
  {
  struct address addrs[20];

   for (int i = 0, j = 33; i < 16; ++i, --j)
        fillStructWithRandomDataForTest(&addrs[i], i, j);

    qx(addrs, 16);

    // results: incorrectly sorted
    for (int k = 0; k < 16; ++k)
        printf("%s \n",addrs[k].zip);

 }

Upvotes: 0

Views: 1036

Answers (3)

PaeneInsula
PaeneInsula

Reputation: 2100

Instead of this:

 while((i < n) && (strcmp(list[i].name, key) < 0)) i++;


while((j > m) && (strcmp(list[j].name , key) > 0)) j--;

should be this:

 while((i <= n) && (strcmp(list[i].name, key) <= 0)) i++;
 while((j >= m) && (strcmp(list[j].name , key) > 0)) j--;

Upvotes: 0

Daniel Fischer
Daniel Fischer

Reputation: 183978

This

x = items[(left+right)/2].zip;

ties the pivot to a position. When the middle address is moved, the pivot against which the zips are compared is changed. That messes up the sort. You need to copy the zip against which to compare,

x = strdup(items[(left+right)/2].zip); // or strlen and malloc
while (...)
free(x);

Upvotes: 1

Mike Nakis
Mike Nakis

Reputation: 62129

It would be nice if you had told us in precisely what way your results are incorrect, but it is okay, let me guess: it prints nothing, right? All blank lines, eh?

The very last loop in your code uses k as loop counter, but then it uses i as an index to select a struct to printf(). This will always select addrs[16], which has not been initialized.

You need coffee. Or sleep. But not both.

Upvotes: 2

Related Questions