Jednym z podstawowych algorytmów, które musi znać każdy z początkujących programistów, jest sortowanie przez wstawianie (insertion sort). Ten właśnie algorytm oraz jego implementację, poznamy w tej części „Piątku z sortowaniem”.
Jak to działa?
Zasada funkcjonowania tego algorytmu przedstawia się w następujący sposób. Każdą iterację zaczynamy od wybrania elementu (startując od pierwszego miejsca w tablicy), który będziemy przyrównywać, do elementów znajdujących się na pozycjach poprzedzających. Jeżeli element znajdujący się przed wybranym przez nas elementem jest większy, przesuwamy się o jedno miejsce wstecz.
Robimy tak, aż do momentu, gdy znajdziemy się na pozycji, w której element poprzedzający jest mniejszy, lub dojdziemy do początku tablicy. Wybrany element wstawiamy na tą właśnie pozycję. Wszystkie elementy, znajdujące się przed jego wcześniejszą pozycją, przesuwamy o jedną pozycję w głąb tablicy. Następnie powtarzamy ten proces, dla kolejnych elementów w tablicy, aż rozpatrzymy ostatni jej element.
Karciany porządek
Zasady działania tego sortowania, mogą brzmieć nieco chaotycznie, lecz każdy z nas może zobrazować sobie działanie tego algorytmu, na prostej sytuacji z życia codziennego. Wyobraźmy sobie, że podczas gry w karty dobraliśmy właśnie króla, piątkę, damę, dwójkę i dziewiątkę.
By za każdym razem nie szukać kart w swojej ręce, chcemy je posortować. Na początku bierzemy więc piątkę i przekładamy ją na sam początek. Króla zastawiamy na miejscu, ponieważ piątka która znajduje się przed nim, ma
mniejszą wartość. Kolejna, przeniesiona zostaje dama. Ląduje na miejscu między piątką, a królem. W następnym kroku bierzemy dwójkę i przenosimy ją na sam początek, po czym dziewiątkę wstawiamy pomiędzy piątkę i damę.
Poniżej zobaczycie wizualizację procesu sortowania przez wstawianie, na przykładzie omówionym powyżej:
W taki sposób posortowaliśmy właśnie wszystkie karty na naszej ręce. Czy to nie proste? Ponoć, to właśnie sposób w jaki ludzie układają karty w ręce podczas gry, był inspiracją dla tego algorytmu.
Sortowanie przez wstawianie – Implementacje
C++
//program do sortowania n-elementowej tablicy
//przy pomocy algorytmu sortowania przez wstawianie
//Jan Żwirek
#include <iostream>
using namespace std;
void printTab(int *tab, int n);
void insertionSort(int *tab, int n) {
for (int x = 1; x < n; x++) {
//Wybieramy element który chcemy porównywać
int selectedElement = tab[x];
int y;
//Rozpoczynamy przesuwanie elementów szukając miesjca docelowego
//dla wybranego przez nas elementu
for (y = x - 1; (selectedElement < tab[y]) && (y >= 0); y--) {
tab[y + 1] = tab[y];
}
cout << "\nKrok " << x - 1 << ": Przenoszenie elementu " << selectedElement;
cout << " z pozycji " << x << " na pozycje " << y+1 << endl;
tab[y + 1] = selectedElement;
printTab(tab, n);
}
}
int main() {
int n;
cout << "Wprowadz liczbe elementow tablicy: ";
cin >> n;
//Dynamiczne tworzenie tablicy
int *tab = new int[n];
cout << "\nWprowadz " << n << " liczb do posortowania" << endl;
cout << "Zatwierdz kazda z nich klawiszem Enter:" << endl;
for (int x = 0; x < n; x++) {
cin >> tab[x];
}
cout << endl << "Tablica przed posortowaniem:" << endl;
printTab(tab, n);
cout << endl << "Rozpoczecie sortowania" << endl;
insertionSort(tab, n);
cout << endl << "Oto tablica po sortowaniu:" << endl;
printTab(tab, n);
delete[] tab;
system("pause");
return 0;
}
void printTab(int *tab, int n) {
cout << endl;
for (int x = 0; x < n; x++) {
cout << tab[x] << " | ";
}
cout << endl;
}Java
package matura;
import java.util.Scanner;
public class Main {
private static void printArray(int[] tab) {
System.out.println();
for(int i = 0; i < tab.length; i++)
{
System.out.print(tab[i] + " | ");
}
System.out.println();
}
private static void insertionSort(int[] tab) {
for (int x = 1; x < tab.length; x++) {
//Wybieramy element który chcemy porównywać
int selectedElement = tab[x];
int y;
//Rozpoczynamy przesuwanie elementów szukając miejsca docelowego
//dla wybranego przez nas elementu
for (y = x-1; (y >= 0) &&(selectedElement < tab[y]); y--) {
tab[y + 1] = tab[y];
}
System.out.println("\nKrok " + (x-1) + ": Przenoszenie elementu " + selectedElement + " z pozycji " + x + " na pozycje " + (y+1));
tab[y + 1] = selectedElement;
printArray(tab);
}
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in); //inicjalizujemy Scanner - obiekt pozwalajacy na wczytywanie zmiennych od uzytkownika
System.out.println("Wprowadz liczbe elementow tablicy: ");
int n = sc.nextInt();
int[] arr = new int[n];
for(int i = 0; i < n; i++) {
System.out.println("Podaj element nr." + i + ": ");
arr[i]= sc.nextInt(); //wczytujemy kolejne elementy tablicy
}
System.out.println("Oto wprowadzona tablica:");
printArray(arr);
insertionSort(arr);
System.out.println("Oto wprowadzona tablica po przesortowaniu:");
printArray(arr);
sc.close(); //zwalniamy zasoby
}
}Python
def wypisz(tab): #tworzymy metode do wypiswania zawartosci naszej tablicy
for el in tab:
print(el, end=" | ")
def sortuj_wstaw(tab, n): #tworzymy metode do sortowania poprzez wstawianie
for x in range(1, n):
selected = tab[x] #aktualnie wybrany element
y = x-1 #przygotowujemy iteracje poprzez pozostale elementy
while y >= 0 and selected < tab[y]: #dopoki nie znajdziemy elementu mniejszego od wybranego i nie natrafimy na poczatek tablicy
tab[y+1] = tab[y] #zamieniamy elementy miejscami
y -= 1 #modyfikujemy zmienna iteracyjna
print("\nKrok ", (x-1), ": przenoszenie elementu ", selected, " z pozycji ", x, " na pozycje ", (y+1))
tab[y+1] = selected #po znalezieniu mniejszego elementu, zamieniamy go z wybranym
wypisz(tab)
print("Podaj ilosc elementow tablicy:")
a = int(input())
tablica = []
for i in range(a):
print("Podaj element nr. ", (i+1))
tablica.append(int(input()))
print("Oto twoja tablica:")
wypisz(tablica)
sortuj_wstaw(tablica, a)
print("Oto twoja tablica po sortowaniu:")
wypisz(tablica)Złożoność
Algorytm sortowania przez wstawianie, tak jak większość prostszych algorytmów, posiada złożoność rzędu O(n2). Taka wartość złożoności czasowej nie należy do najniższych i jest identyczna, jak algorytmu sortowania bąbelkowego.
Nie mniej jednak, algorytm ten ma swoje zalety. Oprócz łatwej implementacji, radzi on sobie bardzo dobrze z niedużymi tablicami. Ponadto algorytm ten, w przeciwieństwie algorytmu sortowania przez wybór, jest algorytmem stabilnym. Co to jednak oznacza?
Algorytmy stabilne cechują się tym, że jeśli w zbiorze znajdowały się elementy o identycznej wartości, to po posortowaniu tego zbioru będą ustawione w takiej samej kolejności, jaką miały w zbiorze nieposortowanym. Przykładowo mając zbiór [3, 2a, 5, 2b, 1], po posortowaniu go algorytmem niestabilnym, możemy otrzymać: [1, 2b, 2a, 3, 5]. Korzystając z algorytmu stabilnego, zawsze otrzymamy następujący zbiór: [1, 2a, 2b, 3, 5].
Podsumowanie
Znając już zasadę działania oraz przykładową implementację, wykonaliście kolejny krok, w kierunku pełnego przygotowania do matury z informatyki. Jeśli chcecie poznać kolejne algorytmy sortowania oraz ich implementację, zapraszam was za tydzień na kolejną część „Piątku z sortowaniem”. Ukarze się on, jak zwykle, na waszym ulubionym serwisie binarnie.pl 😉.
Ciekawy wpis, fajny przykład z kartami ;)
Dziękuję za docenienie pracy :)