IntroSort

IntroSort es un algoritmo hibrido (Inserción – Quicksort – Heapsort) de ordenación con comparación pero no estable. Fue desarrollado por David R. Musser en 1.997.

 

Rendimiento – Complejidad
Mejor caso Ω	Peor caso O	Media Θ	Espacio
¿>? (n)	(n log n)	(n log n)	(n log n)

 

Introsort se articula en función del conjunto de datos.

1. Si el número de elementos en la entrada es pequeño, utiliza el método de inserción.
2. Utiliza Quicksort en función de la profundidad ( Math.log(Vector.length))/2) que nos indica el nivel de recursividad.
3. Se utiliza Heapsort cuando el nivel de profundidad en la 2ª opción no es el conveniente.

 

Implementación en lenguaje Java.

//ordenaintrasort(Vector, 0, Vector.length, profundidad); profundidad = ((int) Math.log(Vector.length))/2;
  private static int[] ordenaintrosort(int[] Vector, int menor, int mayor, int profundidad) {
    if (Vector.length > 100)
      while (mayor - menor > umbraldecorte) {
        if (profundidad != 0) {
          profundidad = profundidad - 1;
          int eje = Vector[(menor + mayor) / 2];
          int posicion = quickDivide(Vector, menor, mayor, eje);
          ordenaintrosort(Vector, posicion, mayor, profundidad);
          mayor = posicion;
        } else {
          heapsort(Vector, menor, mayor);
          return Vector;
        }
      }
    else
      insercion(Vector, menor, mayor);
    return Vector;
  }

    private static int quickDivide(int[] Vector, int menor, int mayor, int eje) {
      mayor--;
      while (menor <= mayor) {
        while (Vector[menor] < eje) {menor++;}
        while (Vector[mayor] > eje) {mayor--;}
        if (menor <= mayor) {
          int intercambio = Vector[menor];
          Vector[menor] = Vector[mayor];
          Vector[mayor] = intercambio;
          menor++;
          mayor--;
        }
      }
      return menor;
    }

    private static void heapsort(int[] Vector, int menor, int mayor) {
      int pmedio = mayor-menor;
      for (int i = pmedio / 2; i >= 1; i = i - 1) {
        desciende(Vector, i, pmedio, menor);
      }
      for (int i = pmedio; i > 1; i = i - 1) {
        int intercambio = Vector[menor];
        Vector[menor] = Vector[menor + i - 1];
        Vector[menor + i - 1] = intercambio;
        desciende(Vector, 1, i - 1, menor);
      }
    }
        
    private static void desciende(int[] Vector, int i, int pmedio, int menor) {
      int temp = Vector[menor + i - 1];
      int hijo;
      while (i <= pmedio / 2) {
        hijo = i * 2;
        if (hijo < pmedio && Vector[menor + hijo - 1] < Vector[menor + hijo]) {
          hijo++;
        }
        if (temp >= Vector[menor + hijo - 1])	break;
        Vector[menor + i - 1] = Vector[menor + hijo - 1];
        i = hijo;
      }
      Vector[menor + i - 1] = temp;
    }

Rendimiento.

Estadística individual realizada con el mismo equipo y condiciones del resumen de estadísticas de ordenación.