Быстрая сортировка с 3-сторонней перегородкой

Question

Что такое QuickSort с 3-сторонним разделом?

Answer 1

Изображение массива:

3, 5, 2, 7, 6, 4, 2, 8, 8, 9, 0

A Быстрая сортировка с двумя разделами выберет значение, скажем 4, и поместит каждый элемент больше 4 на одну сторону массива, а каждый элемент меньше 4 на другую сторону. Вот так:

3, 2, 0, 2, 4, | 8, 7, 8, 9, 6, 5

A Быстрая сортировка с тремя разделами выберет два значения для разделения и разделит массив таким образом. Давайте выберем 4 и 7:

3, 2, 0, 2, | 4, 6, 5, 7, | 8, 8, 9

Это небольшая разница в обычной быстрой сортировке.

Вы продолжаете разбиение каждого раздела, пока массив не будет отсортирован. Технически время выполнения - nlog ₃ (n), которое очень незначительно отличается от nlog ₂ (n) обычной быстрой сортировки.

Answer 2

http://www.sorting -algorithms.com / статический / QuicksortIsOptimal.pdf

Смотри также:

http://www.sorting -algorithms.com / быстрая сортировка 3-полосной

Я думал, что версия вопроса об интервью была также интересна. Он спрашивает, есть ли четыре версии разделов быстрой сортировки ...

Answer 3

Я думаю, что 3-х сторонний раздел от Djstrka.

Подумайте о массиве с элементами { 3, 9, 4, 1, 2, 3, 15, 17, 25, 17 }.

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

---

Например, если мы выберем первый 3 в качестве оси, то трехсторонний раздел с использованием Dijkstra упорядочит исходный массив и вернет два индекса m1 и m2, так что все элементы с индексом меньше чем m1 будет меньше 3, все элементы, индекс которых больше или равен m1 и меньше или равен m2, будут равны 3, а все элементы, чей индекс больше чем m2 будет больше 3.

В этом конкретном случае результирующий массив может быть { 1, 2, 3, 3, 9, 4, 15, 17, 25, 17 }, а значения m1 и m2 будут m1 = 2 и m2 = 3.

Обратите внимание, что результирующий массив может меняться в зависимости от стратегии, используемой для разбиения, но числа m1 и m2 будут одинаковыми.

Answer 4

, если вы действительно отшлифуете математику, используя формула Акра-Бацци , оставляя количество разделов в качестве параметра, а затем оптимизируете этот параметр, вы обнаружите, что e (= 2.718 ...) Перегородки дают самую быструю производительность. однако на практике наши языковые конструкции, процессоры и т. д. все оптимизированы для бинарных операций, поэтому стандартное разбиение на два набора будет самым быстрым.

Answer 5

Я думаю, что это связано со способом разбиения Дейкстры, где разделение на один элемент меньше, равно и больше, чем стержень. Только меньшие и большие разделы должны быть отсортированы рекурсивно. Вы можете увидеть интерактивную визуализацию и поиграть с ней на орех . Здесь я использовал красный / белый / синий цвета, потому что метод разделения обычно называют «проблемой голландского флага»

Answer 6

  //code to implement Dijkstra 3-way partitioning

  package Sorting;

  public class QuickSortUsing3WayPartitioning {

private int[]original;
private int length;
private int lt;
private int gt;

public QuickSortUsing3WayPartitioning(int len){
    length = len;
    //original = new int[length];

    original = {0,7,8,1,8,9,3,8,8,8,0,7,8,1,8,9,3,8,8,8};

}

public void swap(int a, int b){ //here indexes are passed
    int temp = original[a];
    original[a] = original[b];
    original[b] = temp;
}

public int random(int start,int end){
    return (start + (int)(Math.random()*(end-start+1)));
}

public void partition(int pivot, int start, int end){
    swap(pivot,start);  // swapping pivot and starting element in that subarray

    int pivot_value = original[start];
    lt = start;
    gt = end;

    int i = start;
    while(i <= gt) {

        if(original[i] < pivot_value) {
            swap(lt, i);
            lt++;
            i++;
        }

        if(original[i] > pivot_value) {
            swap(gt, i);
            gt--;
        }
        if(original[i] == pivot_value)
            i++;
    }
}

public void Sort(int start, int end){
    if(start < end) {

        int pivot = random(start,end); // choose the index for pivot randomly
        partition(pivot, start, end); // about index the array is partitioned

        Sort(start, lt-1);
        Sort(gt+1, end);

    }
}

public void Sort(){
    Sort(0,length-1);
}

public void disp(){
    for(int i=0; i<length;++i){
        System.out.print(original[i]+" ");
    }
    System.out.println();
}

public static void main(String[] args) {

    QuickSortUsing3WayPartitioning qs = new QuickSortUsing3WayPartitioning(20);
    qs.disp();

    qs.Sort();
    qs.disp();

}

}