Демонстрация стабильности Quicksort
Я понимаю, что быстрая сортировка действительно нестабильна (в случае примитивов) из-за того, как работает разделение / обмен на большие расстояния. Я пытаюсь понять, что произойдет, если использовать быструю сортировку для сортировки сложных объектов с одинаковыми ключами. По сути, почему java Collections.sort не использует Quicksort.
Вот демонстрационное приложение, которое я создал, чтобы помочь моему пониманию. Согласно этому приложению, объекты с одинаковыми ключами сохраняют порядок ввода. Я знаю, что здесь у меня есть некоторые пробелы в понимании. Я искал в Интернете, но большинство примеров основаны на целочисленной сортировке.
Пожалуйста, помогите мне разобраться в проблемах стабильности быстрой сортировки.
DEMO
import java.util.*;
public class QuickSortStabilityDemo {
static class Node implements Comparable<Node> {
String name;
int rank;
public Node(String name, int rank) {
this.name = name;
this.rank = rank;
}
@Override
public int compareTo(Node o) {
int result = this.name.compareTo(o.name);
if (result == 0) {
return this.rank == o.rank ? 0 : this.rank < o.rank ? -1: 1;
}
else {
return result;
}
}
@Override
public String toString() {
return "{" + this.name + "," + this.rank + "," + this.hashCode() + "}" ;
}
}
//Fisher-Yates
public void shuffleArray(Node[] arr) {
Random random = new Random();
int n = arr.length;
for(int i=n-1; i>=0; i--) {
int j = random.nextInt(i+1);
Node temp = arr[i];
arr[i]= arr[j];
arr[j]=temp;
}
}
private void swap(Node[] arr, int i, int j) {
Node temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public void sort(Node[] arr, int start, int end) {
if (start >= end) {
return;
}
Node pivot = arr[start];
int lt = start;
int gt = end;
for(int current=start+1;current <= gt; ) {
if (arr[current].compareTo(pivot) < 0) {
swap(arr,current,lt);
current++;
lt++;
}
else if (arr[current].compareTo(pivot) > 0) {
swap(arr,current,gt);
gt--;
}
else {
current++;
}
}
sort(arr,start,lt-1);
sort(arr,gt+1,end);
}
public static void main(String[] args) {
QuickSortStabilityDemo sort = new QuickSortStabilityDemo();
String[] cities = {"New York","Jersey City","Pittsburgh"};
List<Node> list = new ArrayList<>();
for(int i=0;i <3;i++) {
for(int j=1; j <=3; j++) {
list.add(new Node(cities[i],i));
}
}
Node[] arr = list.toArray(new Node[list.size()]);
System.out.println("Before sorting...");
System.out.println(Arrays.toString(arr));
sort.sort(arr,0,arr.length-1);
System.out.println("After sorting...");
System.out.println(Arrays.toString(arr));
}
}
Ответы 2
Если вы хотите увидеть нестабильный результат, НЕ СЛЕДУЕТ сравнивать rank.
Если сравнить имя и звание, то между элементами будет строгий порядок, тогда результат будет стабильным.
Нестабильный результат возникает только тогда, когда два элемента равны друг другу.
Вот моя версия:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class QuickSortStabilityDemo {
static class Node implements Comparable<Node> {
String name;
int rank;
public Node(String name, int rank) {
this.name = name;
this.rank = rank;
}
@Override
public int compareTo(Node o) {
return this.name.compareTo(o.name);
}
@Override
public String toString() {
return "{" + this.name + "," + this.rank + "}";
}
}
private void swap(Node[] arr, int i, int j) {
Node temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public void sort(Node[] arr, int start, int end) {
if (start >= end) {
return;
}
Node pivot = arr[start];
int lt = start;
int gt = end;
for (int current = start + 1; current <= gt; ) {
if (arr[current].compareTo(pivot) < 0) {
swap(arr, current, lt);
current++;
lt++;
} else if (arr[current].compareTo(pivot) > 0) {
swap(arr, current, gt);
gt--;
} else {
current++;
}
}
sort(arr, start, lt - 1);
sort(arr, gt + 1, end);
}
public static void main(String[] args) {
QuickSortStabilityDemo sort = new QuickSortStabilityDemo();
String[] cities = {"New York", "Jersey City", "Pittsburgh"};
List<Node> list = new ArrayList<>();
for (int i = 1; i <= 3; i++) {
for (int j = 0; j < 3; j++) {
list.add(new Node(cities[j], i));
}
}
Node[] arr = list.toArray(new Node[list.size()]);
System.out.println("Before sorting...");
System.out.println(Arrays.toString(arr));
sort.sort(arr, 0, arr.length - 1);
System.out.println("After sorting...");
System.out.println(Arrays.toString(arr));
}
}
Вывод:
Before sorting...
[{New York,1}, {Jersey City,1}, {Pittsburgh,1}, {New York,2}, {Jersey City,2}, {Pittsburgh,2}, {New York,3}, {Jersey City,3}, {Pittsburgh,3}]
After sorting...
[{Jersey City,1}, {Jersey City,3}, {Jersey City,2}, {New York,2}, {New York,1}, {New York,3}, {Pittsburgh,2}, {Pittsburgh,3}, {Pittsburgh,1}]
Вы можете видеть, что {Jersey City,2} стоит ПЕРЕД {Jersey City,3} перед сортировкой.
Но после сортировки {Jersey City,2} - ПОСЛЕ {Jersey City,3}.
Это нестабильный результат.
PS: Если вы используете другие стабильные алгоритмы, результат должен быть {J,1},{J,2},{J,3},{N,1},{N,2},{N,3},{P,1},{P,2},{P,3}.
@shawn - Спасибо, что ответили на мой вопрос. Если похожие объекты содержат хотя бы одно отличное свойство, а функция компаратора обрабатывается на неотличимых свойствах, то быстрая сортировка даст нестабильный результат. Вот почему в моей первоначальной демонстрации я убедился, что все объекты NY имеют ранг 1, объекты JC - ранг 2, а Pgh - ранг 3. И я использовал хэш-код для отслеживания исходного порядка объектов.
Вы, должно быть, что-то неправильно поняли? Предположим, у вас есть объекты с 2 полями (A, B) или объекты с 3 полями (X, Y, Z). Есть ли разница между: (A равно, B уникально) и (X равно, Y равно, Z уникально) ?? Почему бы вам не объединить X + Y в B, чтобы сделать их одинаковыми? Подумайте о (A = myName, B = myRank) или (X = yourName, Y = yourRank, Z = hashCode)
Я нашел ответ:
В исходной демонстрации, которую я опубликовал, данные были немного надуманными. Свойства объектов в каждом наборе одинаковы и сделано целенаправленно. Массив не тасовал; установить точку поворота на начальный элемент сортируемой части массива.
Пока я отлаживал свою демонстрацию дальше, хотя объекты Нью-Йорк и JC сохранили свой исходный порядок, объекты Пгх действительно изменили свой исходный порядок вставки. Поэтому я действительно увидел нестабильность алгоритма.
Я использовал хэш-код этих элементов, чтобы отслеживать их исходный порядок вставки.
Вот результат прогона:
[{New York,0,1163157884}
, {New York,0,1956725890}
, {New York,0,356573597}
, {Jersey City,1,1735600054}
, {Jersey City,1,21685669}
, {Jersey City,1,2133927002}
, {Pittsburgh,2,1836019240}
, {Pittsburgh,2,325040804}
, {Pittsburgh,2,1173230247}
]
After sorting
[{Jersey City,1,1735600054}
, {Jersey City,1,21685669}
, {Jersey City,1,2133927002}
, {New York,0,1163157884}
, {New York,0,1956725890}
, {New York,0,356573597}
, {Pittsburgh,2,325040804}
, {Pittsburgh,2,1173230247}
, {Pittsburgh,2,1836019240}
]
Если я перетасовываю входной массив, нестабильность алгоритма становится более очевидной.
Вот результат выполнения (с перемешанным вводом):
Original order
[{New York,0,1163157884}
, {New York,0,1956725890}
, {New York,0,356573597}
, {Jersey City,1,1735600054}
, {Jersey City,1,21685669}
, {Jersey City,1,2133927002}
, {Pittsburgh,2,1836019240}
, {Pittsburgh,2,325040804}
, {Pittsburgh,2,1173230247}
]
After shuffling
[{New York,0,1163157884}
, {New York,0,1956725890}
, {Pittsburgh,2,325040804}
, {Jersey City,1,2133927002}
, {New York,0,356573597}
, {Jersey City,1,1735600054}
, {Pittsburgh,2,1836019240}
, {Pittsburgh,2,1173230247}
, {Jersey City,1,21685669}
]
After sorting
[{Jersey City,1,21685669}
, {Jersey City,1,2133927002}
, {Jersey City,1,1735600054}
, {New York,0,1956725890}
, {New York,0,356573597}
, {New York,0,1163157884}
, {Pittsburgh,2,1173230247}
, {Pittsburgh,2,1836019240}
, {Pittsburgh,2,325040804}
]
Пожалуйста, дайте мне знать, есть ли какие-либо предложения по этому поводу.
Я вижу, что кто-то проголосовал против моего ответа. Дайте мне знать, пожалуйста, почему?
Правильно, сравнивайте только имена. Если вы сравните все поля в классе, результат всегда будет полностью упорядоченным.