Sortowanie przez wstawianie

Chcemy napisać metodę, która posortuje nam przekazany jako parametr wektor liczb całkowitych metodą sortowania przez wstawianie. Sortowanie przez wstawianie polega na podziale wektora na dwie części, część posortowaną i część nieposortowaną. Bierzemy element z części nieposortowanej i wstawiamy na odpowiednie miejsce w części posortowanej (analogia z układaniem kart w dłoni).

/**
 * Sortowanie przez wstawianie
 * @author kodatnik.blogspot.com 
 */ 
public class SortowaniePrzezWstawianie {
 
 // metoda sortuje elementy tablicy przekazanej jako parametr
 public static void sortowaniePrzezWstawianie(int[] wejscie) {

  // pobieramy elementy z części nieposortowanej tablicy
  for (int i = 1; i < wejscie.length; i++) {
   // zapisujemy element w zmiennej
   int liczba = wejscie[i];
   // oraz jego indeks w tablicy
   int j = i;   
   // w pętli "robimy" dla niego miejsce w
   // posortowanej części tablicy
   while (( j > 0) && (wejscie[j-1] > liczba)) {
    wejscie[j] = wejscie[j-1];
    j--;
   }
   // wstawiamy go na odpowiednie miejsce
   wejscie[j] = liczba;
  }
 }
 
 // metoda wyświetla zawartość tablicy przekazanej jako parametr na ekranie
 public static void pokazTablice(int[] wejscie) {
  // każdy element znajdujący się w tablicy wyświetlamy na ekranie
  for(int x : wejscie) System.out.print (x + " ");
  System.out.println ();
 }

 public static void main(String[] args) {
  // tworzymy tablicę wypełniając ją od razu danymi
  int[] tablica = {4, 6, 1, 2, 3, 8, 7, 9, 5};
  
  // wyświetlamy tablicę na ekranie
  pokazTablice(tablica);
  // sortujemy tablicę
  sortowaniePrzezWstawianie(tablica);
  // wyświetlamy posortowaną tablicę na ekranie
  pokazTablice(tablica);  
 }
}

Algorytm wstawienia elementu na odpowiednie miejsce można zoptymalizować stosując wyszukiwanie binarne.

Uruchomiona aplikacja:

4 6 1 2 3 8 7 9 5 
1 2 3 4 5 6 7 8 9