Sortowanie przez wstawianie | Korepetycje do matury z informatyki - Maurycy Gast

Sortowanie przez wstawianie

Jednym z podstawowych algorytmów sortujących, który każdy uczeń powinien znać, jest sortowanie przez wstawianie. Algorytm można porównać do układania kart z talii w ręce. Polega on na tym, że wybieramy kolejny element, a następnie ustawiamy go w już posortowanym fragmencie ciągu.

Na samym początku, ustalamy że pierwszy element w tablicy jest uporządkowany. Następnie wybieramy drugi w naszej tablicy i ustawiamy odpowiednio przed lub za pierwszym elementem w zależności od wielkości. Potem postępujemy analogicznie z trzecim elementem, ustawiając go odpowiednio względem pierwszego i drugiego.

Sortowanie przez wstawianie – na czym polega?

Do zainicjowania funkcji na sortowanie przez wstawianie potrzeba dwóch pętli przechodzących po tablicy, zatem nie powinno być zaskoczeniem, że złożoność tego algorytmu będzie rzędu O(n2) (czyli kwadratowa). Jednak jest on częściej używany niż sortowanie bąbelkowe czy sortowanie przez wybieranie. Dlaczego tak się dzieje, skoro wszystkie te trzy algorytmy mają podobne złożoności?

sortowanie przez wstawianie c++
Aby zainicjować funkcję na sortowanie przez wstawianie potrzeba dwóch pętli przechodzących po tablicy.

Otóż popatrzmy na sytuację, gdy nasza tablica przed wykonaniem algorytmu jest już poprawnie ułożona. Sortowanie przez wybieranie jak i sortowanie bąbelkowe będą w całości wykonywać obie pętle zawarte w ich kodzie, przez co układanie posortowanej już tablicy będzie miało ciągle złożoność kwadratową. Aby temu zapobiec, należy umieścić w kodzie specjalne zabezpieczenie, które dla danych posortowanych nie wykona niepotrzebnych operacji.

Co w przypadku z sortowaniem przez wstawianie? Łatwo zauważyć, że jeśli chcemy dla uogólnienia problemu uporządkować trzeci element z pierwszymi dwoma, to skoro tablica jest posortowana to pętla zatrzyma się po pierwszym porównaniu trzeciego elementu z drugim i nie będzie iść dalej w głąb tablicy. Co z tego wynika? Jeśli każdy element w tablicy będziemy porównywać tylko raz z jego poprzednikiem to okaże się, że w takim przypadku będziemy mieli złożoność rzędu O(n) (czyli liniową). Jest to diametralna różnica i przewaga sortowania przez wstawianie nad sortowaniem bąbelkowym i przez wybieranie. Co więcej, warto również wspomnieć, że  sortowanie przez wstawianie jest też używane do przyspieszenia działania szybkiego sortowania. Gdy w tablicy jest mało elementów (z reguły określa się to na około 20) to wtedy zastępuje się sortowanie szybkie sortowaniem przez wstawianie, ponieważ działa szybciej, zaś w optymistycznym przypadku podania tablicy uporządkowanej lub prawie uporządkowanej zadziała najlepiej.

Skoro już znamy idee, działanie oraz złożoność algorytmu sortowania przez wstawianie możemy przejść do implementacji kodu. Pod spodem zamieszczam dwie wersje: sortowanie przez wstawianie C++ oraz sortowanie przez wstawianie Python:

Sortowanie przez wstawianie – C++:

void  insertionSort(int[] array, int n)
{
	int i, j, temp;
	for(i=1; i<n; i++)
	{
		temp=array[i];
		j=i-1;
		while(j>=0 && array[j]>temp)
		{	
array[j+1]=array[j];
			j--;
		}
		array[j+1]=temp;
	}
}

Sortowanie przez wstawianie – Python:

def instertionSort(array):
	for i in range(1,len(array):
		temp=array[i];
		j=i-1;
		while j>=0 and array[j]>temp:
			array[j+1]=array[j]
			j-=1
		array[j+1]=temp

Wpisy, które mogą Cię zainteresować:



Dodaj komentarz

kurs maturalny informatyka