Ordenamiento: QuickSort, BubbleSort y SelectionSort

En esta entrada vamos a poner, en código, en Java la implementación de los algoritmos de ordenamiento de burbuja, selección y quicksort. Algunos lectores del blog los han solicitado y son de los algoritmos que más se estudian en la facultad.

QuickSort

El algoritmo quicksort tiene un complejidad logarítmica O(n log n).

public static void quickSort(int[] arr, int left, int right) {
	    int pivotIndex = left + (right - left) / 2;
	    int pivotValue = arr[pivotIndex];
	    int i = left;
	    int j = right;
	    while (i <= j) {
	      while (arr[i] < pivotValue) {
	        i++;
	      }
	      while (arr[j] > pivotValue) {
	        j--;
	      }
	      if (i <= j) {
	        int tmp = arr[i];
	        arr[i] = arr[j];
	        arr[j] = tmp;
	        i++;
	        j--;
	      }
	      if (left < i) {
	        quickSort(arr, left, j);
	      }
	      if (right > i) {
	        quickSort(arr, i, right);
	      }
	    }
	  }

BubbleSort

Este es, sin dudas de los más fáciles de implementar y más usados por los estudiantes. La complejidad es O(n^2).

public static void bubbleSort(int[] arr) {
	    int lastIndex = arr.length - 1;
	    for (int j = 0; j < lastIndex; j++) {
	      for (int i = 0; i < lastIndex - j; i++) {
	        if (arr[i] > arr[i + 1]) {
	          int tmp = arr[i];
	          arr[i] = arr[i + 1];
	          arr[i + 1] = tmp;
	        }
	      }
	    }
	  }

Selection Sort

Al igual que burbuja, la doble anidación provoca O(n^2).

public static void selectionSort(int[] arr) {
	    int len = arr.length;
	    for (int i = 0; i < len - 1; i++) {
	      int minIndex = i;
	      for (int j = i + 1; j < len; j++) {
	        if (arr[j] < arr[minIndex]) {
	          minIndex = j;
	        }
	      }
	      int tmp = arr[minIndex];
	      arr[minIndex] = arr[i];
	      arr[i] = tmp;
	    }
	  }

Espero te sirvan estos algoritmos.