Sortowanie przez wstawianie

Spis odnośników

Sortowanie przez wstawianie – prosty i skuteczny algorytm

#Algorytm sortowania przez wstawianie (ang. insertion sort) to jeden z podstawowych algorytmów sortujących, który jest często używany przy niewielkich zbiorach danych lub w sytuacjach, gdy dane są prawie posortowane. Jego prostota i intuicyjność sprawiają, że jest on łatwy do zrozumienia i zaimplementowania.

Jak działa sortowanie przez wstawianie?

Algorytm działa podobnie do tego, jak ludzie sortują karty. Zaczynamy od pierwszego elementu, który uznajemy za posortowany, a następnie kolejno „wstawiamy” każdy kolejny element w odpowiednie miejsce w już posortowanej części listy.

Algorytm zaczyna od drugiego elementu (bo pierwszy jest już posortowany).
Porównuje ten element z elementami wcześniej posortowanymi, przesuwając je, jeśli są większe.
Gdy znajdzie odpowiednią pozycję dla elementu, wstawia go w to miejsce.
Proces powtarza się dla kolejnych elementów, aż cała lista będzie posortowana.

Złożoność obliczeniowa

Najlepszy przypadek (dla prawie posortowanej listy) to O(n).
Najgorszy przypadek (dla odwrotnie posortowanej listy) to O(n²).

Zastosowania

Sortowanie przez wstawianie działa dobrze na małych zbiorach danych i w przypadku, gdy dane są częściowo uporządkowane. Jest też często używane jako część bardziej zaawansowanych algorytmów, np. algorytmu #sortowanie hybrydowe (Timsort), który korzysta z sortowania przez wstawianie dla małych partii danych.

Sortowanie przez wstawianie – prosty i skuteczny algorytm

Algorytm sortowania przez wstawianie (ang. insertion sort) to jeden z podstawowych algorytmów sortujących, który jest często używany przy niewielkich zbiorach danych lub w sytuacjach, gdy dane są prawie posortowane. Jego prostota i intuicyjność sprawiają, że jest on łatwy do zrozumienia i zaimplementowania.

Jak działa sortowanie przez wstawianie?

Algorytm zaczyna od drugiego elementu (bo pierwszy jest już posortowany).
Porównuje ten element z elementami wcześniej posortowanymi, przesuwając je, jeśli są większe.
Gdy znajdzie odpowiednią pozycję dla elementu, wstawia go w to miejsce.
Proces powtarza się dla kolejnych elementów, aż cała lista będzie posortowana.

Złożoność obliczeniowa

Najlepszy przypadek (dla prawie posortowanej listy) to O(n).
Najgorszy przypadek (dla odwrotnie posortowanej listy) to O(n²).

Zastosowania

Sortowanie przez wstawianie działa dobrze na małych zbiorach danych i w przypadku, gdy dane są częściowo uporządkowane. Jest też często używane jako część bardziej zaawansowanych algorytmów, np. algorytmu sortowania hybrydowego (Timsort), który korzysta z sortowania przez wstawianie dla małych partii danych.

Implementacja algorytmu sortowania przez wstawianie

Kod sortowania przez wstawianie w #Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14

def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr

# Przykład użycia:
arr = [12, 11, 13, 5, 6]
sorted_arr = insertion_sort(arr)
print("Posortowana lista:", sorted_arr)

2. Kod sortowania przez wstawianie w #JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3. Kod sortowania przez wstawianie w #Pascal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

program InsertionSort;

procedure InsertionSort(var arr: array of Integer; n: Integer);
var
i, key, j: Integer;
begin
for i := 1 to n - 1 do
begin
key := arr[i];
j := i - 1;

while (j >= 0) and (arr[j] > key) do
begin
arr[j + 1] := arr[j];
j := j - 1;
end;
arr[j + 1] := key;
end;
end;

var
arr: array[1..5] of Integer = (12, 11, 13, 5, 6);
i: Integer;
begin
InsertionSort(arr, Length(arr));

Write('Posortowana lista: ');
for i := 1 to Length(arr) do
Write(arr[i], ' ');
end.

4. Kod sortowania przez wstawianie w #PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

<?php
function insertionSort($arr) {
for ($i = 1; $i < count($arr); $i++) {
$key = $arr[$i];
$j = $i - 1;
while ($j >= 0 && $arr[$j] > $key) {
$arr[$j + 1] = $arr[$j];
$j--;
}
$arr[$j + 1] = $key;
}
return $arr;
}

// Przykład użycia:
$arr = array(12, 11, 13, 5, 6);
$sorted_arr = insertionSort($arr);
echo "Posortowana lista: " . implode(", ", $sorted_arr);
?>

Podsumowanie

Algorytm sortowania przez wstawianie to prosty, ale skuteczny sposób na uporządkowanie danych. Choć nie jest najszybszy w przypadku dużych zbiorów danych, to świetnie sprawdza się przy mniejszych zadaniach i w sytuacjach, gdzie dane są wstępnie uporządkowane. Jego intuicyjna konstrukcja sprawia, że jest chętnie używany w wielu projektach edukacyjnych i praktycznych.