Быстрая сортировка?

Question

Я довольно новичок в программировании и хотел бы получить визуальное представление алгоритма quicksort с использованием медиаинформации 3 и обрезать 3.

Мне хотелось бы увидеть весь итерационный процесс, поскольку алгоритм Java трудно понять для меня.

Например, попробуйте применить быструю сортировку в этом массиве: [2, 6, 3, 1, 6, 5, 2, 4, 8]

С правилом медианного из-трех, стержень является медиана самого левого, центрального и правого элементов. Итак, медиана 2, 6 и 8 равна 6. Что теперь?

Answer 1

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

Перед секционирования:

[2,6,3,1,6,5,2,4,8] 

После разделения <6 слева, >=6 справа:

[2,3,1,5,2,4] [6,6,8] 

Чтобы отсортировать слева и справа, повторите ту же процедуру с обеих сторон.

Я расскажу вам о деталях процедуры разбиения (истинный оставляет элементы в другом порядке).

Проблемы помнить:

• после разделения, должно быть по крайней мере один элемент в обе стороны, в противном случае может бесконечный цикл процедура (в худшем случае, единственный элемент влево может быть стержнем);

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

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

• процедура является излишним для небольших массивов, поэтому в этом случае целесообразно перейти на более простой метод, например StraightInsertion или StraightSelection.

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

Answer 2

Таким образом, среда 2,6,8 равна 6. Что теперь?

Следующий шаг состоит в том, чтобы разделить массив на левую половину, содержащий элементы, которые меньше 6, и правую половину, содержащие элементы, которые равны или больше 6. Затем мы вызываем quicksort на каждую половину ,

Следующая программа Java реализует quicksort, отображая каждый подмассив до и после сортировки. Он также отображает выбор медианы.

import java.io.*; 

public class Quicksort { 
    void swap(int[] data, int i, int j) { 
    int t = data[i]; 
    data[i] = data[j]; 
    data[j] = t; 
    } 

    void display(int[] data, int left, int right) { 
    for (int i = 0; i < right; ++i) { 
     System.out.print(i < left ? " " : " "+data[i]); 
    } 
    System.out.println(); 
    } 

    //--- in-place implementation with median-of-three pivot 
    int quicksort(int[] data, int left, int right, int callId) { 
    int saveCallId = callId; 
    System.out.print(callId+". sorting:"); 
    display(data, left, right); 
    if (left+1 >= right) { 
     System.out.print(" "+saveCallId+". result:"); 
     display(data, left, right); 
     return callId; 
    } 
    int ai = left, bi = (left+right)/2, ci = right-1, pos; 
    int a = data[ai], b = data[bi], c = data[ci]; 
    if (a < b) { 
     if (c < a) { 
     pos = ai; 
     } else if (c < b) { 
     pos = ci; 
     } else { 
     pos = bi; 
     } 
    } else { 
     if (c < b) { 
     pos = bi; 
     } else if (c < a) { 
     pos = ci; 
     } else { 
     pos = ai; 
     } 
    } 
    int pivot = data[pos]; 
    System.out.println(" median of ["+a+", "+b+", "+c+"] is "+pivot); 
    swap(data, right-1, pos); 
    int tail = left; 
    for (int i = left; i != right-1; ++i) { 
     if (data[i] < pivot) { 
     swap(data, tail, i); 
     ++tail; 
     } 
    } 
    swap(data, right-1, tail); 
    callId = quicksort(data, left, tail, ++callId); 
    callId = quicksort(data, tail+1, right, ++callId); 
    System.out.print(" "+saveCallId+". result:"); 
    display(data, left, right); 
    return callId; 
    } 

    public static void main(String[] args) { 
    int[] data = new int[]{ 2, 6, 3, 1, 6, 5, 2, 4, 8 }; 
    new Quicksort().quicksort(data, 0, data.length, 0); 
    } 
} 

Для ввода случае { 2, 6, 3, 1, 6, 5, 2, 4, 8 }, выход:

0. sorting: 2 6 3 1 6 5 2 4 8 
    median of [2, 6, 8] is 6 
1. sorting: 2 3 1 5 2 4 
    median of [2, 5, 4] is 4 
2. sorting: 2 3 1 2 
    median of [2, 1, 2] is 2 
3. sorting: 1 
    3. result: 1 
4. sorting:  2 3 
    median of [2, 3, 3] is 3 
5. sorting:  2 
    5. result:  2 
6. sorting:   
    6. result:   
    4. result:  2 3 
    2. result: 1 2 2 3 
7. sorting:   5 
    7. result:   5 
    1. result: 1 2 2 3 4 5 
8. sorting:    6 8 
    median of [6, 8, 8] is 8 
9. sorting:    6 
    9. result:    6 
10. sorting:     
    10. result:     
    8. result:    6 8 
    0. result: 1 2 2 3 4 5 6 6 8 

Answer 3

Вы можете увидеть интерактивную визуализацию и играть с ним в the walnut. Он использует разбиение Дийкстры (меньшее, равное, большее, чем ось вращения).