zadania z informatyki - Analiza algorytmów

Sortowanie przez wstawianie polega na powtarzaniu operacji wstawiania elementu do już uporządkowanego ciągu. Aby znaleźć w uporządkowanym ciągu miejsce, w które należy wstawić nowy element, można stosować różne strategie. Poniższy algorytm znajduje to miejsce metodą wyszukiwania binarnego.

Specyfikacja

Dane:
n — liczba naturalna oznaczająca długość ciągu,
A[1..n] — ciąg liczb całkowitych zapisanych w tablicy
Wynik:
A[1..n] — tablica liczb całkowitych, w której liczby zostały ustawione w porządku niemalejącym

Algorytm
dla j = n – 1, n – 2, … , 1 wykonuj
x ← A[j]
p ← j
k ← n + 1
dopóki k – p > 1 wykonuj
i ← (p + k) div 2
jeżeli x ≤ A[i]
k ← i
w przeciwnym razie
p ← i
dla i = j, j + 1, … , p – 1 wykonuj
A[i] ← A[i + 1]
A[p] ← x