Sort arrays with pointers using quicksort

Question

I'm trying to sort the values in the array "tab" using quicksort, but it isn't working. the main function just set names and salaries for each tab[n]

typedef struct employee Employee;

struct employee{
  char name[81];
  float salary;
};

Employee *tab[10];

void sort(Employee **tab, int begin, int end){
  int p = tab[(begin + end) / 2] , i = end, j = begin;  
  /*p is the pivot*/
  do{
    while(tab[i]->salary < p && i < end) i++; 
    while(tab[j]->salary > p && j > begin) j--; 

    if(i <= j){
      int tmp = tab[i]->salary;
      tab[i]->salary = tab[j]->salary;
      tab[j]->salary = tmp;
      i++; j--;
    }
  }while(i <= j);

  if(begin < j) sort(tab, begin, j);
  if(end > i) sort(tab, i, end);
}

In what way isn't it working? What size of array is it failing on (0, 1, 2, 3, 4, more elements)? What is the sample data that it is failing on? What is the Employee structure looking like? Why are you only swapping salaries and not the whole employee records? The person whose name comes first ends up with the lowest salary, ad the person whose name comes last ends up with the highest salary? Or vice versa? — Jonathan Leffler
– Jonathan Leffler, Commented Sep 1, 2019 at 23:05
I could be wrong, but shouldn't it be float p = tab[(begin + end) / 2] ->salary? In the 2 while loops that follow you are comparing a float (tab[i]->salary and tab[j]->salary) to an int (p) which (as mangusta points out) in turn has been equated to a structure element pointer, You should swap the i and j th structure elements, not just the salary. — pjaj
– pjaj, Commented Sep 1, 2019 at 23:46
You get my up-vote @JL2210 but I'm not sure we'll win in the long run. Sometime in 5 years time or so I may stop using that version (it's a precanned sequence I copy'n'paste, not something I type ab initio whenever I need it). — Jonathan Leffler
– Jonathan Leffler, Commented Sep 2, 2019 at 0:23
@JL2210: I keep them on GitHub in my SOQ repository — in the src/scripts directory. This one is sscce. I work on Macs mostly, so sscce | sed 5q | pbcopy gives me the text quoted above in the paste buffer, and command-V (⌘-V) puts it into the comment. The other links in lines 6+ are: See also How to Ask Questions the Smart Way and Writing the perfect question — Jonathan Leffler
– Jonathan Leffler, Commented Sep 2, 2019 at 0:29

rcgldr · Accepted Answer · 2019-09-06 06:34:49Z

Changes noted in comments. This is a descending order sort (as asked in a follow up question).

#include <stdio.h>

typedef struct employee{
    char name[81];
    float salary;
}Employee;

void sort(Employee **tab, int begin, int end){
    float p = tab[(begin + end) / 2]->salary; /* float needed for compare == */
    int i = begin, j = end;
    Employee *tmp;                          /* microsoft is c89 */

    while(i <= j){                      /* using while */
        while(tab[i]->salary > p) i++;  /* >, <= pivot stops scan */
        while(tab[j]->salary < p) j--;  /* <, >= pivot stops scan */
        if(i > j)                       /* using break */
            break;
        tmp = tab[i];
        tab[i] = tab[j];
        tab[j] = tmp;
        i++; j--;
    }

    if(begin < j) sort(tab, begin, j);
    if(end > i) sort(tab, i, end);
}

int main(int argc, char**argv)
{
    Employee tab[] = {{"john", 525.}, {"jack", 520.},
                      {"mary", 537.}, {"jane", 523.},
                      {"joan", 548.}, {"sam",  524.},
                      {"lisa", 527.}, {"ann",  541.},
                      {"tom",  521.}, {"ted",  531.}};
    Employee *ptr[sizeof(tab)/sizeof(tab[0])];
    int i;
    /* create array of pointers */
    for(i = 0; i < (sizeof(tab)/sizeof(tab[0])); i++)
        ptr[i] = &tab[i];
    sort(ptr, 0, sizeof(ptr)/sizeof(ptr[0])-1);
    for(i = 0; i < (sizeof(ptr)/sizeof(ptr[0])); i++)
        printf("%5s %6.2f\n", ptr[i]->name, ptr[i]->salary);
    return 0;
}

Collectives™ on Stack Overflow

Sort arrays with pointers using quicksort

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related