Clasificación de hebras

Strand sort es un algoritmo de clasificación recursivo que clasifica los elementos de una lista en orden creciente. Tiene la peor complejidad temporal O(n²) que se produce cuando la lista de entrada se ordena de forma inversa. Tiene una complejidad de tiempo en el mejor de los casos de O (n) que ocurre cuando la entrada es una lista que ya está ordenada.

Dada una lista de elementos, ordenarlos en orden creciente. 

Ejemplos:

Entrada: ip[] = {10, 5, 30, 40, 2, 4, 9}
Salida: op[] = {2, 4, 5, 9, 10, 30, 40}

Entrada: ip[] = {1, 10, 7}
Salida: op[] = {1, 7, 10}

Ilustraciones:

Sea, entrada[] = {10, 5, 30, 40, 2, 4, 9}

Inicializar: salida[] = {}, sublista[] = {}

Mover el primer elemento de entrada a la sublista.
sublista[] = {10}

Recorra los elementos de entrada restantes y, si el elemento actual es mayor que el último elemento de la sublista, mueva este elemento de la entrada a la sublista. 
Ahora, sublista[] = {10, 30, 40}, entrada[] = {5, 2, 4, 9}

Combinar la sublista en la salida.
operación = {10, 30, 40}

Próxima llamada recursiva: Mover el primer elemento de entrada a la sublista. sublista[] = {5}

Atraviese los elementos restantes de entrada y mueva los elementos mayores que los insertados por última vez.
entrada[] = {2, 4}
sublista[] = {5, 9}

Fusionar sublista en op.
salida = {5, 9, 10, 30, 40}

Última llamada recursiva:

{2, 4} primero se mueven a la sublista y luego se fusionan en la salida.
salida = {2, 4, 5, 9, 10, 30, 40}

A continuación se muestran los pasos simples utilizados en el algoritmo:

• Sea ip[] una lista de entrada y op[] una lista de salida.
• Cree una sublista vacía y mueva el primer elemento de ip[] a ella.
• Atraviesa los elementos restantes de ip. Para cada elemento x, verifique si x es mayor que el último elemento insertado para sublistar. En caso afirmativo, elimine x de ip y agregue al final de la sublista. Si no, ignore x (Manténgalo en ip)
• Fusionar sublista en op (lista de salida)
• Repetir para elementos restantes en ip y elementos actuales en op.

A continuación se muestra la implementación del algoritmo anterior. La implementación de C++ usa la lista en C++ STL . 

// CPP program to implement Strand Sort
#include <bits/stdc++.h>
using namespace std;
  
// A recursive function to implement Strand
// sort.
// ip is input list of items (unsorted).
// op is output list of items (sorted)
void strandSort(list<int> &ip, list<int> &op)
{
    // Base case : input is empty
    if (ip.empty())
        return;
  
    // Create a sorted sublist with
    // first item of input list as
    // first item of the sublist
    list<int> sublist;
    sublist.push_back(ip.front());
    ip.pop_front();
       
    // Traverse remaining items of ip list
    for (auto it = ip.begin(); it != ip.end(); ) {
  
        // If current item of input list
        // is greater than last added item
        // to sublist, move current item
        // to sublist as sorted order is
        // maintained.
        if (*it > sublist.back()) {
            sublist.push_back(*it);
  
            // erase() on list removes an
            // item and returns iterator to
            // next of removed item.
            it = ip.erase(it);
        }
  
        // Otherwise ignore current element
        else
            it++;
    }
  
    // Merge current sublist into output
    op.merge(sublist);
  
    // Recur for remaining items in
    // input and current items in op.
    strandSort(ip, op);
}
  
// Driver code
int main(void)
{
    list<int> ip{10, 5, 30, 40, 2, 4, 9};
  
    // To store sorted output list
    list<int> op;
  
    // Sorting the list
    strandSort(ip, op);
  
    // Printing the sorted list
    for (auto x : op)
        cout << x << " ";
    return 0;
}

2 4 5 9 10 30 40

Complejidad temporal: O(N ² )
Espacio auxiliar: O(N)

Echa un vistazo al curso de autoaprendizaje de DSA

Más algoritmos de clasificación: 

Problemas de práctica sobre clasificación