Sortowanie przez wstawianie (ang. insertion sort) to prosty i efektywny algorytm sortowania, który działa dobrze dla małych zbiorów danych lub w przypadku, gdy dane są prawie posortowane. Algorytm ten działa na zasadzie budowania posortowanej tablicy jeden element na raz, poprzez wstawianie każdego nowego elementu w odpowiednie miejsce.
Opis metody sortowania przez wstawianie
Sortowanie przez wstawianie działa w sposób podobny do sortowania kart w ręku. Zaczynamy od drugiego elementu w tablicy i porównujemy go z elementami przed nim, przesuwając większe elementy w prawo, aż znajdziemy właściwe miejsce dla bieżącego elementu. Proces ten jest powtarzany dla wszystkich elementów w tablicy.
Algorytm sortowania przez wstawianie
- Rozpocznij od drugiego elementu tablicy (indeks 1).
- Porównaj bieżący element z elementami przed nim:
- Jeśli bieżący element jest mniejszy od elementu przed nim, zamień je miejscami.
- Powtarzaj ten krok, przesuwając się wstecz przez tablicę, aż znajdziesz odpowiednie miejsce dla bieżącego elementu.
- Przejdź do następnego elementu i powtórz kroki 2 i 3, aż do końca tablicy.
Przykład sortowania przez wstawianie
Tablica do posortowania [5, 3, 8, 4, 2]
Początkowa tablica: [5, 3, 8, 4, 2]
i = 1, klucz = 3:
5 > 3, więc przesuwamy 5 w prawo, wynik [5, 5, 8, 4, 2]
Wstawiamy 3 na miejsce 5, wynik [3, 5, 8, 4, 2]
i = 2, klucz = 8:
8 > 5, więc pozostawiamy bez zmian, wynik [3, 5, 8, 4, 2]
i = 3, klucz = 4:
8 > 4, więc przesuwamy 8 w prawo, wynik [3, 5, 8, 8, 2]
5 > 4, więc przesuwamy 5 w prawo, wynik [3, 5, 5, 8, 2]
Wstawiamy 4 na miejsce 5, wynik [3, 4, 5, 8, 2]
i = 4, klucz = 2:
8 > 2, więc przesuwamy 8 w prawo, wynik [3, 4, 5, 8, 8]
5 > 2, więc przesuwamy 5 w prawo, wynik [3, 4, 5, 5, 8]
4 > 2, więc przesuwamy 4 w prawo, wynik [3, 4, 4, 5, 8]
3 > 2, więc przesuwamy 3 w prawo, wynik [3, 3, 4, 5, 8]
Wstawiamy 2 na miejsce 3, wynik [2, 3, 4, 5, 8]
Złożoność obliczeniowa sortowania przez wstawianie
W najgorszym przypadku O(n²) (kiedy tablica jest posortowana w odwrotnej kolejności)
W najlepszym przypadku O(n) (kiedy tablica jest już posortowana)
Średnia złożoność O(n²)
Zalety i wady sortowania przez wstawianie
Zalety
- Prosty do zaimplementowania i zrozumienia.
- Działa efektywnie dla małych zbiorów danych.
- Bardzo wydajny, gdy tablica jest prawie posortowana.
- Algorytm jest stabilny (nie zmienia kolejności elementów o tych samych wartościach).
Wady
- Nieefektywny dla dużych zbiorów danych.
- Złożoność O(n²) w najgorszym przypadku.
Sortowanie przez wstawianie, mimo swoich ograniczeń, jest często używane w praktyce do sortowania małych zbiorów danych lub jako część bardziej złożonych algorytmów sortowania, takich jak sortowanie hybrydowe.
Implementacje sortowania przez wstawianie w różnych językach
Sortowanie przez wstawianie w języku C++
#include <iostream>
using namespace std;
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
int main() {
int arr[] = {5, 3, 8, 4, 2};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Nieposortowana tablica: ";
printArray(arr, n);
insertionSort(arr, n);
cout << "Posortowana tablica: ";
printArray(arr, n);
return 0;
}
Sortowanie przez wstawianie w języku Python
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
def print_array(arr):
for i in arr:
print(i, end=" ")
print()
# Przykładowa tablica
arr = [5, 3, 8, 4, 2]
print("Nieposortowana tablica:", end=" ")
print_array(arr)
insertion_sort(arr)
print("Posortowana tablica:", end=" ")
print_array(arr)
Sortowanie przez wstawianie w języku Java
public class InsertionSort {
static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
static void printArray(int[] arr) {
for (int i : arr) {
System.out.print(i + " ");
}
System.out.println();
}
public static void main(String[] args) {
int[] arr = {5, 3, 8, 4, 2};
System.out.println("Nieposortowana tablica:");
printArray(arr);
insertionSort(arr);
System.out.println("Posortowana tablica:");
printArray(arr);
}
}
Sortowanie przez wstawianie w języku JavaScript
function insertionSort(arr) {
let n = arr.length;
for (let i = 1; i < n; i++) {
let key = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
function printArray(arr) {
console.log(arr.join(" "));
}
// Przykładowa tablica
let arr = [5, 3, 8, 4, 2];
console.log("Nieposortowana tablica:");
printArray(arr);
insertionSort(arr);
console.log("Posortowana tablica:");
printArray(arr);
Ww. implementacje w różnych językach programowania działają zgodnie z algorytmem sortowania przez wstawianie, przedstawionym wcześniej.
Komentarze