Le tri par insertion considère chaque élément du tableau et l'insère à la bonne place parmi les éléments déjà triés. Ainsi, au moment où on considère un élément, les éléments qui le précèdent sont déjà triés, tandis que les éléments qui le suivent ne sont pas encore triés.
Pour trouver la place où insérer un élément parmi les précédents, il faut le comparer à ces derniers, et les décaler afin de libérer une place où effectuer l'insertion. Le décalage occupe la place laissée libre par l'élément considéré. En pratique, ces deux actions s'effectuent en une passe, qui consiste à faire « remonter » l'élément au fur et à mesure jusqu'à rencontrer un élément plus petit.
static void triInsertion(int[] tab) {
for (int i = 1; i < tab.length; i++) {
// mémoriser T[i] dans tmp
int tmp = tab[i];
// décaler les éléments T[0]..T[i-1] qui sont plus grands que x, en partant de
// T[i-1]
int j = i;
while (j > 0 && tab[j - 1] > tmp) {
tab[j] = tab[j - 1];
j--;
}
// insérer x dans le trou laissé par le décalage
tab[j] = tmp;
}
}
Le tri à bulles est souvent enseigné en tant qu'exemple algorithmique, car son principe est simple. Mais c'est le plus lent des algorithmes de tri communément enseignés, et il n'est donc guère utilisé en pratique.
L'algorithme parcourt le tableau et compare les éléments consécutifs. Lorsque deux éléments consécutifs ne sont pas dans l'ordre, ils sont permutés.
Après un premier parcours complet du tableau, le plus grand élément est forcément en fin de tableau, à sa position définitive. En effet, aussitôt que le plus grand élément est rencontré durant le parcours, il est mal trié par rapport à tous les éléments suivants, donc permuté avec le suivant jusqu'à arriver à la fin du parcours.
Après le premier parcours, le plus grand élément étant à sa position définitive, il n'a plus à être traité. Le reste du tableau est en revanche encore en désordre. Il faut donc le parcourir à nouveau, en s'arrêtant à l'avant-dernier élément. Après ce deuxième parcours, les deux plus grands éléments sont à leur position définitive. Il faut donc répéter les parcours du tableau, jusqu'à ce que les deux plus petits éléments soient placés à leur position définitive.
private static void bubbleSort(int[] nums) {
int left;
int right;
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < nums.length - 1; j++) {
left = nums[j];
right = nums[j + 1];
if (left > right) {
nums[j] = right;
nums[j + 1] = left;
}
}
}
}
import java.util.Arrays;
public class JavaSorts {
public static void main(String[] args) {
int[] nums = { 5, 3, 8, 4, 1, 2, 5, 6, 4, 2, 4, 5, 1, 2, 1 };
System.out.println(Arrays.toString(nums));
// bubbleSort(nums);
insertSort(nums);
System.out.println(Arrays.toString(nums));
}
/**
* Sorts an array of int using the bubble sort algorithm
* It will find the highest number in the array and carry it to the end
* It will swap each number that needs to be swapper along the way
* It will then do the same for the next highest number, etc.
*
* @param array of int to be sorted
*/
private static void bubbleSort(int[] nums) {
int left;
int right;
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < nums.length - 1; j++) {
left = nums[j];
right = nums[j + 1];
if (left > right) {
nums[j] = right;
nums[j + 1] = left;
}
}
}
}
/**
* At each iteration,
* insertion sort removes one element from the input data,
* finds the location it belongs within the sorted list,
* and inserts it there.
*
* @param array of int to be sorted
*/
private static void insertSort(int[] nums) {
int tmp;
for (int i = 1; i < nums.length; i++) {
tmp = nums[i];
int j = i;
while (j > 0 && tmp < nums[j - 1]) {
nums[j] = nums[j - 1];
j--;
}
nums[j] = tmp;
}
}
}