Sortowanie przez wstawianie – algorytm i implementacje w C++, Java i Python

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.

Więcej ciekawych algorytmów znajdziesz w tym tytule

Sortowanie przez wstawianie – Implementacje

C++

//program do sortowania n-elementowej tablicy
//przy pomocy algorytmu sortowania przez wstawianie
//Jan Żwirek

#include &lt;iostream>

using namespace std;
void printTab(int *tab, int n);

void insertionSort(int *tab, int n) {

	for (int x = 1; x &lt; 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 &lt; tab[y]) &amp;&amp; (y >= 0); y--) {
			tab[y + 1] = tab[y];
		}

		cout &lt;&lt; "\nKrok " &lt;&lt; x - 1 &lt;&lt; ": Przenoszenie elementu " &lt;&lt; selectedElement;
		cout &lt;&lt; " z pozycji " &lt;&lt; x &lt;&lt; " na pozycje " &lt;&lt; y+1 &lt;&lt; endl;
		tab[y + 1] = selectedElement;
		printTab(tab, n);
	}
}


int main() {
	int n;

	cout &lt;&lt; "Wprowadz liczbe elementow tablicy: ";
	cin >> n;

	//Dynamiczne tworzenie tablicy
	int *tab = new int[n];

	cout &lt;&lt; "\nWprowadz " &lt;&lt; n &lt;&lt; " liczb do posortowania" &lt;&lt; endl; 
	cout &lt;&lt; "Zatwierdz kazda z nich klawiszem Enter:" &lt;&lt; endl;

	for (int x = 0; x &lt; n; x++) {
		cin >> tab[x];
	}

	cout &lt;&lt; endl &lt;&lt; "Tablica przed posortowaniem:" &lt;&lt; endl;
	printTab(tab, n);

	cout &lt;&lt; endl &lt;&lt; "Rozpoczecie sortowania" &lt;&lt; endl;
	insertionSort(tab, n);

	cout &lt;&lt; endl &lt;&lt; "Oto tablica po sortowaniu:" &lt;&lt; endl;

	printTab(tab, n);

	delete[] tab;
	system("pause");
	return 0;

}

void printTab(int *tab, int n) {
	cout &lt;&lt; endl;
	for (int x = 0; x &lt; n; x++) {
		cout &lt;&lt; tab[x] &lt;&lt; " | ";
	}
	cout &lt;&lt; endl;
}

//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 &lt; tab.length; i++)
		{
			System.out.print(tab[i] + " | ");
		}
		System.out.println();
	}
	private static void insertionSort(int[] tab) {
		for (int x = 1; x &lt; 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) &amp;&amp;(selectedElement &lt; 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 &lt; 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
	}
		
		
	
		
	
	
}

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 &lt; 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)

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(n²). 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 😉.

Binarnie.pl

Sortowanie przez wstawianie – algorytm i implementacje w C++, Java i Python

Jak to działa?

Karciany porządek

Sortowanie przez wstawianie – Implementacje

C++

Java

Python

Złożoność

Podsumowanie

You Might Also Like

Jak wyjść z Vim

Praktyki w Scythe Studio

Praca zdalna jako junior

2 komentarze

Marek

Jan Żwirek

Dodaj komentarz Anuluj pisanie odpowiedzi