Complementing the response of @spuente , bubble can be easily optimized, reducing its execution time by 50% in the worst case detecting when the array is ordered in one of the iterations, avoiding a good amount of comparisons.
In each iteration it is assumed that the array is ordered, setting a flag sorted = true
, then, in the loop where the disordered elements are exchanged, if two disordered elements are found,% is set sorted = false
In each iteration it is checked if sorted
keeps true
, if so it implies that it iterated over list.length -i -1
remaining elements without finding disordered elements and therefore the array is ordered and it does not make sense to continue iterating about it.
public static void main(String[] args) {
optimizedBubbleSort(new int[]{1,2,4,5,6}); // Iteración 0, array ordenado
optimizedBubbleSort(new int[]{11,2,44,5,16}); // Iteración 2, array ordenado
optimizedBubbleSort(new int[]{0,8,74,5,1}); // Iteración 3, array ordenado
}
private static void optimizedBubbleSort(int [] list){
for(int i =0; i< list.length; i++){
boolean sorted = true; // asumo que para la iteración i el listado es ordenado,
for(int j =0; j< list.length - i - 1; j++){ // en cada iteración los elementos desde la posición (length-i) estan ordenados, por lo tanto solo recorro hasta esa posición
if(list[j] > list[j+1]){
int temp = list[j];
list[j] = list[j+1];
list[j+1] = temp;
sorted = false;
}
}
if(sorted){
System.out.println(String.format("Iteración %s, array ordenado", i));
return;
}
}
}