Sortowanie przez wstawianie: algorytm z C, C++, Java, Python Przykłady
Sara Chen
Co to jest sortowanie przez wstawianie?
Sortowanie przez wstawianie jest jednym z algorytmów sortowania przez porównywanie, który służy do sortowania elementów poprzez iterowanie po jednym elemencie na raz i umieszczanie go we właściwym miejscu.
Każdy element jest sekwencyjnie wstawiany do już posortowanej listy. Rozmiar już posortowanej listy początkowo wynosi jeden. Algorytm sortowania przez wstawianie zapewnia, że pierwszych k elementów zostanie posortowanych po k-tej iteracji.
Charakterystyka algorytmu sortowania przez wstawianie
Algorytm sortowania przez wstawianie ma następujące ważne cechy:
- Jest to stabilna technika sortowania, więc nie zmienia względnej kolejności równych elementów.
- Jest skuteczny w przypadku mniejszych zestawów danych, ale nie jest skuteczny w przypadku większych list.
- Sortowanie przez wstawianie ma charakter adaptacyjny, co zmniejsza całkowitą liczbę kroków, jeśli jest posortowane częściowo. Szyk jest dostarczany jako dane wejściowe, aby był skuteczny.
Jak działa Wstaw Operapraca?
W algorytmie sortowania przez wstawianie operacja wstawiania służy do sortowania nieposortowanych elementów. Pomaga wstawić nowy element do już posortowanej listy.
Pseudokod operacji wstawiania:
Rozważmy listę A złożoną z N elementów.
A[N-1] is the element to be inserted in the sorted sublist A[0..N-2]. For i = N-1 to 1: if A[i] < A[i-1], then swap A[i] and A[i-1] else Stop
W powyższym przykładzie do już posortowanej listy należy wstawić nowy element 6.
Krok 1) W porównaniu z lewym sąsiadującym elementem A[5], 9 > 6, zamieniamy położenie 9 i 6. Teraz element 6 zostaje przeniesiony do A[4].
Krok 2) Teraz porównujemy A[4] i A[3] i stwierdzamy, że A[3] > A[4], ponownie zamieniamy pozycje 6 i 8.
Krok 3) Teraz porównaj A[3] i A[2], ponieważ A[2] > A[3] zamieniają miejscami 7 i 6.
Krok 4) Porównujemy A[1] i A[2] i jako A[1] < A[2], czyli lewy sąsiedni element nie jest już większy. Teraz dochodzimy do wniosku, że liczba 6 została wstawiona poprawnie i w tym miejscu zatrzymujemy algorytm.
Jak działa sortowanie przez wstawianie
Omówiona powyżej operacja wstawiania jest podstawą sortowania przez wstawianie. Procedura wstawiania jest wykonywana na każdym elemencie, a na końcu otrzymujemy posortowaną listę.
Powyższy przykładowy rysunek ilustruje działanie sortowania przez wstawianie w strukturze danych. Początkowo na posortowanej podliście znajduje się tylko jeden element, tj. 4. Po wstawieniu A[1], czyli 3, rozmiar posortowanej podlisty wzrasta do 2.
C++ Program do sortowania przez wstawianie
#include <iostream>
using namespace std;
int main(){
//unsorted list
int unsorted[] = {9,8,7,6,5,4,3,3,2,1};
//size of list
int size_unsorted = sizeof(unsorted) / sizeof(unsorted[0]);
//printing unsorted list
cout << "\nUnsorted: ";
for(int i = 0 ; i < size_unsorted ; i++){
cout << unsorted[i] << " ";
}
int current_element,temp;
for(int i = 1; i < size_unsorted; i++){
current_element = unsorted[i];
for(int j = i-1; j >= 0 && unsorted[j] > current_element; j--){
//swapping if current element is lesser
temp = unsorted[j+1];
unsorted[j+1] = unsorted[j];
unsorted[j] = temp;
}
}
//printing sorted list
cout << "\nSorted: ";
for(int i = 0 ; i < size_unsorted ; i++){
cout << unsorted[i] << " ";
}
return 0;
}
Wyjście:
Unsorted: 9 8 7 6 5 4 3 3 2 1 Sorted: 1 2 3 3 4 5 6 7 8 9
Kod C do sortowania przez wstawianie
#include <stdio.h>
int main() {
//unsorted list
int unsorted[] = {9,8,7,6,5,4,3,3,2,1};
//size of list
int size_unsorted = sizeof(unsorted) / sizeof(unsorted[0]);
//printing unsorted list
printf("\nUnsorted: ");
for(int i = 0 ; i < size_unsorted ; i++){
printf("%d ", unsorted[i]);
}
int current_element, temp;
for(int i = 1; i < size_unsorted; i++){
current_element = unsorted[i];
for(int j = i-1; j >= 0 && unsorted[j] > current_element; j--){
//swapping if current element is lesser
temp = unsorted[j+1];
unsorted[j+1] = unsorted[j];
unsorted[j] = temp;
}
}
//printing sorted list
printf("\nSorted: ");
for(int i = 0 ; i < size_unsorted ; i++){
printf("%d ", unsorted[i]);
}
return 0;
}
Wyjście:
Output: Unsorted: 9 8 7 6 5 4 3 3 2 1 Sorted: 1 2 3 3 4 5 6 7 8 9
Python Program do sortowania przez wstawianie
#unsorted list
unsorted = [9,8,7,6,5,4,3,3,2,1]
#size of list
size_unsorted = len(unsorted)
#printing unsorted list
print("\nUnsorted: ", end="")
for i in range(size_unsorted):
print(unsorted[i], end=" ")
for i in range(1, size_unsorted):
current_element = unsorted[i]
j = i - 1
while j >= 0 and unsorted[j] > current_element:
#swapping if current element is lesser
unsorted[j+1], unsorted[j] = unsorted[j], unsorted[j+1]
j -= 1
#printing sorted list
print("\nSorted: ", end="")
for i in range(size_unsorted):
print(unsorted[i], end=" ")
Wyjście:
Unsorted: 9 8 7 6 5 4 3 3 2 1 Sorted: 1 2 3 3 4 5 6 7 8 9
Właściwości sortowania przez wstawianie
Oto ważne właściwości sortowania przez wstawianie:
- online: Sortowanie przez wstawianie może sortować elementy w miarę ich otrzymywania. Oznacza to, że jeśli posortowaliśmy już listę elementów i dołączyliśmy do list kolejne elementy, to nie musimy od nowa przeprowadzać całej procedury sortowania. Zamiast tego musimy iterować tylko na nowo dodanych elementach.
- W miejscu: Złożoność przestrzenna algorytmu sortowania przez wstawianie jest stała i nie wymaga dodatkowej przestrzeni. Ten algorytm sortuje elementy w miejscu.
- Stabilny: Podczas sortowania przez wstawianie nie zamieniamy elementów, jeśli ich wartości są równe. Na przykład dwa elementy x i y są równe, a x pojawia się przed y na nieposortowanych listach, a następnie na posortowanej liście x pojawia się przed y. Dzięki temu sortowanie przez wstawianie jest stabilne.
- Adaptacyjny: A algorytm sortowania jest adaptacyjny, jeśli zajmuje mniej czasu, jeśli elementy wejściowe lub podzbiór elementów są już posortowane. Jak omówiliśmy powyżej, najlepszy czas wykonania sortowania przez wstawianie wynosi O(N), a najgorszy czas wykonania to O(N^2). Sortowanie przez wstawianie jest jednym z adaptacyjnych algorytmów sortowania.
Złożoność sortowania przez wstawianie
Złożoność przestrzeni
Sortowanie przez wstawianie nie wymaga dodatkowej przestrzeni do sortowania elementów, złożoność przestrzenna jest stała, tj. O(1).
Złożoność czasowa
Ponieważ sortowanie przez wstawianie iteruje każdy element jednocześnie, wymaga N-1 przejść, aby posortować N elementów. W każdym przejściu może wykonać zero zamian, jeśli elementy są już posortowane, lub zamianę, jeśli elementy są ułożone w kolejności malejącej.
- W przypadku przebiegu 1 minimalne wymagane zamiany wynoszą zero, a maksymalne wymagane zamiany wynoszą 1.
- W przypadku przebiegu 2 minimalne wymagane zamiany wynoszą zero, a maksymalne wymagane zamiany wynoszą 2.
- W przypadku przebiegu N minimalna wymagana zamiana wynosi zero, a maksymalna wymagana zamiana wynosi N.
- Minimalna wartość zamiany wynosi zero, więc najlepsza złożoność czasowa wynosi O(N) dla iteracji N przebiegów.
- Łączna liczba zamian wynosi (1+2+3+4+..+N) i. N(N+1)/2, najgorsza złożoność czasowa wynosi O(N^2).
Oto istotna złożoność czasowa sortowania przez wstawianie:
- Najgorszy przypadek złożoności: O(n2): Sortowanie tablicy w porządku malejącym, gdy jest ona w porządku rosnącym, jest najgorszym scenariuszem.
- Najlepsza złożoność przypadku: O(n): Best Case Complexity występuje, gdy tablica jest już posortowana, pętla zewnętrzna działa n razy, podczas gdy pętla wewnętrzna nie działa wcale. Istnieje tylko n porównań. Tak więc w tym przypadku złożoność jest liniowa.
- Średnia złożoność przypadku: O(n2): Dzieje się tak, gdy elementy tablicy występują w pomieszanej kolejności, która nie jest ani rosnąca, ani malejąca.
Podsumowanie
- Sortowanie przez wstawianie to metoda algorytmu sortowania oparta na porównaniu.
- Jest to stabilna technika sortowania, więc nie zmienia względnej kolejności równych elementów.
- W każdym elemencie operacja wstawiania służy do wstawienia elementu do posortowanej podlisty.
- Sortowanie przez wstawianie to algorytm sortowania w miejscu.
- Najgorsza i przeciętna złożoność czasowa sortowania przez wstawianie jest kwadratowa, tj. O(N^2).
- Sortowanie przez wstawianie nie wymaga dodatkowej przestrzeni.
