tipos - C Consejos de clasificación de matriz

operaciones con matrices algebra lineal

Question

       a=[1,3,6,7,1,2]

¿Cuál es la mejor técnica de clasificación para ordenar la siguiente matriz y si hay duplicados cómo manejarlos? Además, cuál es la mejor técnica de clasificación de todos ...

 void BubbleSort(int a[], int array_size)
 {
 int i, j, temp;
 for (i = 0; i < (array_size - 1); ++i)
 {
      for (j = 0; j < array_size - 1 - i; ++j )
      {
           if (a[j] > a[j+1])
           {
                temp = a[j+1];
                a[j+1] = a[j];
                a[j] = temp;
           }
      }
 }
 }   

Answer 1

Depende

Depende de varias cosas. Pero, en general, los algoritmos que utilizan un enfoque dichotomic Divide-and-Conquer tendrán un buen rendimiento en la clasificación de problemas, ya que presentan complejidades interesantes de casos promedio.

Lo esencial

Para comprender qué algoritmos funcionan mejor, necesitará conocimientos básicos de complejidad de algoritmos y notación de gran O , para que pueda entender cómo califican en términos de casos promedio, mejor y peor de los casos . Si es necesario, también deberá prestar atención a la estabilidad del algoritmo de clasificación .

Por ejemplo, generalmente un algoritmo eficiente es quicksort. Sin embargo, si le da a quicksort una lista perfectamente invertida, tendrá un bajo rendimiento (¡una selección simple de clasificación tendrá un mejor rendimiento en ese caso!). Shell-sort también suele ser un buen complemento de quicksort si realiza un preanálisis de su lista.

Eche un vistazo a lo siguiente, para "búsquedas avanzadas" que usan enfoques de dividir y conquistar:

• quicksort
• shellsort
• mergesort

Y estos algoritmos más directos para los menos complejos:

• bubblesort
• tipo de selección
• insertar tipo

Promover

Los anteriores son los sospechosos habituales al comenzar, pero hay muchos más.

Como señaló R. en los comentarios y por Kriss en su respuesta, es posible que desee echarle un vistazo a HeapSort , que ofrece una complejidad de clasificación teóricamente mejor que un quicksort (pero a menudo no le irá mejor en entornos prácticos). También hay variantes y algoritmos híbridos (por ejemplo, TimSort ).

Answer 2

En C, puede usar el comando integrado qsort :

int compare( const void* a, const void* b)
{
     int int_a = * ( (int*) a );
     int int_b = * ( (int*) b );

     if ( int_a == int_b ) return 0;
     else if ( int_a < int_b ) return -1;
     else return 1;
}

qsort( a, 6, sizeof(int), compare )

ver: http://www.cplusplus.com/reference/clibrary/cstdlib/qsort/

Para responder la segunda parte de su pregunta: un algoritmo de clasificación óptimo (basado en la comparación) es uno que se ejecuta con comparaciones O (n log (n)). Hay varios que tienen esta propiedad (incluida la ordenación rápida, el tipo de fusión, el ordenamiento en heap, etc.), pero cuál usar depende de su caso de uso.

Como nota al margen, en algún momento puede obtener mejores resultados que O (n log (n)) si conoce algo sobre sus datos: consulte el artículo de Wikipedia sobre Radix Sort

Answer 3

En su caso particular, la clasificación más rápida es probablemente la que se describe en esta respuesta . Está exactamente optimizado para una matriz de 6 ints y utiliza redes de clasificación. Es 20 veces (medido en x86) más rápido que la biblioteca qsort. Las redes de clasificación son óptimas para el tipo de matrices de longitud fija. Como son una secuencia fija de instrucciones, incluso pueden implementarse fácilmente mediante hardware.

En general, hay muchos algoritmos de clasificación optimizados para algunos casos especializados. Los algoritmos de uso general como el ordenamiento en montones o el ordenamiento rápido están optimizados para la ordenación in situ de un conjunto de elementos. Otorgan una complejidad de O (n.log (n)), siendo n el número de elementos para ordenar.

La función de biblioteca qsort () está muy bien codificada y es eficiente en términos de complejidad, pero utiliza una llamada a alguna función comparizon proporcionada por el usuario, y esta llamada tiene un costo bastante alto.

Para clasificar gran cantidad de datos, los algoritmos también deben encargarse del intercambio de datos hacia y desde el disco, este es el tipo de ordenamientos implementados en las bases de datos y su mejor opción si tiene tales necesidades es colocar datos en alguna base de datos y usar el construido en especie.

Answer 4

La mejor técnica de clasificación de todos generalmente depende del tamaño de una matriz. El tipo de fusión puede ser el mejor de todos, ya que logra una mejor complejidad de espacio y tiempo de acuerdo con el algoritmo Big-O (Esto se adapta mejor a una matriz grande).

Answer 5

Me gustaría hacer algunos cambios: en C, puede usar el comando integrado qsort :

int compare( const void* a, const void* b)
{
   int int_a = * ( (int*) a );
   int int_b = * ( (int*) b );

   // an easy expression for comparing
   return (int_a > int_b) - (int_a < int_b);
}

qsort( a, 6, sizeof(int), compare )