Conozca su algoritmo de clasificación | Conjunto 2 (Introsort- Arma clasificadora de C++)

Hemos discutido la clasificación de armas utilizadas por diferentes idiomas en el artículo anterior. En este artículo, se analiza el arma de clasificación de C++, Introsort. ¿Qué es Introsort? 

En pocas palabras, es el mejor algoritmo de clasificación que existe. Es un algoritmo de clasificación híbrido, lo que significa que utiliza más de un algoritmo de clasificación como rutina. 

Qué algoritmos de clasificación estándar se utilizan en Introsort 

Introsort, que es un algoritmo de clasificación híbrido, utiliza tres algoritmos de clasificación para minimizar el tiempo de ejecución, Quicksort , Heapsort y Insertion Sort . 

¿Como funciona? 

Introsort comienza con quicksort y si la profundidad de recursión va más allá de un límite particular, cambia a Heapsort para evitar la complejidad de tiempo O(N ^{2 ) del peor caso de Quicksort.} También utiliza la ordenación por inserción cuando el número de elementos a ordenar es bastante menor. Así que primero crea una partición. Tres casos surgen de aquí.

1. Si el tamaño de la partición es tal que existe la posibilidad de superar el límite máximo de profundidad, entonces Introsort cambia a Heapsort. Definimos el límite de profundidad máxima como 2*log(N)
2. Si el tamaño de la partición es demasiado pequeño, la ordenación rápida decae a la ordenación por inserción. Definimos este límite como 16 (debido a la investigación). Entonces, si el tamaño de la partición es inferior a 16, haremos una ordenación por inserción.
3. Si el tamaño de la partición está por debajo del límite y no es demasiado pequeño (es decir, entre 16 y 2*log(N)), realiza una clasificación rápida simple.

¿Por qué es mejor que el simple Quicksort o por qué la necesidad de Introsort? 

^{Dado que Quicksort puede tener una complejidad de tiempo O(N 2} ) en el peor de los casos y también aumenta el espacio de la pila de recursividad (O(log N) si se aplica la recursión de cola), por lo que para evitar todo esto, debemos cambiar el algoritmo de Quicksort a otro si hay posibilidad de peor caso. Así que Introsort resuelve este problema cambiando a Heapsort. Además, debido a un factor constante más grande, la clasificación rápida puede funcionar incluso peor que el algoritmo de clasificación O(N2) cuando N es lo suficientemente pequeño. Por lo tanto, cambia a ordenación por inserción para disminuir el tiempo de ejecución de la ordenación. Además, si se realiza una mala selección de pivote, la ordenación rápida no funciona mejor que la ordenación de burbujas. 

¿Por qué se utiliza la clasificación por inserción (y no la clasificación por burbuja, etc.)?

 La ordenación por inserción ofrece las siguientes ventajas.

1. Es un hecho conocido y establecido que la ordenación por inserción es el algoritmo de ordenación basado en comparación más óptimo para arreglos pequeños.
2. Tiene una buena localidad de referencia.
3. Es un algoritmo de clasificación adaptable, es decir, supera a todos los demás algoritmos si los elementos de la array se clasifican parcialmente.

¿Por qué se usa Heapsort (y no Mergesort, etc.)? 

Esto se debe únicamente a los requisitos de memoria. Merge sort requiere espacio O(N), mientras que Heapsort es un algoritmo de espacio O(1) in situ. 

¿Por qué no se usa Heapsort en lugar de Quicksort cuando el tamaño de la partición está por debajo del límite? 

Esta pregunta es la misma que la de por qué Quicksort generalmente supera a Heapsort. La respuesta es, aunque Heapsort también es O (N log N) en promedio, así como en el peor de los casos y también en el espacio O (1), todavía no lo usamos cuando el tamaño de la partición está por debajo del límite porque el factor constante extra oculto en Heapsort es bastante mayor que el de Quicksort. 

¿Por qué el corte es 16 para cambiar de ordenación rápida a ordenación por inserción y 2*logN para cambiar de ordenación rápida a ordenación en montón? 

Estos valores se eligen empíricamente como una aproximación debido a varias pruebas e investigaciones realizadas. 

/* A Program to sort the array using Introsort.
  The most popular C++ STL Algorithm- sort()
  uses Introsort. */
 
#include<bits/stdc++.h>
using namespace std;
 
// A utility function to swap the values pointed by
// the two pointers
void swapValue(int *a, int *b)
{
    int *temp = a;
    a = b;
    b = temp;
    return;
}
 
/* Function to sort an array using insertion sort*/
void InsertionSort(int arr[], int *begin, int *end)
{
    // Get the left and the right index of the subarray
    // to be sorted
    int left = begin - arr;
    int right = end - arr;
 
    for (int i = left+1; i <= right; i++)
    {
        int key = arr[i];
        int j = i-1;
 
       /* Move elements of arr[0..i-1], that are
          greater than key, to one position ahead
          of their current position */
        while (j >= left && arr[j] > key)
        {
            arr[j+1] = arr[j];
            j = j-1;
        }
        arr[j+1] = key;
   }
 
   return;
}
 
// A function to partition the array and return
// the partition point
int* Partition(int arr[], int low, int high)
{
    int pivot = arr[high];    // pivot
    int i = (low - 1);  // Index of smaller element
 
    for (int j = low; j <= high- 1; j++)
    {
        // If current element is smaller than or
        // equal to pivot
        if (arr[j] <= pivot)
        {
            // increment index of smaller element
            i++;
 
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return (arr + i + 1);
}
 
 
// A function that find the middle of the
// values pointed by the pointers a, b, c
// and return that pointer
int *MedianOfThree(int * a, int * b, int * c)
{
    if (*a < *b && *b < *c)
        return (b);
 
    if (*a < *c && *c <= *b)
        return (c);
 
    if (*b <= *a && *a < *c)
        return (a);
 
    if (*b < *c && *c <= *a)
        return (c);
 
    if (*c <= *a && *a < *b)
        return (a);
 
    if (*c <= *b && *b <= *a)
        return (b);
}
 
// A Utility function to perform intro sort
void IntrosortUtil(int arr[], int * begin,
                  int * end, int depthLimit)
{
    // Count the number of elements
    int size = end - begin;
 
      // If partition size is low then do insertion sort
    if (size < 16)
    {
        InsertionSort(arr, begin, end);
        return;
    }
 
    // If the depth is zero use heapsort
    if (depthLimit == 0)
    {
        make_heap(begin, end+1);
        sort_heap(begin, end+1);
        return;
    }
 
    // Else use a median-of-three concept to
    // find a good pivot
    int * pivot = MedianOfThree(begin, begin+size/2, end);
 
    // Swap the values pointed by the two pointers
    swapValue(pivot, end);
 
   // Perform Quick Sort
    int * partitionPoint = Partition(arr, begin-arr, end-arr);
    IntrosortUtil(arr, begin, partitionPoint-1, depthLimit - 1);
    IntrosortUtil(arr, partitionPoint + 1, end, depthLimit - 1);
 
    return;
}
 
/* Implementation of introsort*/
void Introsort(int arr[], int *begin, int *end)
{
    int depthLimit = 2 * log(end-begin);
 
    // Perform a recursive Introsort
    IntrosortUtil(arr, begin, end, depthLimit);
 
      return;
}
 
// A utility function to print an array of size n
void printArray(int arr[], int n)
{
   for (int i=0; i < n; i++)
       printf("%d ", arr[i]);
   printf("\n");
}
 
// Driver program to test Introsort
int main()
{
    int arr[] = {3, 1, 23, -9, 233, 23, -313, 32, -9};
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Pass the array, the pointer to the first element and
    // the pointer to the last element
    Introsort(arr, arr, arr+n-1);
    printArray(arr, n);
 
    return(0);
}

-313 -9 -9 1 3 23 23 32 233

¿Es estable Introsort? 

Dado que Quicksort tampoco es estable, Introsort tampoco es estable. 

Complejidad de tiempo Mejor caso: O (N log N) Caso promedio: O (N log N) Peor caso: O (N log N) donde, N = número de elementos que se ordenarán. Espacio auxiliar Al igual que la ordenación rápida, puede usar el espacio de pila de recursión auxiliar O (log N). Conozca su algoritmo de clasificación | Conjunto 2 (Introsort- Arma clasificadora de C++) 

Referencias https://en.wikipedia.org/wiki/Introsort 

Este artículo es una contribución de Rachit Belwariar . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.