Insertion Sort algoritme in Java: Duidelijk voorbeeld & stapsgewijze handleiding

Wat is het Insertion Sort algoritme?

Insertion sort is een eenvoudige sorteertechniek ideaal voor kleine of bijna gesorteerde datasets. In elke iteratie verwijdert het algoritme een element, vergelijkt het met de voorgaande elementen en plaatst het op de juiste positie.

Insertion sort werkt in O(n²) tijd in het slechtste en gemiddelde geval, maar bereikt lineaire prestaties wanneer de array al gesorteerd is. Het is een in-place, stabiele sorteer die alleen constante extra ruimte vereist.

Insertion Sort algoritme proces

Hier is een visuele weergave van de insertion sort workflow:

Insertion Sort algoritme proces

Java-programma voorbeeld om een array te sorteren met Insertion Sort algoritme:

package com.guru99; public class InsertionSortVoorbeeld { public static void main(String a[]) { int[] mijnArray = {860,8,200,9}; System.out.println("Voor Insertion Sort"); printArray(mijnArray); insertionSort(mijnArray);//array sorteren met insertion sort System.out.println("Na Insertion Sort"); printArray(mijnArray); } public static void insertionSort(int arr[]) { int n = arr.length; for (int i = 1; i < n; i++) { System.out.println("Sorteerpas nummer "+(i)); int key = arr[i]; int j = i-1; while ( (j > -1) && ( arr [j] > key ) ) { System.out.println("Vergelijken "+ key + " en " + arr [j]); arr [j+1] = arr [j]; j--; } arr[j+1] = key; System.out.println("Elementen verwisselen: Nieuwe array na wissel"); printArray(arr); } } static void printArray(int[] array){ for(int i=0; i < array.length; i++) { System.out.print(array[i] + " "); } System.out.println(); } } 

Code-uitvoer:

Voor Insertion Sort 860 8 200 9 Sorteerpas nummer 1 Vergelijken 8 en 860 Elementen verwisselen: Nieuwe array na wissel 8 860 200 9 Sorteerpas nummer 2 Vergelijken 200 en 860 Elementen verwisselen: Nieuwe array na wissel 8 200 860 9 Sorteerpas nummer 3 Vergelijken 9 en 860 Vergelijken 9 en 200 Elementen verwisselen: Nieuwe array na wissel 8 9 200 860 Na Insertion Sort 8 9 200 860