Подтвердить что ты не робот

Quicksort с 3-полосным разделом

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

4b9b3361

ОТВЕТЫ

Ответ 1

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

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

A два раздела Quick Sort выберет значение, скажем 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 3 (n), которое так мало меняется от регулярного quicksort nlog 2 (n).

Ответ 3

если вы действительно измельчите математику, используя , оставляя количество разделов в качестве параметра, а затем оптимизируя этот параметр, вы обнаружите, что разделы e (= 2,718...) дают самую быструю производительность. на практике, однако, наши языковые конструкции, cpus и т.д. оптимизированы для двоичных операций, поэтому стандартное разбиение на два набора будет самым быстрым.

Ответ 4

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

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

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

Например, если мы выбираем первый 3 в качестве шарнира, а затем 3-полосная раздела А, используя Алгоритм Дейкстры бы расположить исходный массив и возвращают два индекса 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 будут одинаковыми.

Ответ 5

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

Ответ 6

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

Ответ 7

  //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();

}

}