¿Cuál de los siguientes algoritmos de clasificación en el lugar necesita la cantidad mínima de intercambios?
(A) Clasificación rápida
(B) Clasificación por inserción
(C) Clasificación por selección
(D) Clasificación en montón
Respuesta: (C)
Explicación:
Intentemos analizar el número de intercambios en cada uno de los algoritmos de clasificación dados.
Ordenación rápida : la entrada del peor de los casos para el número máximo de intercambios ya se ordenará en orden decreciente.
Recurrencia para el número total de intercambios en este caso:
T(n) = T(n-1) + O(n) // Los intercambios O(n) ocurrirán en llamadas alternativas al algoritmo de partición.
= O(n2)
Clasificación por inserción : la entrada en el peor de los casos para el número máximo de intercambios ya estará ordenada en orden ascendente. Cuando se inserta un nuevo elemento en una array ya ordenada de tamaño k, puede dar lugar a k intercambios (en caso de que sea el más pequeño de todos). ) en el peor caso. Para n-1 iteraciones de clasificación por inserción, los intercambios totales serán O(n2).
Clasificación de selección : no hay entrada de peor caso para la clasificación de selección. Dado que busca el índice del k-ésimo elemento mínimo en la k-ésima iteración y luego en un intercambio, coloca ese elemento en su posición correcta. Para n-1 iteraciones de tipo de selección, puede tener intercambios O(n).
Heap sort : el número total de intercambios en Heap sort puede ser O (nlogn) ya que después de realizar Build-heap que puede requerir O (n) swaps, realiza n-1 extract-min operaciones que dan como resultado intercambios O (nlogn).
Consulte la pregunta 3 de https://www.geeksforgeeks.org/data-structures-and-algorithms-set-7/
Esta solución es aportada por Pranjul Ahuja
Cuestionario de esta pregunta
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA