I'm learning about quick sort and have been having trouble for days with this problem. I implemented Hoare partition algorithm according to the algorithm on wikipedia: https://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme

// Sorts a (portion of an) array, divides it into partitions, then sorts those
algorithm quicksort(A, lo, hi) is 
  if lo >= 0 && hi >= 0 && lo < hi then
    p := partition(A, lo, hi) 
    quicksort(A, lo, p) // Note: the pivot is now included
    quicksort(A, p   1, hi) 

// Divides array into two partitions
algorithm partition(A, lo, hi) is 
  // Pivot value
  pivot := A[ floor((hi   lo) / 2) ] // The value in the middle of the array

  // Left index
  i := lo - 1 

  // Right index
  j := hi   1

  loop forever 
    // Move the left index to the right at least once and while the element at
    // the left index is less than the pivot
    do i := i   1 while A[i] < pivot
    
    // Move the right index to the left at least once and while the element at
    // the right index is greater than the pivot
    do j := j - 1 while A[j] > pivot

    // If the indices crossed, return
    if i ≥ j then return j
    
    // Swap the elements at the left and right indices
    swap A[i] with A[j]

Here is my c code:

#include <iostream>
int hoare_partition(int A[], int low, int high){
    int pivot = A[high];
    int i = low-1;
    int j = high 1;
    while (true){
        do i  ; while (A[i] < pivot);
        do j--; while (A[j] > pivot);
        if (i >= j) return j; 
        std::swap(A[i], A[j]);
    }
}
void quick_sort(int A[], int low, int high){
    if (low < high){
        int pivot = hoare_partition(A, low, high);
        quick_sort(A, low, pivot);
        quick_sort(A, pivot 1, high);
    }
}
int main(){
    int n; std::cin >> n;
    int A[n]; for (int i = 0; i < n; i  ) std::cin >> A[i];
    quick_sort(A, 0, n-1);
    for (int i = 0; i < n; i  ) std::cout << A[i] << " ";
    return 0;
}

The problem comes when I want to select the last element as pivot so I have set int pivot = A[high] and when I enter test case 5 4 3 2 1 my code is not working. After testing many times I found if I set pivot = A[from low to high-1] everything works fine, it only gives error when I set pivot = A[high].

Can anyone help me understand why things are not working in this case? And how to select last element as pivot with hoare's partition?

Thank you very much.

CodePudding user response：

TL;DR

The implementation you use may not choose the final element as a pivot.

Explanation

You need to carefully read the whole description of the algorithm. Specially, note the following quote from the section you linked:

The division returned is after the final position of the second pointer, so the case to avoid is where the pivot is the final element of the range and all others are smaller than it. Therefore the pivot choice must avoid the final element (in Hoare's description it could be any element in the range); this is done here by rounding down the middle position, using the floor function. This illustrates that the argument for correctness of an implementation of the Hoare partition scheme can be subtle, and it is easy to get it wrong.

Simple demo of this case is {4,3,2,5}, which comes in your data in the second recursion step: https://godbolt.org/z/hsca8EEG8.