superioridad sobre la ordenación rápida pila de clasificación

Question

pila de clasificación tiene un peor caso de complejidad O(nlogn) mientras ordenación rápida ha O(n^2). Pero las evidencias dicen Empírico adentrándonos ordenación rápida es superior. ¿Por qué?

Answer 1

Uno de los factores principales es que tiene una mejor clasificación rápida localidad de referencia - el siguiente paso para acceder es por lo general cerca de la memoria a la que solo se considera. Por el contrario, heapsort salta significativamente más. Puesto que las cosas que están muy juntos es probable que se almacenan en caché en conjunto, la clasificación rápida tiende a ser más rápido.

Sin embargo, peor de los casos de ordenación rápida el rendimiento es significativamente peor que heapsort de decir. Debido a que algunas aplicaciones críticas requerirán garantías de rendimiento de velocidad, heapsort es el camino correcto a seguir para estos casos.

Answer 2

heapsort es O (N log N) guaranted, lo que es mucho mejor que el peor caso en Quicksort. Heapsort no necesita más memoria para otra matriz para poner datos ordenados como sea necesario mediante la ordenación por fusión. Entonces, por qué las aplicaciones comerciales se pega con la ordenación rápida? Lo que tiene la ordenación rápida que es tan especial sobre los demás implementaciones?

He probado los algoritmos de mí mismo y he visto que la ordenación rápida tiene algo especial. Se ejecuta algoritmos rápidos, mucho más rápido que Heap y Combinar.

El secreto de ordenación rápida es: Casi no hace permutas de elementos innecesarios. Swap es mucho tiempo.

Con heapsort, incluso si todos los datos ya están ordenados, que se van a intercambiar el 100% de los elementos para ordenar la matriz.

Con la ordenación por fusión, es aún peor. Usted va a escribir el 100% de los elementos de otra matriz y escribir de nuevo en el original, incluso si los datos ya están ordenados.

Con la ordenación rápida que no intercambia lo que ya se ordenó. Si los datos se ordenó por completo, se intercambian casi nada! Aunque hay una gran cantidad de quejarse sobre el peor de los casos, una pequeña mejora en la elección del pivote, cualquier otro que conseguir el primer o el último elemento de la matriz, puede evitarlo. Si obtiene un pivote del elemento intermedio entre el primero, último y media del elemento, es suficiente parar para evitar la peor de los casos.

Lo que es superior en la ordenación rápida no es el peor de los casos, pero el mejor de los casos! En mejor de los casos lo hace el mismo número de comparaciones, ok, pero se intercambian casi nada. En caso promedio se intercambia parte de los elementos, pero no todos los elementos, como en heapsort y ordenación por fusión. Eso es lo que da la ordenación rápida el mejor momento. Menos de intercambio, más velocidad.

La aplicación a continuación en C # en mi equipo, que se ejecuta en modo de lanzamiento, latidos Array.Sort por 3 segundos con pivote central y de 2 segundos con una mejor pivote (sí, hay una sobrecarga de conseguir un buen pivote).

static void Main(string[] args)
{
    int[] arrToSort = new int[100000000];
    var r = new Random();
    for (int i = 0; i < arrToSort.Length; i++) arrToSort[i] = r.Next(1, arrToSort.Length);

    Console.WriteLine("Press q to quick sort, s to Array.Sort");
    while (true)
    {
        var k = Console.ReadKey(true);
        if (k.KeyChar == 'q')
        {
            // quick sort
            Console.WriteLine("Beg quick sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff"));
            QuickSort(arrToSort, 0, arrToSort.Length - 1);
            Console.WriteLine("End quick sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff"));
            for (int i = 0; i < arrToSort.Length; i++) arrToSort[i] = r.Next(1, arrToSort.Length);
        }
        else if (k.KeyChar == 's')
        {
            Console.WriteLine("Beg Array.Sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff"));
            Array.Sort(arrToSort);
            Console.WriteLine("End Array.Sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff"));
            for (int i = 0; i < arrToSort.Length; i++) arrToSort[i] = r.Next(1, arrToSort.Length);
        }
    }
}

static public void QuickSort(int[] arr, int left, int right)
{
    int begin = left
        , end = right
        , pivot
        // get middle element pivot
        //= arr[(left + right) / 2]
        ;

    //improved pivot
    int middle = (left + right) / 2;
    int
        LM = arr[left].CompareTo(arr[middle])
        , MR = arr[middle].CompareTo(arr[right])
        , LR = arr[left].CompareTo(arr[right])
        ;
    if (-1 * LM == LR)
        pivot = arr[left];
    else
        if (MR == -1 * LR)
            pivot = arr[right];
        else
            pivot = arr[middle];
    do
    {
        while (arr[left] < pivot) left++;
        while (arr[right] > pivot) right--;

        if(left <= right)
        {
            int temp = arr[right];
            arr[right] = arr[left];
            arr[left] = temp;

            left++;
            right--;
        }
    } while (left <= right);

    if (left < end) QuickSort(arr, left, end);
    if (begin < right) QuickSort(arr, begin, right);
}

Answer 3

Aquí está un par de explicaciones:

http://www.cs.auckland.ac.nz/ software / AlgAnim / qsort3.html

http://users.aims.ac.za/~mackay/ Clasificación / sorting.html

En esencia, a pesar de que el peor de los casos para la ordenación rápida es O (n ^ 2) que en promedio se obtienen mejores resultados. : -)

Answer 4

La notación grande-O significa que el tiempo necesario para ordenar n artículos está acotado superiormente por la c*n*log(n) función, donde c es algún factor constante no especificado. No hay ninguna razón por qué el c constante debe ser el mismo para quicksort y heapsort. Así que la pregunta real es: ¿por qué se espera que sean igual de rápido

Quicksort siempre ha sido un poco más rápido que heapsort en la práctica, pero la diferencia se ha vuelto mayor recientemente, ya que, como se mencionó antes, localidad de acceso a la memoria se ha vuelto tan importante para la velocidad de ejecución.

Answer 5

complejidad media de los casos, y el hecho de que se pueden tomar medidas sencillas para minimizar el riesgo de peor caso de complejidad en la ordenación rápida (por ejemplo, seleccione el pivote como una mediana de tres elementos en lugar de una sola posición seleccionada).