Sortowanie przez wstawianie to prosty algorytm sortowania, który działa poprzez iteracyjne wstawianie każdego elementu nieposortowanej listy na właściwe miejsce w posortowanej części listy. To jest stabilne sortowanie algorytm, co oznacza, że ​​elementy o równych wartościach zachowują względny porządek w posortowanym wyniku.

Sortowanie przez wstawianie jest jak sortowanie kart do gry w twoich rękach. Karty dzielisz na dwie grupy: karty posortowane i karty nieposortowane. Następnie wybierasz kartę z nieposortowanej grupy i umieszczasz ją w odpowiednim miejscu w posortowanej grupie.

Algorytm sortowania przez wstawianie:

Sortowanie przez wstawianie to prosty algorytm sortowania, który działa poprzez budowanie posortowanej tablicy po jednym elemencie na raz. Uważa się, że w miejscu algorytm sortowania, co oznacza, że ​​nie wymaga dodatkowej przestrzeni w pamięci poza oryginalną tablicą.

przechodzenie przez pocztę

Algorytm:

Aby uzyskać sortowanie przez wstawianie, wykonaj następujące kroki:

• Musimy zacząć od drugiego elementu tablicy, ponieważ zakłada się, że pierwszy element tablicy jest posortowany.
• Porównaj drugi element z pierwszym elementem i sprawdź, czy drugi element jest mniejszy, a następnie zamień je.
• Przejdź do trzeciego elementu i porównaj go z drugim elementem, następnie z pierwszym elementem i zamień go w razie potrzeby, aby umieścić go we właściwej pozycji wśród pierwszych trzech elementów.
• Kontynuuj ten proces, porównując każdy element z poprzednimi i zamieniając je w razie potrzeby, aby umieścić go we właściwej pozycji wśród posortowanych elementów.
• Powtarzaj, aż cała tablica zostanie posortowana.

Działanie algorytmu sortowania przez wstawianie:

Rozważmy tablicę zawierającą elementy : {23, 1, 10, 5, 2}

Pierwsze przejście:

• Obecny element to 23
• Zakłada się, że pierwszy element tablicy jest posortowany.
• Posortowana część do 0 indeks to: [23]

Drugie przejście:

• Porównywać 1 z 23 (bieżący element z posortowaną częścią).
• Od 1 jest mniejszy, wstaw 1 zanim 23 .
• Posortowana część do 1 indeks to: [1, 23]

Trzecie przejście:

• Porównywać 10 z 1 I 23 (bieżący element z posortowaną częścią).
• Od 10 jest większy niż 1 i mniejszy niż 23 , wstawić 10 między 1 I 23 .
• Posortowana część do 2 indeks to: [1, 10, 23]

Czwarte przejście:

• Porównywać 5 z 1 , 10 , I 23 (bieżący element z posortowaną częścią).
• Od 5 jest większy niż 1 i mniejszy niż 10 , wstawić 5 między 1 I 10 .
• Posortowana część do 3 indeks jest : [1, 5, 10, 23]

Piąta przepustka:

• Porównywać 2 z 1, 5, 10 , I 23 (bieżący element z posortowaną częścią).
• Od 2 jest większy niż 1 i mniejszy niż 5 wstawić 2 między 1 I 5 .
• Posortowana część do 4 indeks to: [1, 2, 5, 10, 23]

Ostateczny układ:

• Posortowana tablica to: [1, 2, 5, 10, 23]

Implementacja sortowania przez wstawianie:

// C++ program for insertion sort #include  using namespace std; // Function to sort an array using // insertion sort void insertionSort(int arr[], int n) {  int i, key, j;  for (i = 1; i < n; i++) {  key = arr[i];  j = i - 1;  // Move elements of arr[0..i-1],  // that are greater than key,   // to one position ahead of their  // current position  while (j>= 0 && arr[j]> klucz) { arr[j + 1] = arr[j];  j = j - 1;  } arr[j + 1] = klucz;  } } // Funkcja narzędziowa umożliwiająca wydrukowanie tablicy // o rozmiarze n void printArray(int arr[], int n) { int i;  dla (i = 0; tj< n; i++)  cout << arr[i] << ' ';  cout << endl; } // Driver code int main() {  int arr[] = { 12, 11, 13, 5, 6 };  int N = sizeof(arr) / sizeof(arr[0]);  insertionSort(arr, N);  printArray(arr, N);  return 0; } // This is code is contributed by rathbhupendra>

// C program for insertion sort #include  #include  /* Function to sort an array using insertion sort*/ void insertionSort(int arr[], int n) {  int i, key, j;  for (i = 1; i < n; i++) {  key = arr[i];  j = i - 1;  /* Move elements of arr[0..i-1], that are  greater than key, to one position ahead  of their current position */  while (j>= 0 && arr[j]> klucz) { arr[j + 1] = arr[j];  j = j - 1;  } arr[j + 1] = klucz;  } } // Funkcja narzędziowa umożliwiająca wydrukowanie tablicy o rozmiarze n void printArray(int arr[], int n) { int i;  dla (i = 0; tj< n; i++)  printf('%d ', arr[i]);  printf('
'); } /* Driver program to test insertion sort */ int main() {  int arr[] = { 12, 11, 13, 5, 6 };  int n = sizeof(arr) / sizeof(arr[0]);  insertionSort(arr, n);  printArray(arr, n);  return 0; }>

// Java program for implementation of Insertion Sort public class InsertionSort {  /*Function to sort array using insertion sort*/  void sort(int arr[])  {  int n = arr.length;  for (int i = 1; i < n; ++i) {  int key = arr[i];  int j = i - 1;  /* Move elements of arr[0..i-1], that are  greater than key, to one position ahead  of their current position */  while (j>= 0 && arr[j]> klucz) { arr[j + 1] = arr[j];  j = j - 1;  } arr[j + 1] = klucz;  } } /* Funkcja narzędziowa do drukowania tablicy o rozmiarze n*/ static void printArray(int arr[]) { int n = arr.length;  for (int i = 0; tj< n; ++i)  System.out.print(arr[i] + ' ');  System.out.println();  }  // Driver method  public static void main(String args[])  {  int arr[] = { 12, 11, 13, 5, 6 };  InsertionSort ob = new InsertionSort();  ob.sort(arr);  printArray(arr);  } }; /* This code is contributed by Rajat Mishra. */>

# Python program for implementation of Insertion Sort # Function to do insertion sort def insertionSort(arr): # Traverse through 1 to len(arr) for i in range(1, len(arr)): key = arr[i] # Move elements of arr[0..i-1], that are # greater than key, to one position ahead # of their current position j = i-1 while j>= 0 i klucz< arr[j] : arr[j + 1] = arr[j] j -= 1 arr[j + 1] = key # Driver code to test above arr = [12, 11, 13, 5, 6] insertionSort(arr) for i in range(len(arr)): print ('% d' % arr[i]) # This code is contributed by Mohit Kumra>

// C# program for implementation of Insertion Sort using System; class InsertionSort {  // Function to sort array  // using insertion sort  void sort(int[] arr)  {  int n = arr.Length;  for (int i = 1; i < n; ++i) {  int key = arr[i];  int j = i - 1;  // Move elements of arr[0..i-1],  // that are greater than key,  // to one position ahead of  // their current position  while (j>= 0 && arr[j]> klucz) { arr[j + 1] = arr[j];  j = j - 1;  } arr[j + 1] = klucz;  } } // Funkcja narzędziowa do drukowania // tablicy o rozmiarze n static void printArray(int[] arr) { int n = arr.Length;  for (int i = 0; tj< n; ++i)  Console.Write(arr[i] + ' ');  Console.Write('
');  }  // Driver Code  public static void Main()  {  int[] arr = { 12, 11, 13, 5, 6 };  InsertionSort ob = new InsertionSort();  ob.sort(arr);  printArray(arr);  } } // This code is contributed by ChitraNayal.>

>

 // PHP program for insertion sort // Function to sort an array // using insertion sort function insertionSort(&$arr, $n) { for ($i = 1; $i < $n; $i++) { $key = $arr[$i]; $j = $i-1; // Move elements of arr[0..i-1], // that are greater than key, to  // one position ahead of their  // current position while ($j>= 0 && $arr[$j]> $klucz) { $arr[$j + 1] = $arr[$j]; $j = $j - 1; } $arr[$j + 1] = $klucz; } } // Funkcja narzędziowa umożliwiająca // wydrukowanie tablicy o rozmiarze n funkcja printArray(&$arr, $n) { for ($i = 0; $i< $n; $i++) echo $arr[$i].' '; echo '
'; } // Driver Code $arr = array(12, 11, 13, 5, 6); $n = sizeof($arr); insertionSort($arr, $n); printArray($arr, $n); // This code is contributed by ChitraNayal. ?>>

5 6 11 12 13>

Złożoność czasowa: O(N^2)
Przestrzeń pomocnicza: O(1)

Analiza złożoności sortowania przez wstawianie :

Złożoność czasowa sortowania przez wstawianie

• Najlepszy przypadek: NA) , Jeśli lista jest już posortowana, gdzie n jest liczbą elementów na liście.
• Przeciętny przypadek: NA ² ) , Jeśli lista jest uporządkowana losowo
• Najgorszy przypadek: NA ² ) , Jeśli lista jest w odwrotnej kolejności

Złożoność przestrzeni sortowania przez wstawianie

• Przestrzeń pomocnicza: O(1), wymaga sortowania przez wstawianie O(1) dodatkową przestrzeń, dzięki czemu jest to algorytm sortowania oszczędzający przestrzeń.

Zalety sortowania przez wstawianie:

• Proste i łatwe do wdrożenia.
• Stabilny algorytm sortowania.
• Skuteczne w przypadku małych list i prawie posortowanych list.
• Oszczędność miejsca.

Niedogodności sortowania przez wstawianie:

• Nieefektywne w przypadku dużych list.
• W większości przypadków nie jest tak skuteczny jak inne algorytmy sortowania (np. sortowanie przez scalanie, sortowanie szybkie).

Aplikacje sortowania przez wstawianie:

Sortowanie przez wstawianie jest powszechnie stosowane w sytuacjach, gdy:

• Lista jest niewielka lub prawie posortowana.
• Ważna jest prostota i stabilność.

Często zadawane pytania dotyczące sortowania przez wstawianie

Pytanie 1. Jakie są przypadki graniczne algorytmu sortowania przez wstawianie?

zaktualizuj w sql za pomocą łączenia

Sortowanie przez wstawianie zajmuje maksymalny czas, jeśli elementy są sortowane w odwrotnej kolejności. I zajmuje to minimum czasu (kolejność n), gdy elementy są już posortowane.

Pytanie 2. Jaki jest paradygmat algorytmiczny algorytmu sortowania przez wstawianie?

3d w autocadzie

Algorytm sortowania przez wstawianie wykorzystuje podejście przyrostowe.

Pytanie 3. Czy sortowanie przez wstawianie jest algorytmem sortowania w miejscu?

Tak, sortowanie przez wstawianie jest algorytmem sortowania w miejscu.

Pytanie 4. Czy sortowanie przez wstawianie jest stabilnym algorytmem?

Tak, sortowanie przez wstawianie jest stabilnym algorytmem sortowania.

Pytanie 5. Kiedy używany jest algorytm sortowania przez wstawianie?

Sortowanie przez wstawianie stosuje się, gdy liczba elementów jest mała. Może się to również przydać, gdy tablica wejściowa jest prawie posortowana i w całej dużej tablicy tylko kilka elementów zostało błędnie rozmieszczonych.