Thread: Quicksort

PHP Code:

int partition(int arr[], int left, int right)

{

      int i = left, j = right;

      int tmp;

      int pivot = arr[(left + right) / 2];

     

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

            }

      };

     

      return i;

}

 

void quickSort(int arr[], int left, int right) {

      int index = partition(arr, left, right);

      if (left < index - 1)

            quickSort(arr, left, index - 1);

      if (index < right)

            quickSort(arr, index, right);

} 


The reason why the range of the array decreases in size, is it because of the line of code "return i;"? Moreover, does "index - 1" make it so that the left range of the array decreases in size faster than the right one? Last question: Why won't the program work if I write "index" instead of "index - 1"? I know that there would be a conflict in the algorithm, but I don't know exactly why it wouldn't work.

Why won't the program work if I write "index" instead of "index - 1"

What happens when you try that? Do you get errors or is the output wrong?

Originally Posted by Norm

What happens when you try that? Do you get errors or is the output wrong?

I get errors.

If you want help with the errors, you need to post the full text of the error messages.

It's just a theoretical question. I am not trying to make a program or anything.

It looked like You were asking a specific programming question. If you change how large the index is for an array, you get an exception. No theory, very practical.

What?

I am trying to fully understand the Quicksort algorithm, but since I can only simulate the first turn mentally I have a hard time understanding why it doesn't work if I replace "index - 1" with "index".