ORDENAMIENTO DE ELEMENTOS
Ordenamiento en C++ de la forma: Burbuja
El método burbuja es un sencillo algoritmo de ordenamiento. Funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambiándolos de posición si están en el orden equivocado. Es necesario revisar varias veces toda la lista hasta que no se necesiten más intercambios, lo cual significa que la lista está ordenada.
El método de ordenación por burbuja se basa en comparaciones sucesivas de dos elementos consecutivos y realizar un intercambio entre los elementos hasta que queden ordenados.
Supongamos el vector mostrado en la siguiente tabla, para realizar la ordenación se han de seguir estos pasos:
-
Se comparan los dos primeros elementos, si el segundo es superior al primero, se dejan tal como están, pero si el primero es el más grande, se intercambian los elementos.
-
A continuación se compara el segundo elemento con el tercero aplicando los mismos criterios del paso anterior.
-
De esta forma se repite la operación de comparación con todos los elementos que forman el vector. Cuando se alcance el último elemento se ha encontrado el elemento que tiene el valor más elevado y este ha quedado situado al final del vector.
-
Para encontrar el segundo elemento se repite la operación de ordenación de todos los elementos del vector excepto con el último.
-
Reiterando el proceso descrito, el vector quedará ordenado cuando solo se comparen los dos primeros elementos.
Ordenamiento en C++ de la forma: Selección
Es un algoritmo de ordenamiento que requiere O(n^2) operaciones para ordenar una lista de n números. Su funcionamiento es el siguiente:
Buscar el mínimo elemento de la lista.
Intercambiar con el primer elemento.
Buscar el mínimo del resto de la lista. Intercambiar con el segundo.
Y así sucesivamente.
Ordenamiento en C++ de la forma: Inserción
Es una manera muy natural de ordenar para un ser humano, y puede usarse fácilmente para ordenar un mazo de cartas numeradas en forma arbitraria. Requiere O(n²) operaciones para ordenar una lista de n elementos.
Básicamente lo que hace este algoritmo es:
-
Cómo entrada tenemos un arreglo u otra estructura compatible con elementos ordenables, que vamos a llamar v.
-
Vamos a recorrer i veces este arreglo, donde i es el tamaño de nuestro arreglo. Esto quiere decir que se recorrerá el arreglo una vez por cada elemento que contenga.
-
Tendremos además un contador j, que iniciará en i-1, y recorrerá todo el arreglo a la izquierda del elemento i.
-
Se guardará el elemento i en una variable temporal.
-
Para posteriormente recorrer todo el arreglo de j a 0. Si algún elemento es mayor que la variable temporal se intercambiarán. De lo contrario se recorrerá el arreglo.
-
Esto significa que se recorre el arreglo hasta que se encuentre el mejor lugar para insertar el elemento temporal.
-
Este procedimiento se repite hasta que se haya concluido con todos los elementos de el arreglo. En este momento también el arreglo también estará ordenado.
Ordenamiento en C++ de la forma: Shell
El Shell sort es una generalización del ordenamiento por inserción, teniendo en cuenta dos observaciones: El ordenamiento por inserción es eficiente si la entrada está "casi ordenada". El ordenamiento por inserción es ineficiente, en general, porque mueve los valores sólo una posición cada vez.
El algoritmo Shell sort mejora el ordenamiento por inserción comparando elementos separados por un espacio de varias posiciones. Esto permite que un elemento haga "pasos más grandes" hacia su posición esperada. Los pasos múltiples sobre los datos se hacen con tamaños de espacio cada vez más pequeños. El último paso del Shell sort es un simple ordenamiento por inserción, pero para entonces, ya está garantizado que los datos del vector están casi ordenados
Ordenamiento en C++ de la forma: Quick Sort
El ordenamiento por partición (Quick Sort) se puede definir en una forma más conveniente como un procedimiento recursivo. Tiene aparentemente la propiedad de trabajar mejor para elementos de entrada desordenados completamente, que para elementos semiordenados. Esta situación es precisamente la opuesta al ordenamiento de burbuja.Este tipo de algoritmos se basa en la técnica "divide y vencerás", o sea es más rápido y fácil ordenar dos arreglos o listas de datos pequeños, que un arreglo o lista grande.
