My assignment is preforming quick sort on array of structs using pointers to the first and last elements of the array. This is the struct-

typedef struct Bus {
int number, distance, time; } Bus;

At some point of the program, i have an array of user-defined number of these struct. My goal is to sort the array by the time (lowest to highest). The functions that i need to fill are-

void swap(Bus *a, Bus *b)    
void quick_sort (Bus *start, Bus *end) 
Bus *partition (Bus *start, Bus *end)

that's my implementation-

void swap(Bus *a, Bus *b)
{
  Bus tmp = *a;
  *a = *b;
  *b = tmp;
}

void quick_sort (Bus *start, Bus *end)
{
  long long n = end - start;
  if (n > 2)
  {
    Bus * pivot = partition (start, end);
    quick_sort (start, (end-1));
    quick_sort ((start 1), end);
  }

}

Bus *partition (Bus *start, Bus *end)
{
  long long n = end - start;
  int pivot = (end -1)->time;
  int i = start->time;
  int j = (end - 1)->time;
  for(;;)
  {
    
  }
}

I got this far and didn't knew how to continue. I will appreciate your help.

edit- Thats how i call the function from main- quick_sort(arr, (arr num_of_lines)) when num_of_lines is the size of the array.

CodePudding user response：

First, your quick_sort is wrong. It should look like this:

void quick_sort(Bus *start, Bus *end)
{
    long long n = end - start;
    if (n >= 2)
    {
        Bus *pivot = partition(start, end);
        quick_sort(start, pivot  );
        quick_sort(pivot, end);
    }
}

Note the length condition. you should only skip partitions of length 0 or 1, not 2. And note the post-increment adjustment to the pivot index in the first recursive call. This ensures the subsequent recursion does not include the one element you do not want to include in the recursion: the pivot indexed value.

As far as the partition function is concerned, also wrong. It should look like this (I'm assuming you're using the Lomuto Partition Scheme:

int *partition(Bus *beg, Bus *end)
{
    long len = end - beg;
    if (len < 2)
        return beg;

    Bus *last = end-1;
    Bus *pvt = beg;
    for (;beg != last;   beg)
    {
        if (beg->time < last->time)
            swap(pvt  , beg);
    }    
    swap(pvt, last);

    return pvt;
}