Quicksort an Array using a function

[oudavid1]

Hey guys, been at it all day, but I just cant seem to figure out this assignment I have. It's not due for a while but I am almost done. I just need help with quicksort.

Basically the main program generates random numbers, puts them in an array, copies the array, sends them to 3 separate functions in three separate .cpp files. The objective is to test 3 different sorts, bubble, shell, and quicksort and then have each of the 3 programs sort the array(all arrays have same 20 values) and assign and then return them to the screen. Bubble and shell are easy. But I cannot seem to figure out when the quicksort function(in its' own file) is done and tell it to print the sorted array. Here is my code for the quicksort file:

void quickSort(int arr[], int left, int right) {
      int i = left, j = right;
      bool end = false;
      int tmp;
      int pivot = arr[(left + right) / 2];
      /* partition */
      while (i <= j) {
            while (arr[i] < pivot)
                  i++;
            while (arr[j] > pivot)
                  j--;
            if (i <= j) {
                  tmp = arr[i];
                  arr[i] = arr[j];
                  arr[j] = tmp;
                  i++;
                  j--;
            } 
      }   
      /* recursion */
      if (left < j){
         
            quickSort(arr, left, j);
            }
      if (i < right){
            
            quickSort(arr, i, right);
}
      if (i >= right && left >= j){
            
}

So what I am asking is if this is the proper format to quicksort something and then have it returned? Is there a better way to set this up to where when the sort is finally finished, to figure out where or when that exactly is.

Is there a way to just pass the array generated in the main program to a function, have it sorted in the function, and then returned? I know I am asking a lot; it's been a long day. Any tips are appreciated.

[ssrun]

Quicksort is usually implemented as 2 separate functions where an auxiliary function is used to select the pivot, arrange the two halves and then return the pivot index. The enclosing function then calls itself twice to sort the two remaining halves.

As a template:

void quickSort(int a[], int s, int e) {
  if (s < e) {  //only sort if there is more than 1 element
      int p = pivot(a, s, e);

      quickSort(a, s, p - 1);  //sort all the elements to the left of the pivot
      quickSort(a, p + 1, e);  //sort all the elements to the right of the pivot
  }
}

int pivot(int a[], int s, int e) {
  // do your pivot, sorting and return the pivot index
}

Also, the pivot is not usually located in the middle of the array. Simplest case for learning purposes is to use the last value in the array as your pivot value. Start j = right - 1. Once you exit the while (i <= j) loop you need to swap the values at arr[i] and arr[right] so that the pivot value is now in the "middle" of the list so that all values to its left are no greater than it and all values to its right are no less than it.

Then you need to quicksort the left half and right half separately and keep repeating this until there are no more elements to sort. This will then sort the whole array.

Also the while loops should be:

while (arr[i] <= pivot && i <= j) {
  i++;
}

while (arr[j] >= pivot && j >= i) {
  j--;
}

[oudavid1]

So in the pivot function, what am i using the arguments for?

[ssrun]

You use the arguments to traverse the array from the left side and from the right side swapping elements that are out of position relative to the pivot's value.

Essentially the work that your while loop is doing is the pivot() function but there are still a few bugs in your code.

[oudavid1]

I got it all figured out, man! Thank you so much, I really apperciate you taking the time. God Bless.