Algorithmes de tri en Java - Différents types d'algorithmes de tri en Java

• Introduction aux algorithmes de tri en Java

Introduction aux algorithmes de tri en Java

Trier les informations dans un certain ordre, souvent dans un cadre de type tableau, c'est les organiser. Vous pouvez utiliser différentes exigences de séquence, les plus courantes sont le tri des nombres du plus petit au plus grand ou vice versa, ou le tri lexicographique des chaînes. Nous couvrirons différents algorithmes, des alternatives inefficaces mais intuitives aux algorithmes efficaces mis en œuvre efficacement en Java et dans d'autres langages si vous êtes intéressé par le fonctionnement du tri.

Différents algorithmes de tri en Java

Il existe différents algorithmes de tri et ils ne sont pas tous aussi efficaces. Afin de les comparer et de voir celles qui fonctionnent le mieux, nous analyserons leur complexité temporelle.

1. Tri par insertion
2. Tri des bulles
3. Tri de sélection
4. Tri par fusion
5. Heapsort

1. Tri par insertion

Le concept derrière le tri par insertion divise la plage en sous-réseaux triés et non triés. La partie classée est au début de la durée 1 et correspond au premier composant (côté gauche) du tableau. Nous parcourons le tableau et développons la partie classée du tableau d'un composant à chaque itération. Lorsque nous développons, nous positionnons l'élément frais dans le sous-tableau trié. Pour ce faire, nous déplaçons tous les éléments vers la droite jusqu'à ce que nous constations que nous n'avons pas à modifier le premier composant. Lorsque la partie en gras est triée par ordre croissant, par exemple, dans le tableau suivant, cela se produit:

1. 3 5 7 8 4 2 1 9 6: Considérez 4 et insérez ce dont nous avons besoin. Nous changeons depuis 8> 4
2. 2. 3 5 7 x 8 2 1 9 6
3. 3 5 x 7 8 2 1 9 6
4. 3 x 5 7 8 2 1 9 6
5. 3 4 5 7 8 2 1 9 6

Code:

public class InsertionSortEx (
public static void insertionSort(int() arr) (
for (int x = 1; x < arr.length; x++) (
int current = arr(x);
int y = x - 1;
while(y >= 0 && current < arr(y)) (
arr(y+1) = arr(y);
y--;
)
arr(y+1) = current;
)
)
public static void main(String a())(
int() arr1 = (3, 5, 7, 8, 4, 2, 1, 9, 6);
System.out.println("Before Sorting");
for(int x:arr1)(
System.out.print(x+" ");
)
System.out.println();
insertionSort(arr1);//sorting array using insertion sort
System.out.println("After Insertion Sorting");
for(int x:arr1)(
System.out.print(x+" ");
)
)
)

Production:

En suivant cette méthode, un composant a étendu la partie triée, nous avons maintenant cinq au lieu de quatre éléments. Chaque itération fait cela et le tableau entier sera trié à la fin.

Remarque: Ceci est dû au fait que nous devons transférer la liste classée entière une par une à chaque itération, qui est O (n). Pour chaque composant de chaque table, nous devons le faire, ce qui implique qu'il est borné O (n 2).

2. Tri des bulles

Si la bulle n'est pas dans l'ordre requis, elle fonctionne en remplaçant les composants voisins. Cette opération est répétée jusqu'à ce que tous les composants soient en ordre depuis le début de la matrice. Nous savons que si nous parvenons à faire toute l'itération sans swaps, tous les éléments par rapport à leurs éléments adjacents étaient dans l'ordre souhaitable et, par extension, l'ensemble du tableau. La raison de l'algorithme de tri des bulles est que les nombres comme «bulles vers le haut» dans le «sol». Si, après un montant spécifique, vous recommencez l'instance (4 est une bonne instance), vous remarquerez que le nombre lentement se déplace vers la droite.

Les étapes du tri à bulles sont les suivantes:

1. 4 2 1 5 3: Ici, 1 ^er deux nombres ne sont pas dans le bon ordre, donc nous devons trier les deux nombres.
2. 2 4 1 5 3: Après cela, la prochaine paire de chiffres n'est pas non plus dans le bon ordre. Le tri se produit donc à nouveau.
3. 2 1 4 5 3: Ces deux sont dans le bon ordre, 4 <5, il n'est donc pas nécessaire de les échanger.
4. 2 1 4 5 3 : Encore une fois, nous devons échanger pour le bon ordre.
5. 2 1 4 3 5: Voici le tableau résultant après une itération.
6. Nous devons répéter ce processus jusqu'à ce que les chiffres soient en ordre.

Code:

public class BubbleSortExample (
public static void bubbleSort(int() arr) (
int n = arr.length;
int tmp = 0;
for(int x=0; x < n; x++)(
for(int y=1; y < (nx); y++)(
if(arr(y-1) > arr(y))(
//swap elements
tmp = arr(y-1);
arr(y-1) = arr(y);
arr(y) = tmp;
)
)
)
)
public static void main(String() args) (
int arr() =(4, 2, 1, 5, 3);
System.out.println("Array Before Bubble Sort");
for(int x=0; x < arr.length; x++)(
System.out.print(arr(x) + " ");
)
System.out.println();
bubbleSort(arr);
System.out.println("Array After Bubble Sort");
for(int x=0; x < arr.length; x++)(
System.out.print(arr(x) + " ");
)
)
)

Production:

Remarque: Cela aurait pu se retrouver dans une boucle infinie si j'avais utilisé a (i)> = a (i + 1), car cette connexion serait toujours valide avec des composants équivalents et donc toujours les échanger d'un élément à un autre.

3. Tri de sélection

Le tri de sélection divise le tableau en un tableau de classifications qui ne sont pas triées. Cette fois, cependant, le sous-tableau de tri est formé en insérant à la fin du tableau trié l'élément minimum du sous-tableau non trié, en échangeant:

1. 3 5 1 2 4
2. 1 5 3 2 4
3. 1 2 3 5 4
4. 1 2 3 5 4
5. 1 2 3 4 5
6. 1 2 3 4 5

Code:

public class SelectionSortEx (
public static void selectionSort(int() arr)(
for (int x = 0; x < arr.length - 1; x++)
(
int indx = x;
for (int y = x + 1; y < arr.length; y++)(
if (arr(y) < arr(indx))(
indx = y;
)
)
int smallNumber = arr(indx);
arr(indx) = arr(x);
arr(x) = smallNumber;
)
)
public static void main(String a())(
int() arr1 = (3, 5, 1, 2, 4);
System.out.println("Before Sorting");
for(int x:arr1)(
System.out.print(x+" ");
)
System.out.println();
selectionSort(arr1);
System.out.println("After Selection Sorting");
for(int x:arr1)(
System.out.print(x+" ");
)
)
)

Production:

Remarque: Le minimum est O (n) pour la taille du tableau car tous les composants doivent être vérifiés. Pour chaque élément du tableau, nous devons trouver le minimum et limiter l'ensemble du processus O (n 2).

4. Tri par fusion

Merge Sort utilise la récursivité pour résoudre le problème de la méthode de division et de conquête plus efficacement que les algorithmes décrits précédemment.

Cet arbre montre comment fonctionnent les appels récursifs. Les tableaux marqués d'une flèche vers le bas sont les tableaux pour lesquels nous appelons fonction pendant que nous fusionnons des tableaux à flèche vers le haut. Ensuite, vous suivez la flèche jusqu'au bord de l'arbre, puis revenez et fusionnez. Nous avons une plage de 3 5 3 1, nous la divisons donc en 3 5 4 et 2 1. Nous les divisons en leurs parties afin de les trier. Nous commençons à les fusionner et à les trier au fur et à mesure que nous arrivons au fond.

Code:

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
public class MergeSort (
static void merge(int() array, int lowval, int midval, int highval)(
int x, y, k;
int() c= new int(highval-lowval+1);
k = 0;
x=lowval;
y=midval+1;
while(x<=midval && y<=highval)(
if(array(x)<=array(y))(
c(k++) = array(x++);
)
else(
c(k++) = array(y++);
)
)
while(x<=midval)(
c(k++) = array(x++);
)
while(y<=highval)(
c(k++) = array(y++);
)
k=0;
for(x = lowval; x<=highval; x++)(
array(x) = c(k++);
)
)
static void mergeSort(int() array, int lowval, int highval)(
if(highval-lowval+1>1)(
int midval = (lowval+highval)/2;
mergeSort(array, lowval, midval);
mergeSort(array, midval+1, highval);
merge(array, lowval, midval, highval);
)
)
public static void main(String() args) (
BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
int size;
System.out.println("Enter the array");
try (
size = Integer.parseInt(r.readLine());
) catch (Exception e) (
System.out.println("Please Enter valid Input");
return;
)
int() array = new int(size);
System.out.println("Enter array elements");
int x;
for (x = 0; x < array.length; x++) (
try (
array(x) = Integer.parseInt(r.readLine());
) catch (Exception e) (
System.out.println("An error Occurred");
)
)
System.out.println("After Sorting");
System.out.println(Arrays.toString(array));
mergeSort(array, 0, array.length-1);
System.out.println("Before Merge Sorting");
System.out.println(Arrays.toString(array));
)
)

Dans ce programme, nous avons demandé à l'utilisateur d'entrer une entrée. La sortie sera triée en fonction de l'entrée de l'utilisateur.

Production:

5. Tri par tas

Vous devez d'abord connaître le cadre sur lequel Heapsort fonctionne - le tas - afin de comprendre pourquoi il fonctionne. Nous parlerons spécifiquement d'un tas binaire, mais vous pouvez également le généraliser à d'autres constructions de tas. Un tas est un arbre qui remplit la propriété du tas, à savoir que tous ses enfants ont des relations avec chaque nœud. Un tas doit également être presque terminé. Un binaire de profondeur d presque complet a un sous-arbre d-1, avec la même racine, et chaque nœud a un sous-arbre gauche complet, avec un gauche descendant.

En d'autres termes, vous obtenez un nombre de plus en plus faible (min-tas) ou plus grand et plus grand (max-tas) lorsque vous descendez dans l'arborescence. Voici une instance max-heap:

1. 6 1 8 3 5 2 4 : Ici, les deux nombres d'enfants sont plus petits que le parent, donc nous n'avons rien à changer.
2. 6 1 8 3 5 2 4: Ici, 5> 1, nous devons les échanger. Nous devons heapify pour 5.
3. 6 5 8 3 1 2 4: Les deux numéros d'enfants sont plus petits, tout reste le même.
4. 6 5 8 3 1 2 4: Ici, 8> 6, nous devons donc les échanger.
5. 8 5 6 3 1 2 4: Après cette itération, nous obtiendrons ce résultat.

Après avoir répété ce processus, nous obtiendrons les résultats suivants:

• 8 5 6 3 1 2 4

1. 4 5 6 3 1 2 8 : échange
2. 6 5 4 3 1 2 8 : Heapify
3. 2 5 4 3 1 6 8 : échange
4. 5 2 4 2 1 6 8 : Heapify
5. 1 2 4 2 5 6 8 : échange

Code:

public class HeapSort
(
public void sort(int arr())
(
int n = arr.length;
for (int x = n / 2 - 1; x >= 0; x--)
heapify(arr, n, x);
for (int x=n-1; x>=0; x--)
int tmp = arr(0);
arr(0) = arr(x);
arr(x) = tmp;
heapify(arr, x, 0);
)
)
void heapify(int arr(), int n, int x)
(
int largest = x;
int L = 2*x + 1;
int r = 2*x + 2;
if (L arr(largest))
largest = L;
if (r arr(largest))
largest = r;
if (largest != x)
(
int swap = arr(x);
arr(x) = arr(largest);
arr(largest) = swap;
heapify(arr, n, largest);
)
)
static void printArray(int arr())
(
int n = arr.length;
for (int x=0; x System.out.print(arr(x)+" ");
System.out.println();
)
public static void main(String args())
(
int arr() = (6, 1, 8, 3, 5, 2, 4);
int n = arr.length;
System.out.println("Before Sorting:");
printArray(arr);
HeapSort ob = new HeapSort();
ob.sort(arr);
System.out.println("After Heap Sorting:");
printArray(arr);
)
) public class HeapSort
(
public void sort(int arr())
(
int n = arr.length;
for (int x = n / 2 - 1; x >= 0; x--)
heapify(arr, n, x);
for (int x=n-1; x>=0; x--)
int tmp = arr(0);
arr(0) = arr(x);
arr(x) = tmp;
heapify(arr, x, 0);
)
)
void heapify(int arr(), int n, int x)
(
int largest = x;
int L = 2*x + 1;
int r = 2*x + 2;
if (L arr(largest))
largest = L;
if (r arr(largest))
largest = r;
if (largest != x)
(
int swap = arr(x);
arr(x) = arr(largest);
arr(largest) = swap;
heapify(arr, n, largest);
)
)
static void printArray(int arr())
(
int n = arr.length;
for (int x=0; x System.out.print(arr(x)+" ");
System.out.println();
)
public static void main(String args())
(
int arr() = (6, 1, 8, 3, 5, 2, 4);
int n = arr.length;
System.out.println("Before Sorting:");
printArray(arr);
HeapSort ob = new HeapSort();
ob.sort(arr);
System.out.println("After Heap Sorting:");
printArray(arr);
)
)

Production:

Vous pouvez le visualiser du point au niveau du graphique, de gauche à droite. Ce que nous avons réalisé ici, c'est que lorsque nous avons le kème composant dans le tableau, la position de ses enfants est 2 \ * k + 1 et 2 \ * k + 2 (en supposant que l'indexation commence à 0). Vous pouvez surveiller cela. La position du parent est toujours (k-1) / 2 pour le kième composant. Vous pouvez facilement «accumuler au maximum» n'importe quelle plage, car vous le savez. Vérifiez si l'un de ses enfants est inférieur à celui de chaque composant. Si c'est le cas, associez un parent et répétez cette étape récursivement avec le parent.

Remarque: étant donné que l'itération des boucles for sur l'ensemble du tableau crée heapSort) (évidemment O (N), cela créerait la complexité globale de Heapsort O (nlog n). Heapsort a un type sur place, ce qui signifie qu'il nécessite O ( 1) plus d'espace que le tri par fusion, mais il présente certains inconvénients, tels que les parallèles difficiles.

Conclusion - Tri des algorithmes en Java

Le tri est une procédure très répandue avec des jeux de données, que ce soit pour une analyse plus approfondie, pour accélérer la recherche avec des algorithmes plus efficaces reposant sur des informations triées, filtrer les informations, etc. Le tri est approuvé par plusieurs langues et souvent les interfaces obscurcissent ce que fait le programmeur.

Articles recommandés

Ceci est un guide de tri des algorithmes en Java. Ici, nous discutons différents types de tri en Java avec leurs algorithmes. Vous pouvez également consulter nos autres articles suggérés -

1. Fusionner les algorithmes de tri en Java
2. JComboBox en Java
3. StringBuffer en Java
4. JTextField en Java
5. Tri de tas en Python
6. Algorithmes de tri rapide en Java
7. Guide complet de tri en C # avec des exemples
8. Algorithmes de tri en JavaScript
9. Guide d'exemples d'algorithme C ++
10. Guide complet de tri des algorithmes en Python