Демо-версия Quicksort

Question

Я понимаю, что быстрая сортировка действительно нестабильна (в случае примитивов) из-за того, как работает разбиение / обмены на большие расстояния.Я пытаюсь понять, что происходит, если бы быстрая сортировка использовалась для сортировки сложных объектов с равными ключами.По сути, почему 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));
        }

}

Answer 1

Я нашел ответ:

В оригинальной демонстрации, которую я разместил, данные были немного надуманными.Свойства объектов в каждом наборе одинаковы и выполняются целенаправленно.Я не тасовал массив;установите pivot на начальный элемент части массива, который сортируется.

Когда я продолжил отладку демонстрации, события NY и JC сохранили свой первоначальный порядок Pgh объекты действительно изменили свой первоначальный порядок вставки.Поэтому я видел нестабильность алгоритма.

Я использовал хеш-код этих элементов для отслеживания их первоначального порядка вставки.

Вот результат выполнения:

[{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}
]

Пожалуйста, дайте мне знать, если есть какие-либо предложения поэтот ответ

Answer 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}.