Implementacja algorytmu sortowania przez wstawianie w języku C++

Naszym zadaniem jest napisanie programu, który posortuje podaną przez użytkownika tablicę n liczb naturalnych, używając algorytmu sortowania przez wstawianie.

Załączamy niezbędną bibliotekę i zapisujemy funkcję main().

#include <iostream>
using namespace std;

int main() {

}

Tworzymy cztery zmienne. Pierwsza z nich to zmienna tab, która jest tablicą przechowującą n liczb całkowitych. Druga to zmienna n przechowująca rozmiar tablicy tab. Kolejne dwie zmienne to zmienne pomocnicze pom oraz j.

W zmiennej pom będzie tymczasowo przechowywany analizowany element tablicy.

#include <iostream>
using namespace std;

int main() {

	int tab[] = {15, 9, 7, -1, 1, 2, 3, 4, 8, 5, 7, 3, 3, 0, -3};
	int n = sizeof(tab)/sizeof(tab[0]);
	int pom;
	int j;

}

Aby posortować tablicę, konieczne jest przeiterowanie po jej elementach. W tym celu zapiszemy pętlę for, która wykona się o jeden raz mniej niż wynosi liczba elementów do posortowania. Zatem początkowa wartość zmiennej i wynosi 1. Pętla for wykonuje się, dopóki nie zostaną posortowane wszystkie elementy tablicy (czyli i < n).

#include <iostream>
using namespace std;

int main() {

	int tab[] = {15, 9, 7, -1, 1, 2, 3, 4, 8, 5, 7, 3, 3, 0, -3};
	int n = sizeof(tab)/sizeof(tab[0]);
	int pom;
	int j;

	for (int i = 1; i < n; i++) {

	}

}

W pętli for zmiennej pom przypiszemy wartość elementu tablicy tab o indeksie i, natomiast wartość zmiennej j ustawimy na i - 1.

W zmiennej j będziemy przechowywać indeksy poszczególnych elementów znajdujących się w lewej części tablicy (czyli tych, które porównujemy z elementem przechowywanym w zmiennej pom).

#include <iostream>
using namespace std;

int main() {

	int tab[] = {15, 9, 7, -1, 1, 2, 3, 4, 8, 5, 7, 3, 3, 0, -3};
	int n = sizeof(tab)/sizeof(tab[0]);
	int pom;
	int j;

	for (int i = 1; i < n; i++) {

		pom = tab[i];
		j = i - 1;

	}

}

Następnie definiujemy pętlę wewnętrzną while, która będzie wykonywana, dopóki spełnione będą naraz dwa warunki (warunki połączone operatorem logicznym &&).

Pierwszy warunek to j >= 0. Oznacza porównanie wartości elementów wszystkich  tablicy z wartością przechowywaną przez zmienną pom.

W momencie, gdy warunek nie będzie już spełniony (j < 0), będzie to oznaczać, że każda liczba w posortowanej części tablicy została porównana z wartością zmiennej pom i była od niej mniejsza, czyli dotarliśmy na początek tablicy.

Drugi warunek (tab[j] > pom) sprawdza, czy element tablicy tab o indeksie j jest większy od elementu, którego wartość jest przechowywana w zmiennej pom. Jeśli warunki są spełnione, wykonywane jest przesunięcie elementu na miejsce j + 1.

#include <iostream>
using namespace std;

int main() {

	int tab[] = {15, 9, 7, -1, 1, 2, 3, 4, 8, 5, 7, 3, 3, 0, -3};
	int n = sizeof(tab)/sizeof(tab[0]);
	int pom;
	int j;

	for (int i = 1; i < n; i++) {

		pom = tab[i];
		j = i - 1;

		while (j >= 0 && tablica[j] > a) {

		}

	}

}

W pętli while przypisujemy elementowi tablicy tab o indeksie j + 1 wartość elementu o indeksie j. Wykonujemy tę operację, by mieć możliwość zapisania wartości wstawianego elementu do części posortowanej, nie tracąc danych. Pętla jest wykonywana do momentu odnalezienia odpowiedniego miejsca w tablicy dla wstawianego elementu lub do momentu, gdy natrafimy na początek tablicy (czyli j = 0).

Zmniejszamy wartość zmiennej j o jeden i przechodzimy do ponownego sprawdzenia warunku pętli.

Ostatnią operacją wykonywaną w pętli for jest podstawienie w miejsce zmiennej zapisanej pod indeksem j + 1 wartości zmiennej pomocniczej pom. W ten sposób wstawiamy obecnie sprawdzaną liczbę na odpowiednie miejsce.

#include <iostream>
using namespace std;

int main() {

	int tab[] = {15, 9, 7, -1, 1, 2, 3, 4, 8, 5, 7, 3, 3, 0, -3};
	int n = sizeof(tab)/sizeof(tab[0]);
	int pom;
	int j;

	for (int i = 1; i < n; i++) {

		pom = tab[i];
		j = i - 1;

		while (j >= 0 && tab[j] > pom) {
			tab[j + 1] = tab[j];
			--j;
		}
	tab[j + 1] = pom;
	}

}

Tym samym posortowaliśmy tablicę liczb przez wstawianie. Teraz pozostaje wypisać posortowaną tablicę za pomocą pętli for.

Oto kod całego programu:

#include <iostream>
using namespace std;

int main() {

	int tab[] = {15, 9, 7, -1, 1, 2, 3, 4, 8, 5, 7, 3, 3, 0, -3};
	int n = sizeof(tab)/sizeof(tab[0]);
	int pom;
	int j;

	for (int i = 1; i < n; i++) {

		pom = tab[i];
		j = i - 1;

		while (j >= 0 && tab[j] > pom) {
			tab[j + 1] = tab[j];
			--j;
		}
	tab[j + 1] = pom;
	}

	for (int i = 0; i < n; i++) 
		cout << tab[i] << " ";
}

Przetestujmy działanie programu dla przykładowych danych.

Wynik działania programu:

-3 -1 0 1 2 3 3 3 4 5 7 7 8 9 15

Porównania

Liczba potrzebnych porównań elementów tablicy jest wyrażona wzorami:

• przypadek optymistyczny: $n-1$,

• przypadek pesymistyczny: $\frac{1}{2}(n^2 - n)$.

Uwaga! Dwa porównania na początku pętli while liczymy jako jedno.

Słownik