Ordenamiento Simple

Profesores

Estructura de datos y algoritmosUnidad 05 – Recursividad y Ordenamiento

•Alfredo Granda

•Juan Ramírez

Unidad 05 - Ordenamiento SimpleObjetivos

• Definición

• Ordenamiento por intercambio

• Burbuja

• Burbuja Modificada

• Ordenamiento por selección

• Ordenamiento por inserción

Definición

Ordenamiento

• El ordenamiento de los datos consiste en disponerun conjunto de datos (o una estructura) en algúndeterminado orden con respecto a alguno de suscampos.▫ Clave: Campo por el cual se ordena.

• Según donde estén almacenados los datos aordenar, podemos decir que el ordenamiento es:▫ Interna: Arrays, listas o árbol. Típicamente en RAM.

▫ Externa: En Archivos en discos.

Orden

• Una lista de datos está ordenada por la clave k si la listaestá en orden con respecto a la clave anterior.

• Este Orden puede ser:▫ Ascendente: (i<j) entonces (k[i]<=k[j])▫ Descendente: (i>j) entonces (k[i]>=k[j])

• Hay Numerosos Métodos de Ordenamiento que difierenen eficiencia.▫ Análisis de algoritmo orientado a las comparaciones

realizadas por cada uno.▫ Las comparaciones serán función de “n”. Siendo “n” el

tamaño del vector a Ordenar.

Clasificación de Métodos de Ordenamiento

• Analizaremos los siguientes métodos:▫ Básicos: Son eficaces en Listas pequeñas Burbuja e Intercambio: simple pero Ineficiente.

Selección e inserción: Recomendados.

▫ Avanzados: Son eficaces en Listas grandes. Merge Sort: muy extendido

Quick Sort: muy extendido

Shell Sort: muy extendido

Counting Sort: el mas rápido para números

Ordenamiento por intercambio

Ordenamiento por Intercambio(Conocido como Burbuja)• El más sencillo de todos. Se basa en:

▫ La lectura sucesiva de la lista a ordenar,

▫ Comparando el elemento inferior de la lista con todoslos restantes

▫ Efectuando el Intercambio de posiciones cuando elorden resultante no sea correcto.

• Siendo n la cantidad de elementos, Realizará almenos n–1 pasadas.

Ejemplo - Ordenamiento por Intercambio

Pasada 1: Se compara a[1] con todos, así primero se cambia a[1] con a[2] pues a[1] >a[2] y debe ser Ascendente, es decir a[1]<a[2] …y por utimo a[1] con a[4]

a[1] a[2] a[3] a[4]

8 4 6 2

a[1] a[2] a[3] a[4]

4 8 6 2

a[1] a[2] a[3] a[4]

2 8 6 4

Pasada 2: El elemento mas pequeño esta en a[1] y se analiza la sublista restante.Al cabo de la pasada, el segundo mas chico esta en a[2]….

Pasada i: Al cabo de la pasada i, el elemento de orden i, está en a[i]

Pasada 3:a[1] a[2] a[3] a[4]

2 4 6 8

a[1] a[2] a[3] a[4]

2 4 8 6

Algoritmo: Ordenamiento por Intercambio

Algoritmo ordIntercambio (a[], n)

i, k, aux: enteros /* se realizan n-1 pasadas */

para i desde 1 hasta n-1 hacer

para k desde i+1 hasta n hacer

si a[i] > a[k] entonces

aux a[i]

a[i] a[k];

a[k] aux ;

Complejidad (n)(n–1)

Del Orden F(n)=n2.

Mejor Caso = O(n2)

Peor Caso = O(n2)

Código en C++Ordenamiento por Intercambio

void ordIntercambio (int a[], int n)

{

for (int i=0; i < n-1; i++)

{

for (int k=i+1; k<n; k++)

{

if (a[i] > a[k])

{

int aux = a[i];

a[i] = a[k];

a[k] = aux;

}

}

}

}

Burbuja

Burbuja (Verdadera Burbuja)

• Los elementos burbujean: ▫ Los mas grandes, caen al fondo del arreglo (posición n) ▫ Los mas chicos suben a la cima (posición 1).

• Estudia parejas de elementos Adyacentes▫ a[1] y a[2], a[2] y a[3]…a[i] y a[i+1]… a[n–1] y a[n].▫ Si a[i+1] < a[i] Entonces Los INTERCAMBIA

• Algoritmo:▫ Pasada 1: considera desde (a[1], a[2]) hasta (a[n–1], a[n]). En a[n] esta el elemento mas grande.

▫ Pasada 2: considera desde (a[1], a[2]) hasta (a[n–2], a[n–1]). En a[n–1] esta el segundo elemento mas grande.

▫ Pasada i: considera desde (a[1], a[2]) hasta (a[n–i], a[n-i+1]). En a[n–i+1] esta el elemento de orden i.

▫ El proceso termina con la pasada n–1 El elemento mas pequeño esta en a[1].

Burbuja

Pasada 1:

a[1] a[2] a[3] a[4] a[5]

50 20 40 80 30

a[1] a[2] a[3] a[4] a[5]

20 50 40 80 30

a[1] a[2] a[3] a[4] a[5]

20 40 50 80 30

a[1] a[2] a[3] a[4] a[5]

20 40 50 80 30

a[1] a[2] a[3] a[4] a[5]

20 40 50 30 80

Pasada 2:

a[1] a[2] a[3] a[4] a[5]

20 40 50 30 80

a[1] a[2] a[3] a[4] a[5]

20 40 50 30 80

a[1] a[2] a[3] a[4] a[5]

20 40 50 30 80

a[1] a[2] a[3] a[4] a[5]

20 40 30 50 80

Pasada 3:

a[1] a[2] a[3] a[4] a[5]

20 40 30 50 80

a[1] a[2] a[3] a[4] a[5]

20 40 30 50 80

a[1] a[2] a[3] a[4] a[5]

20 30 40 50 80

Algoritmo: Ordenamiento por Burbuja

Algoritmo ordBurbuja (a[], n)

i, k, aux: enteros

Repetir con i desde 1 hasta n-1

Repetir con k desde 1 hasta n-i

si (a[k] > a[k+1]) entonces

aux = a[k]

a[k] = a[k+1]

a[k+1] = auxMejor Caso = O(n2)

Caso Prom. = O(n2)

Peor Caso = O(n2)

Algoritmo: Ordenamiento por Burbuja (Modificado)Algoritmo ordBurbujaModificado (a[], n)

i, k, aux: enterosordenado: boolean

Repetir con i desde 1 hasta n-1ordenado = trueRepetir con k desde 1 hasta n-i

si (a[k] > a[k+1]) entonces aux = a[k]a[k] = a[k+1]a[k+1] = auxordenado = false

si (ordenado) break Mejor Caso = O(n)

Caso Prom. = O(n2)

Peor Caso = O(n2)

Código en C++:Ordenamiento por Burbuja (Modificado)

void ordBurbujaModificado (int a[], int n)

{

bool ordenado;

for (int i=0; i < n-1; i++)

{

ordenado = true;

for (int j=0; j < n - (i + 1); j++)

{

if (a[j] > a[j+1])

{

int aux = a[j];

a[j] = a[j+1];

a[j+1] = aux;

ordenado = false;

}

}

if (ordenado) break;

}

}

Ordenamiento por selecciónSelection Sort

Ordenamiento Por Selección

• Realiza sucesivas pasadas que▫ Buscan el elemento más pequeño de la lista a y lo

escribe al frente de la lista a[1].▫ Considera las posiciones restantes, a[2]…a[n]▫ Finaliza cuando ya no hay Posiciones Restantes.

• En la pasada i▫ Está Ordenado: desde a[1] hasta a[i–1].▫ Está Desordenado: Desde a[i] hasta a[n].

• El proceso continua n–1 vueltas.

Ejemplo: Ordenamiento por Selección

Pasada 1: Lista entre 1 y 4. Selecciona el menor (21)y lo pasa al a[1]

a[1] a[2] a[3] a[4]

51 21 39 80

Pasada 2: Lista entre 2 y 4. Selecciona el menor (39)y lo pasa al a[2]

a[1] a[2] a[3] a[4]

21 39 51 80

Pasada 3: Lista entre 3 y 4. No selecciona nada.a[1] a[2] a[3] a[4]

21 39 51 80

a[1] a[2] a[3] a[4]

21 51 39 80

Lista Original:

Algoritmo: Ordenamiento por Selección

Algortimo ordSeleccion (a[], n)menor, k, j: enteros;Repetir con i desde 1 hasta n-1

k = i /* comienzo de la exploración en índice i */menor = a[i]Repetir con j desde i+1 hasta n

si a[j] < menor entoncesmenor = a[j]k = j

a[k] = a[i]a[i] = menor

Complejidad (n (n–1))/2Del Orden F(n)=n2.

Mejor Caso = O(n2)

Caso Prom. = O(n2)

Peor Caso = O(n2)

Código en C++: Ordenamiento por Selección

void ordSeleccion (int a[], int n)

{

int k, menor;

for (int i=0; i < n-1; i++)

{

k = i;

menor = a[i];

for (int j=i+1; j<n; j++)

{

if (a[j] < menor)

{

menor = a[j];

k = j;

}

}

a[k] = a[i];

a[i] = menor;

}

}

Ordenamiento por inserción

Ordenamiento Por Inserción

• Similar al proceso de ordenar tarjetas en un tarjetero por ordenalfabético:▫ Consiste en insertar un elemento en su posición correcta, dentro de

una lista que ya está Ordenada.

• Algoritmo:▫ El 1er elemento a[1] se lo considera ordenado.

▫ Se inserta a[2] en la posición correcta, delante o detrás del a[1], segúnsea mayor o menor.

▫ Por cada bucle i (desde i = 2 hasta n) se explora la sublista a[1]..a[i–1]buscando la posición correcta de inserción del elemento a[i].

▫ Al dejar vacía la posición a[i] se impone un desplazamiento de todo elvector, desde el lugar de inserción.

Ejemplo: Ordenamiento por Inserción

Pasada 1: Comenzamos en a[2] desplazando a laderecha todos los valores que sean mayores a 21 (a[1])

a[1] a[2] a[3] a[4]

51 21 10 15

Pasada 2: El 10 lo mueve hasta a[1] a[1] a[2] a[3] a[4]

10 21 51 15

Pasada 3: El 15 lo mueve hasta a[2].a[1] a[2] a[3] a[4]

10 15 21 51

a[1] a[2] a[3] a[4]

21 51 10 15

Lista Original:

Algoritmo: Ordenamiento por Inserción

Algoritmo ordInsercion (a[], n)

i, j, aux : enteros

Repetir con i desde 2 hasta n

aux = a[i]

k = i-1

Repetir mientras (k >= 1) y (aux < a[k])

a[k+1] = a[k]

k = k-1

a[k+1] = aux

Complejidad (n (n–1))/2

Del Orden F(n)=n2.

Mejor Caso = O(n)

Caso Prom. = O(n+d)

Peor Caso = O(n2)

d es la cantidad de inversiones

Código en C++:Ordenamiento por Inserción

void ordInsercion (int a[], int n)

{

int aux, k;

for (int i=1; i<n; i++)

{

aux = a[i];

k = i-1;

while (k >= 0 && aux < a[k])

{

a[k+1] = a[k];

k--;

}

a[k+1] = aux;

}

}

Ejercicios

Ejercicio 1 - UVA - 10327

Sample Input31 2 3 32 3 1

Sample OutputMinimum exchange operations : 0 Minimum exchange operations : 2

Sorting in computer science is an important part. Almost every problem can be solved effeciently if sorteddata are found. There are some excellent sorting algorithm which has already acheived the lower boundnlgn. In this problem we will also discuss about a new sorting approach. In this approach only oneoperation ( Flip ) is available and that is you can exchange two adjacent terms. If you think a while, youwill see that it is always possible to sort a set of numbers in this way.

The ProblemA set of integers will be given. Now using the above approach we want to sort the numbers in ascendingorder. You have to find out the minimum number of flips required. Such as to sort "1 2 3" we need no flipoperation whether to sort "2 3 1" we need at least 2 flip operations.

The InputThe input will start with a positive integer N ( N<=1000 ). In next few lines there will be N integers. Inputwill be terminated by EOF.

The OutputFor each data set print "Minimum exchange operations : M" where M is the minimum flip operationsrequired to perform sorting. Use a seperate line for each case.


Example Input3 3 1 3 2 4 4 3 2 1 2 2 1

Example OutputOptimal train swapping takes 1 swaps. Optimal train swapping takes 6 swaps. Optimal train swapping takes 1 swaps.

At an old railway station, you may still encounter one of the last remaining ``train swappers''. A train swapper is an employee of the railroad,whose sole job it is to rearrange the carriages of trains.Once the carriages are arranged in the optimal order, all the train driver has to do, is drop the carriages off, one by one, at the stations for whichthe load is meant.

The title ``train swapper'' stems from the first person who performed this task, at a station close to a railway bridge. Instead of opening upvertically, the bridge rotated around a pillar in the center of the river. After rotating the bridge 90 degrees, boats could pass left or right.The first train swapper had discovered that the bridge could be operated with at most two carriages on it. By rotating the bridge 180 degrees,the carriages switched place, allowing him to rearrange the carriages (as a side effect, the carriages then faced the opposite direction, but traincarriages can move either way, so who cares).

Now that almost all train swappers have died out, the railway company would like to automate their operation. Part of the program to bedeveloped, is a routine which decides for a given train the least number of swaps of two adjacent carriages necessary to order the train. Yourassignment is to create that routine.

Input SpecificationThe input contains on the first line the number of test cases (N). Each test case consists of two input lines. The first line of a test case contains aninteger L, determining the length of the train ( ). The second line of a test case contains a permutation of the numbers 1 through L, indicating thecurrent order of the carriages. The carriages should be ordered such that carriage 1 comes first, then 2, etc. with carriage L coming last.

Output SpecificationFor each test case output the sentence: 'Optimal train swapping takes S swaps.' where S is an integer.


Sample Input15 31234567891011121314150 0

Hmm! Here you are asked to do a simple sorting. You will be given N numbers and a positive integer M. You will have to sort the N numbers in ascending order of their modulo M value.

If there is a tie between an odd number and an even number (that is their modulo M value is the same) then the odd number will precede the even number.

If there is a tie between two odd numbers (that is their modulo M value is the same) then the larger odd number will precede the smaller odd number and if there is a tie between two even numbers (that is their modulo M value is the same) then the smaller even number will precede the larger even number.

For remainder value of negative numbers follow the rule of C programming language: A negative number can never have modulus greater than zero. E.g. -100 MOD 3 = -1, -100 MOD 4 = 0 etc.

InputThe input file contains 20 sets of inputs. Each set starts with two integers N (0<N<=10000) and M (0<M<=10000) which denotes how many numbers are within this set. Each of the next N lines contains one number each. These numbers should all fit in 32-bit signed integer. Input is terminated by a line containing two zeroes.

OutputFor each set of input produce N+1 lines of outputs. The first line of each set contains the value of N and M. The next N lines contain N numbers, sorted according to the rules mentioned above. Print the last two zeroes of the input file in the output file also.

Sample Output15 31593612137141011528140 0

Education

Ordenamiento Simple