Selection Sort

Last updated Aug 6, 2023 Edit Source

• Programming
• Interviewprep
• Algorithms
• Sorting

Consiste en recorrer una estructura de datos y encontrar el elemento mas pequeño, intercambiarlo por el elemento en el primer indice de la estructura y proseguir, ignorando ahora, el elemento ya ordenado.

In selection sort, the idea of the algorithm is to find the smallest unsorted element add it to the end of the sorted list.

Autor: Harvard - CS50

1
2
3
4

for i from [0] to [n - 1]
	find smallest number between numbers[i] and numbers[n - 1]
	swap smallest number with numbers[i]
	increment i by 1

Complejidad: Worst-case scenario: O(n^2). Best-case scenario: Omega(n^2).

No entendia por que siempre su complejidad era n^2, incluso en el mejor caso. Tras investigar vi que era por tener los dos loops para hacer las comparaciones. Al tenerlos asi hasta en una coleccion ya ordenada se compara cada elemento con todos los elementos.

In selection sort, the performance is N^2 because of the nested loops. Even though the elements at the end do not need to be swapped, the loops will still compare them.

Extraido de: StackOverFlow

Siguiente: Bubble Sort