IntroSort o clasificación introspectiva

Introsort (clasificación introspectiva) es una clasificación basada en comparación que consta de tres fases de clasificación. Son Quicksort, Heapsort y ordenación por inserción. Los conceptos básicos de Introsort y el código C++ están disponibles aquí.
La siguiente sección muestra cómo se formula el algoritmo de Introsort, después de revisar los pros y los contras de los respectivos algoritmos. 

1. Quicksort 
   El Quicksort es un algoritmo de clasificación eficiente, pero tiene el peor rendimiento de las comparaciones O(N ^ 2) con el espacio auxiliar O(N). Esta complejidad en el peor de los casos depende de dos fases del algoritmo Quicksort. 
   1. Elegir el elemento pivote 
   2. Profundidad de recurrencia durante el curso del algoritmo
2. Heapsort 
   Heapsort tiene una complejidad de tiempo en el peor de los casos O(N log N), que es mucho mejor que el peor de los casos de Quicksort. Entonces, ¿es evidente que Heapsort es el mejor? No, el secreto de Quicksort es que no intercambia elementos que ya están en orden, lo cual es innecesario, mientras que con Heapsort, incluso si todos los datos ya están ordenados, el algoritmo intercambia todos los elementos para ordenar la array. . Además, al elegir el pivote óptimo, se puede evitar el peor de los casos de O(N ^ 2) en la ordenación rápida. Pero, el intercambio pagará más tiempo en el caso de Heapsort que es inevitable. Por lo tanto, Quicksort supera a Heapsort.
   Lo mejor de Heapsort es que, si la profundidad de recursión se vuelve demasiado grande como (log N), la complejidad del peor de los casos seguiría siendo O (N log N).
3.  Mergesort 
   Mergesort tiene la complejidad del peor de los casos solo como O(N log N). Mergesort puede funcionar bien en cualquier tipo de conjuntos de datos, independientemente de su tamaño, mientras que Quicksort no puede funcionar bien con grandes conjuntos de datos. Pero Mergesort no está en el lugar mientras que Quicksort está en el lugar, y eso juega un papel vital aquí. Mergesort va bien con LinkedLists mientras que Quicksort va bien con arreglos. La localidad de referencia es mejor con Quicksort, mientras que con Mergesort es mala. Por lo tanto, para fines convencionales, teniendo en cuenta las limitaciones de memoria, Quicksort supera a Mergesort.
4.  Clasificación por inserción 
   La principal ventaja de la clasificación por inserción es su simplicidad. También exhibe un buen desempeño cuando se trata de una lista pequeña. La clasificación por inserción es un algoritmo de clasificación en el lugar, por lo que el requisito de espacio es mínimo. La desventaja de la ordenación por inserción es que no funciona tan bien como los otros algoritmos de ordenación cuando el tamaño de los datos aumenta.
    

Así es como se formula Introsort: 
La elección del algoritmo de clasificación correcto depende de la ocasión en la que se utilice el algoritmo de clasificación. Ya hay una buena cantidad de algoritmos de clasificación disponibles que tienen sus propios pros y contras. Entonces, para obtener un mejor algoritmo de clasificación, la solución es modificar los algoritmos existentes y producir un nuevo algoritmo de clasificación que funcione mejor. Hay muchos algoritmos híbridos que superan a los algoritmos generales de clasificación. Uno de ellos es el Introsort. Las mejores versiones de Quicksort son competitivas con la ordenación en montón y la ordenación combinada en la gran mayoría de las entradas. Rara vez Quicksort tiene el peor caso de tiempo de ejecución O(N ^ 2) y uso de pila O(N). Tanto Heapsort como Mergesort tienen un tiempo de ejecución en el peor de los casos O(N log N), junto con un uso de pila de O(1) para Heapsort y O(log N) para Mergesort respectivamente. También,
Combinando todas las ventajas de los algoritmos de clasificación, Introsort se comporta en función del conjunto de datos. 

1. Si el número de elementos en la entrada es menor, Introsort realiza la ordenación por inserción para la entrada.
2. Teniendo en cuenta el menor número de comparaciones (Quicksort), para dividir la array encontrando el elemento pivote, se utiliza Quicksort. Citado anteriormente, el peor caso de Quicksort se basa en las dos fases y así es como podemos solucionarlo.
   1. Elegir el elemento pivote: podemos usar el concepto de mediana de 3 o el concepto pivote aleatorio o el medio como concepto pivote para encontrar el elemento pivote
   2. Profundidad de recursión durante el curso del algoritmo: cuando la profundidad de recursión aumenta, Introsort usa Heapsort ya que tiene el límite superior definido de O (N log N).

¿Cómo funciona el límite de profundidad? 
depthLimit representa la profundidad máxima para la recursividad. Por lo general, se elige como registro de la longitud de la array de entrada (consulte la implementación a continuación). La idea es garantizar que la complejidad de tiempo del peor de los casos permanezca en O (N log N). Tenga en cuenta que la complejidad de tiempo en el peor de los casos de HeapSort es O (N log N).

¿Por qué no se usa Mergesort? 
Dado que las arrays se tratan con el concepto in situ en el que Quicksort supera a Mergesort, no utilizamos Mergesort.

¿Se puede aplicar Introsort en todas partes?  

1. Si los datos no caben en una array, no se puede usar Introsort.
2. Además, al igual que Quicksort y Heapsort, Introsort no es estable. Cuando se necesita una ordenación estable, no se puede aplicar Introsort.

¿Es Introsort el único algoritmo de clasificación híbrido?  
No. Hay otros algoritmos de clasificación híbridos como Hybrid Mergesort, Tim sort, Insertion-Merge hybrid.
Comparación de Heapsort, ordenación por inserción, Quicksort, Introsort al ordenar 6000 elementos (en milisegundos). 
 

Pseudocódigo: 

sort(A : array):
    depthLimit = 2xfloor(log(length(A)))
    introsort(A, depthLimit)

introsort(A, depthLimit):
    n = length(A)
    if n<=16:
        insertionSort(A)
    if depthLimit == 0:
        heapsort(A)
    else:

        // using quick sort, the
        // partition point is found 
        p = partition(A)  
        introsort(A[0:p-1], depthLimit - 1)
        introsort(A[p+1:n], depthLimit - 1)

Complejidad de tiempo: 
Desempeño en el peor de los casos: O(nlogn) (mejor que Quicksort) 
Desempeño en el caso promedio: O(nlogn)
En la fase de Quicksort, el pivote puede elegirse usando el concepto de mediana de 3 o el último elemento del formación. Para los datos que tienen una gran cantidad de elementos, el concepto de mediana de 3 ralentiza el tiempo de ejecución de Quicksort.
En el ejemplo que se describe a continuación, el algoritmo de clasificación rápida calcula el elemento pivote según el concepto de mediana de 3. 

Ejemplo:

// C++ implementation of Introsort algorithm
 
#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 ot print an array of size n
void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " \n"[i + 1 == n];
}
 
// Driver program to test Introsort
int main()
{
    int arr[] = { 2,  10, 24, 2,  10, 11, 27, 4,  2,  4,
                  28, 16, 9,  8,  28, 10, 13, 24, 22, 28,
                  0,  13, 27, 13, 3,  23, 18, 22, 8,  8 };
    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);
}

// Java implementation of Introsort algorithm
 
import java.io.IOException;
 
public class Introsort {
 
    // the actual data that has to be sorted
    private int a[];
 
    // the number of elements in the data
    private int n;
 
    // Constructor to initialize the size
    // of the data
    Introsort(int n)
    {
        a = new int[n];
        this.n = 0;
    }
 
    // The utility function to insert the data
    private void dataAppend(int temp)
    {
        a[n] = temp;
        n++;
    }
 
    // The utility function to swap two elements
    private void swap(int i, int j)
    {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
 
    // To maxHeap a subtree rooted with node i which is
    // an index in a[]. heapN is size of heap
    private void maxHeap(int i, int heapN, int begin)
    {
        int temp = a[begin + i - 1];
        int child;
 
        while (i <= heapN / 2) {
            child = 2 * i;
 
            if (child < heapN
                && a[begin + child - 1] < a[begin + child])
                child++;
 
            if (temp >= a[begin + child - 1])
                break;
 
            a[begin + i - 1] = a[begin + child - 1];
            i = child;
        }
        a[begin + i - 1] = temp;
    }
 
    // Function to build the heap (rearranging the array)
    private void heapify(int begin, int end, int heapN)
    {
        for (int i = (heapN) / 2; i >= 1; i--)
            maxHeap(i, heapN, begin);
    }
 
    // main function to do heapsort
    private void heapSort(int begin, int end)
    {
        int heapN = end - begin;
 
        // Build heap (rearrange array)
        this.heapify(begin, end, heapN);
 
        // One by one extract an element from heap
        for (int i = heapN; i >= 1; i--) {
 
            // Move current root to end
            swap(begin, begin + i);
 
            // call maxHeap() on the reduced heap
            maxHeap(1, i, begin);
        }
    }
 
    // function that implements insertion sort
    private void insertionSort(int left, int right)
    {
 
        for (int i = left; i <= right; i++) {
            int key = a[i];
            int j = i;
 
            // Move elements of arr[0..i-1], that are
            // greater than the key, to one position ahead
            // of their current position
            while (j > left && a[j - 1] > key) {
                a[j] = a[j - 1];
                j--;
            }
            a[j] = key;
        }
    }
 
    // Function for finding the median of the three elements
    private int findPivot(int a1, int b1, int c1)
    {
        int max = Math.max(Math.max(a[a1], a[b1]), a[c1]);
        int min = Math.min(Math.min(a[a1], a[b1]), a[c1]);
        int median = max ^ min ^ a[a1] ^ a[b1] ^ a[c1];
        if (median == a[a1])
            return a1;
        if (median == a[b1])
            return b1;
        return c1;
    }
 
    // This function takes the last element as pivot, places
    // the pivot element at its correct position in sorted
    // array, and places all smaller (smaller than pivot)
    // to the left of the pivot
    // and greater elements to the right of the pivot
    private int partition(int low, int high)
    {
 
        // pivot
        int pivot = a[high];
 
        // Index of smaller element
        int i = (low - 1);
        for (int j = low; j <= high - 1; j++) {
 
            // If the current element is smaller
            // than or equal to the pivot
            if (a[j] <= pivot) {
 
                // increment index of smaller element
                i++;
                swap(i, j);
            }
        }
        swap(i + 1, high);
        return (i + 1);
    }
 
    // The main function that implements Introsort
    // low  --> Starting index,
    // high  --> Ending index,
    // depthLimit  --> recursion level
    private void sortDataUtil(int begin, int end, int depthLimit)
    {
        if (end - begin > 16) {
            if (depthLimit == 0) {
 
                // if the recursion limit is
                // occurred call heap sort
                this.heapSort(begin, end);
                return;
            }
 
            depthLimit = depthLimit - 1;
            int pivot = findPivot(begin,
                begin + ((end - begin) / 2) + 1,
                                           end);
            swap(pivot, end);
 
            // p is partitioning index,
            // arr[p] is now at right place
            int p = partition(begin, end);
 
            // Separately sort elements before
            // partition and after partition
            sortDataUtil(begin, p - 1, depthLimit);
            sortDataUtil(p + 1, end, depthLimit);
        }
 
        else {
            // if the data set is small,
            // call insertion sort
            insertionSort(begin, end);
        }
    }
 
    // A utility function to begin the
    // Introsort module
    private void sortData()
    {
 
        // Initialise the depthLimit
        // as 2*log(length(data))
        int depthLimit
            = (int)(2 * Math.floor(Math.log(n) /
                                  Math.log(2)));
 
        this.sortDataUtil(0, n - 1, depthLimit);
    }
 
    // A utility function to print the array data
    private void printData()
    {
        for (int i = 0; i < n; i++)
            System.out.print(a[i] + " ");
    }
 
    // Driver code
    public static void main(String args[]) throws IOException
    {
        int[] inp = { 2, 10, 24, 2, 10, 11, 27,
                      4, 2, 4, 28, 16, 9, 8,
                      28, 10, 13, 24, 22, 28,
                      0, 13, 27, 13, 3, 23,
                      18, 22, 8, 8 };
 
        int n = inp.length;
        Introsort introsort = new Introsort(n);
 
        for (int i = 0; i < n; i++) {
            introsort.dataAppend(inp[i]);
        }
 
        introsort.sortData();
        introsort.printData();
    }
}

# Python implementation of Introsort algorithm
 
import math
import sys
from heapq import heappush, heappop
 
arr = []
 
 
# The main function to sort
# an array of the given size
# using heapsort algorithm
 
def heapsort():
    global arr
    h = []
 
    # building the heap
 
    for value in arr:
        heappush(h, value)
    arr = []
 
    # extracting the sorted elements one by one
 
    arr = arr + [heappop(h) for i in range(len(h))]
 
 
# The main function to sort the data using
# insertion sort algorithm
 
def InsertionSort(begin, end):
    left = begin
    right = end
 
    # Traverse through 1 to len(arr)
 
    for i in range(left + 1, right + 1):
        key = arr[i]
 
        # Move elements of arr[0..i-1], that are
        # greater than key, to one position ahead
        # of their current position
 
        j = i - 1
        while j >= left and arr[j] > key:
            arr[j + 1] = arr[j]
            j = j - 1
        arr[j + 1] = key
 
 
# This function takes last element as pivot, places
# the pivot element at its correct position in sorted
# array, and places all smaller (smaller than pivot)
# to left of pivot and all greater elements to right
# of pivot
 
def Partition(low, high):
    global arr
 
  # pivot
 
    pivot = arr[high]
 
  # index of smaller element
 
    i = low - 1
 
    for j in range(low, high):
 
        # If the current element is smaller than or
        # equal to the pivot
 
        if arr[j] <= pivot:
 
            # increment index of smaller element
 
            i = i + 1
            (arr[i], arr[j]) = (arr[j], arr[i])
    (arr[i + 1], arr[high]) = (arr[high], arr[i + 1])
    return i + 1
 
 
# The function to find the median
# of the three elements in
# in the index a, b, d
 
def MedianOfThree(a, b, d):
    global arr
    A = arr[a]
    B = arr[b]
    C = arr[d]
 
    if A <= B and B <= C:
        return b
    if C <= B and B <= A:
        return b
    if B <= A and A <= C:
        return a
    if C <= A and A <= B:
        return a
    if B <= C and C <= A:
        return d
    if A <= C and C <= B:
        return d
 
 
# The main function that implements Introsort
# low  --> Starting index,
# high  --> Ending index
# depthLimit --> recursion level
 
def IntrosortUtil(begin, end, depthLimit):
    global arr
    size = end - begin
    if size < 16:
 
        # if the data set is small, call insertion sort
 
        InsertionSort(begin, end)
        return
 
    if depthLimit == 0:
 
        # if the recursion limit is occurred call heap sort
 
        heapsort()
        return
 
    pivot = MedianOfThree(begin, begin + size // 2, end)
    (arr[pivot], arr[end]) = (arr[end], arr[pivot])
 
    # partitionPoint is partitioning index,
    # arr[partitionPoint] is now at right place
 
    partitionPoint = Partition(begin, end)
 
    # Separately sort elements before partition and after partition
 
    IntrosortUtil(begin, partitionPoint - 1, depthLimit - 1)
    IntrosortUtil(partitionPoint + 1, end, depthLimit - 1)
 
 
# A utility function to begin the Introsort module
 
def Introsort(begin, end):
 
    # initialise the depthLimit as 2 * log(length(data))
 
    depthLimit = 2 * math.floor(math.log2(end - begin))
    IntrosortUtil(begin, end, depthLimit)
 
 
# A utility function to print the array data
 
def printArr():
    print ('Arr: ', arr)
 
 
def main():
    global arr
    arr = arr + [
        2, 10, 24, 2, 10, 11, 27,
        4, 2, 4, 28, 16, 9, 8,
        28, 10, 13, 24, 22, 28,
        0, 13, 27, 13, 3, 23,
        18, 22, 8, 8 ]
         
    n = len(arr)
 
    Introsort(0, n - 1)
    printArr()
 
 
if __name__ == '__main__':
    main()

// C# implementation of
// Introsort algorithm
using System;
class Introsort{
 
// the actual data that
// has to be sorted
public int []a;
 
// the number of elements
// in the data
public int n;
 
// Constructor to initialize
// the size of the data
Introsort(int n)
{
  a = new int[n];
  this.n = 0;
}
 
// The utility function to
// insert the data
private void dataAppend(int temp)
{
  a[n] = temp;
  n++;
}
 
// The utility function to
// swap two elements
private void swap(int i,
                  int j)
{
  int temp = a[i];
  a[i] = a[j];
  a[j] = temp;
}
 
// To maxHeap a subtree rooted
// with node i which is an index
// in []a. heapN is size of heap
private void maxHeap(int i,
                     int heapN,
                     int begin)
{
  int temp = a[begin + i - 1];
  int child;
 
  while (i <= heapN / 2)
  {
    child = 2 * i;
 
    if (child < heapN &&
        a[begin + child - 1] <
        a[begin + child])
      child++;
 
    if (temp >=
        a[begin + child - 1])
      break;
 
    a[begin + i - 1] = a[begin + child - 1];
    i = child;
  }
  a[begin + i - 1] = temp;
}
 
// Function to build the
// heap (rearranging the array)
private void heapify(int begin,
                     int end,
                     int heapN)
{
  for (int i = (heapN) / 2;
           i >= 1; i--)
    maxHeap(i, heapN, begin);
}
 
// main function to do heapsort
private void heapSort(int begin,
                      int end)
{
  int heapN = end - begin;
 
  // Build heap (rearrange array)
  this.heapify(begin, end, heapN);
 
  // One by one extract an element
  // from heap
  for (int i = heapN; i >= 1; i--)
  {
    // Move current root to end
    swap(begin, begin + i);
 
    // call maxHeap() on the
    // reduced heap
    maxHeap(1, i, begin);
  }
}
 
// function that implements
// insertion sort
private void insertionSort(int left,
                           int right)
{
  for (int i = left; i <= right; i++)
  {
    int key = a[i];
    int j = i;
 
    // Move elements of arr[0..i-1],
    // that are greater than the key,
    // to one position ahead
    // of their current position
    while (j > left && a[j - 1] > key)
    {
      a[j] = a[j - 1];
      j--;
    }
    a[j] = key;
  }
}
 
// Function for finding the median
// of the three elements
private int findPivot(int a1,
                      int b1, int c1)
{
  int max = Math.Max(
            Math.Max(a[a1],
                     a[b1]), a[c1]);
  int min = Math.Min(
            Math.Min(a[a1],
                     a[b1]), a[c1]);
  int median = max ^ min ^
               a[a1] ^ a[b1] ^ a[c1];
  if (median == a[a1])
    return a1;
  if (median == a[b1])
    return b1;
  return c1;
}
 
// This function takes the last element
// as pivot, places the pivot element at
// its correct position in sorted
// array, and places all smaller
// (smaller than pivot) to the left of
// the pivot and greater elements to
// the right of the pivot
private int partition(int low,
                      int high)
{
  // pivot
  int pivot = a[high];
 
  // Index of smaller element
  int i = (low - 1);
   
  for (int j = low;
           j <= high - 1; j++)
  {
    // If the current element
    // is smaller than or equal
    // to the pivot
    if (a[j] <= pivot)
    {
      // increment index of
      // smaller element
      i++;
      swap(i, j);
    }
  }
  swap(i + 1, high);
  return (i + 1);
}
 
// The main function that implements
// Introsort low  --> Starting index,
// high  --> Ending index, depthLimit
// --> recursion level
private void sortDataUtil(int begin,
                          int end,
                          int depthLimit)
{
  if (end - begin > 16)
  {
    if (depthLimit == 0)
    {
      // if the recursion limit is
      // occurred call heap sort
      this.heapSort(begin, end);
      return;
    }
 
    depthLimit = depthLimit - 1;
    int pivot = findPivot(begin, begin +
                         ((end - begin) /
                           2) + 1, end);
    swap(pivot, end);
 
    // p is partitioning index,
    // arr[p] is now at right place
    int p = partition(begin, end);
 
    // Separately sort elements
    // before partition and after
    // partition
    sortDataUtil(begin, p - 1,
                 depthLimit);
    sortDataUtil(p + 1, end,
                 depthLimit);
  }
 
  else
  {
    // if the data set is small,
    // call insertion sort
    insertionSort(begin, end);
  }
}
 
// A utility function to begin
// the Introsort module
private void sortData()
{
  // Initialise the depthLimit
  // as 2*log(length(data))
  int depthLimit = (int)(2 * Math.Floor(
                             Math.Log(n) /
                             Math.Log(2)));
 
  this.sortDataUtil(0, n - 1, depthLimit);
}
 
// A utility function to print
// the array data
private void printData()
{
  for (int i = 0; i < n; i++)
    Console.Write(a[i] + " ");
}
 
// Driver code
public static void Main(String []args)
{
  int[] inp = {2, 10, 24, 2, 10, 11, 27,
               4, 2, 4, 28, 16, 9, 8,
               28, 10, 13, 24, 22, 28,
               0, 13, 27, 13, 3, 23,
               18, 22, 8, 8};
 
  int n = inp.Length;
  Introsort introsort = new Introsort(n);
 
  for (int i = 0; i < n; i++)
  {
    introsort.dataAppend(inp[i]);
  }
 
  introsort.sortData();
  introsort.printData();
}
}
 
// This code is contributed by Rajput-Ji

0 2 2 2 3 4 4 8 8 8 9 10 10 10 11 13 13 13 16 18 22 22 23 24 24 27 27 28 28 28