Почему быстрый код сортировки нарушает стабильность?

Question

Ниже partition() логика используется qSort(),

static void qSort(List *list, int low, int high, compareTo compare){ 

    if(high <= low){ 
    return; // no partition for sub array of size 1 
    } 
    int pivotIndex = partition(list, low, high, compare); 
    qSort(list, low, pivotIndex-1, compare); 
    qSort(list, pivotIndex+1, high, compare); 
} 

static int partition(List *list, int low, int high, compareTo compare){ 

    int pivot = low; 
    int leftIndex = low + 1; 
    int rightIndex = high; 
    const void **array = list->array; 

    while(true){ 

    while(leftIndex < high && (compare(array[leftIndex], array[pivot]) < 0)){ 
     leftIndex++; 
    } 

    while(rightIndex > pivot && (compare(array[rightIndex], array[pivot]) > 0)){ 
     rightIndex--; 
    } 

    if(leftIndex >= rightIndex){ 
     break;    // partition is done 
    } 
    if(compare(array[leftIndex], array[rightIndex]) == 0){ 
     leftIndex++; rightIndex--; 
     continue;     //Maintain stability 
    } 
    arraySwap(list, leftIndex, rightIndex); 
    } 
    if(compare(array[pivot], array[rightIndex]) != 0){ 
    arraySwap(list, pivot, rightIndex);   // Maintain stability 
    } 
    return rightIndex; 
} 

---

где arraySwap() & & compare() определяется как,

void arraySwap(List *list, int i, int j){ 

    const void **array = list->array; 

    const void *tempPointer = array[i]; 
    array[i] = array[j]; 
    array[j] = tempPointer; 
} 

int compare(const void *key, const void *item){ 

    if(((Person *)key)->age < ((Person *)item)->age ){ 

    return -1; 
    }else if(((Person *)key)->age > ((Person *)item)->age ){ 

    return 1; 
    }else{ 

    return 0; 
    } 
} 

---

partition() должен поддерживать стабильность, имея дополнительные проверки перед каждый arraySwap().

Но ниже выхода показывает, что стабильность частично сохраняется (ключ 10 стабилен в отличие от ключа 50),

$ ./sort.exe 
Before sorting 
Age,LastName,FirstName 
    50 B A 
    30 A B 
    20 X D 
    10 F A 
    50 A B 
    90 V E 
    60 N M 
    10 A B 
After sorting 

Age,LastName,FirstName 
    10 F A 
    10 A B 
    20 X D 
    30 A B 
    50 A B 
    50 B A 
    60 N M 
    90 V E 

---

В функции partition(), ниже кода фрагмента, чтобы просто поддерживать стабильность,

while(true){ 
    .... 
    if(compare(array[leftIndex], array[rightIndex]) == 0){ 
    leftIndex++; rightIndex--; 
    continue;      //Maintain stability 
    } 
    .... 
} 
...  
if(compare(array[pivot], array[rightIndex]) != 0){ 
    ... 
} 

---

Вопрос:

Почему запись с ключом 50 нестабильна?

Answer 1

Быстрая сортировка нестабильна, так как этап разделения может менять элементы, сравнимые друг с другом, и таким образом ставить их в другом порядке, чем в исходном массиве.

Для создания быстрой сортировки требуется функция сравнения, которая всегда будет возвращать ноль для разных элементов.

Answer 2

Избегание замены одинаковых элементов не является достаточным для достижения стабильной быстрой сортировки. Рассмотрим, например, этот простой случай:

key value 
2 A 
3 B 
3 C 
1 D 
1 E 

Принимая первый элемент в качестве шарнира, первое разделение включает в себя три свопы (1, 4) и (2, 3) в основной части перегородки, затем (0, 2), чтобы поставить стержень на место. Это дает:

1 D 
1 E 
2 A 
3 C 
3 B 

Нет элементов, имеющих одинаковые ключи не были перепутаны, но относительный порядок двух элементов с ключом 3 было отменено. Это происходит, естественно, на обоих концах раздела, в результате того, что верхняя половина массива проходит в обратном порядке.

Кроме того, у вас есть возможность нестабильности при замене шарнирного элемента на место. Поскольку он начинается в крайнем левом углу массива, если есть какие-либо другие элементы с тем же ключом, которые попадают в левый раздел, но элемент на крайнем правом конце левого раздела имеет другой ключ, тогда элемент раздела будут перемещены относительно других, имеющих один и тот же ключ.

Чтобы убедиться в стабильной сортировке, функция сравнения должна учитывать исходный порядок элементов. Для этого обычно требуется использование O (N) дополнительных метаданных.Было бы справедливо интерпретировать это как сказать, что quicksort не может быть стабильным вообще, поскольку включение исходного порядка элементов в функцию сравнения эффективно делает все элементы неодинаковыми, и поэтому вопрос стабильности остается спорным.