Archivo etiqueta selectionsort

Los algoritmos de ordenación son funciones o métodos que se encargan de ordenar un “array” de datos. Existen varios tipos de métodos de ordenación, pero hoy solo vamos a comentar algunos de los más potentes:

• QuickSort
• MergeSort
• SelectionSort
• BubbleSort

QuickSort

El ordenamiento rápido (quicksort en inglés) es un algoritmo basado en la técnica de “divide y vencerás”, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n.

Quizás este sea el algoritmo de ordenación más rápido que existe.

Representación del algoritmo en pseudo-código:

 function quicksort(array)
     var list less, greater
     if length(array) ≤ 1
         return array
     select and remove a pivot value pivot from array
     for each x in array
         if x ≤ pivot then append x to less
         else append x to greater
     return concatenate(quicksort(less), pivot, quicksort(greater))

Representación del algoritmo en Java:

private static void quickSort(int[] x, int a, int b) {
	int i = a, j = b;
	int p = x[(a+b)/2];
	int v;
	do{
		while(x[i] < p) i++;
		while(x[j] > p) j--;
		if( i <= j ){
			v = x[j];
			x[j] = x[i];
			x[i] = v;
			i++;
			j--;
		}
	} while (i <= j);
	if( a < j ) quickSort(x,a, j);
	if( b > i ) quickSort(x,i, b);
}

Representación del algoritmo gráficamente:

MergeSort

El algoritmo de MergeSort se basa en la misma técnica que QuickSort de “divide y vencerás”, y su tiempo de ordenación es proporcional a n log n.

Representación del algoritmo en pseudo-código:

function mergesort(array A[x..y])
begin
  if (x-y > 1)):
    array A1 := mergesort(A[x..(int( x+y / 2))])
    array A2 := mergesort(A[int(1+(x+y / 2))..y])
    return merge(A1, A2)
  else:
    return A
end

function merge(array A1[0..n1], array A2[0..n2])
begin
  integer p1 := 0
  integer p2 := 0
  array R[0..(n1 + n2 + 1)]
  while (p1 <= n1 or p2 <= n2):
    if (p1 <= n1 and A1[p1] <= A2[p2]):
      R[p1 + p2] := A1[p1]
      p1 := p1 + 1
    if (p2 <= n2 and A1[p1] > A2[p2]):
      R[p1 + p2] := A2[p2]
      p2 := p2 + 1
  return R
end

Representación del algoritmo en Java:

private static void mergeSort( int[ ] x, int[ ] tmpArray, int left, int right ) {
	if( left < right ) {
		int center = ( left + right ) / 2;
		mergeSort( x, tmpArray, left, center );
		mergeSort( x, tmpArray, center + 1, right );
		merge( x, tmpArray, left, center + 1, right );
	}
}

private static void merge( int[ ] x, int[ ] tmpArray, int leftPos, int rightPos, int rightEnd ) {
	int leftEnd = rightPos - 1;
	int tmpPos = leftPos;
	int numElements = rightEnd - leftPos + 1;
	while( leftPos <= leftEnd && rightPos <= rightEnd )
		if( x[ leftPos ] <= x[ rightPos ] )
			tmpArray[ tmpPos++ ] = x[ leftPos++ ];
		else
			tmpArray[ tmpPos++ ] = x[ rightPos++ ];
	while( leftPos <= leftEnd )
		tmpArray[ tmpPos++ ] = x[ leftPos++ ];
	while( rightPos <= rightEnd )
		tmpArray[ tmpPos++ ] = x[ rightPos++ ];
	for( int i = 0; i < numElements; i++, rightEnd-- )
		x[ rightEnd ] = tmpArray[ rightEnd ];
}

Representación del algoritmo gráficamente:

SelectionSort:

El ordenamiento por selección (Selection Sort en inglés) es un algoritmo de ordenamiento que requiere O(n²) operaciones para ordenar una lista de n elementos.

Su funcionamiento es el siguiente:

• Buscar el mínimo elemento de la lísta
• Intercambiarlo con el primero
• Buscar el mínimo en el resto de la lista
• Intercambiarlo con el segundo

Representación del algoritmo en pseudo-código:

para i=1 hasta n-1
    minimo = i;
    para j=i+1 hasta n
        si lista[j] < lista[minimo] entonces
            minimo = j /* (!) */
        fin si
    fin para
    intercambiar(lista[i], lista[minimo])
fin para

Representación del algoritmo en Java:

public static void selectionSort(int[] x) {
	int n = x.length;
	for (int i=0; i<n-1; i++) {
		for (int j=i+1; j<n; j++) {
			if (x[i] > x[j]) {
				int temp = x[i];
				x[i] = x[j];
				x[j] = temp;
			}
		}
	}
}

Representación del algoritmo gráficamente:

BubbleSort

El Ordenamiento de Burbuja (Bubble Sort en inglés) 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. Este algoritmo obtiene su nombre de la forma con la que suben por la lista los elementos durante los intercambios, como si fueran pequeñas “burbujas”. También es conocido como el método del intercambio directo. Dado que solo usa comparaciones para operar elementos, se lo considera un algoritmo de comparación, siendo el más sencillo de implementar.

Representación del algoritmo en pseudo-código:

procedure bubbleSort( A : list of sortable items ) defined as:
  do
    swapped := false
    for each i in 0 to length(A) - 2 inclusive do:
      if A[i] > A[i+1] then
        swap( A[i], A[i+1] )
        swapped := true
      end if
    end for
  while swapped
end procedure

Representación del algoritmo en Java:

public static void bubbleSort(int[] x) {
	int n = x.length;
	for (int pass=1; pass < n; pass++) {
		for (int i=0; i < n-pass; i++) {
			if (x[i] > x[i+1]) {
				int temp = x[i];  x[i] = x[i+1];  x[i+1] = temp;
			}
		}
	}
}

Representación del algoritmo gráficamente:

Comparación de los Algoritmos

Después de explicar los algoritmos, he procedido a cronometrarlos uno a uno ordenando una lista de 10.000 elementos mediante una maquina de Java.

Los resultados fueron los siguientes:

1. QuickSort: 1.29 ms de media.
2. MergeSort: 1.57 ms de media.
3. BubbleSort: 49.08 ms de media.
4. SelectionSort: 103.77 ms de media.

Los archivos utilizados para este procedimiento están aquí.

Enlaces | Wikipedia