Сортування вставленням і сортування виділенням є двома популярними алгоритмами сортування, і їх основна відмінність полягає в тому, як вони вибирають і розміщують елементи у відсортованій послідовності.
Сортування вибору:
- Під час сортування вибором вхідний масив ділиться на дві частини: відсортовану та невідсортовану.
- Алгоритм неодноразово знаходить мінімальний елемент у невідсортованій частині та міняє його місцями з крайнім лівим елементом невідсортованої частини, таким чином розширюючи відсортовану частину на один елемент.
- Сортування вибору має часову складність O(n^2) у всіх випадках.
Сортування вставки:
- При сортуванні вставкою вхідний масив також ділиться на дві частини: відсортовану та невідсортовану.
Алгоритм вибирає елемент із невідсортованої частини та розміщує його в правильному положенні у відсортованій частині, зрушуючи більші елементи на одну позицію вправо.
Сортування вставленням має часову складність O(n^2) у гіршому випадку, але може працювати краще на частково відсортованих масивах із найкращою часовою складністю O(n).
Основні відмінності: - Сортування вибором сканує невідсортовану частину, щоб знайти мінімальний елемент, а сортування вставкою сканує відсортовану частину, щоб знайти правильну позицію для розміщення елемента.
Сортування вибором вимагає менше замін, ніж сортування вставкою, але більше порівнянь.
Сортування за допомогою вставки є більш ефективним, ніж сортування за вибором, коли вхідний масив відсортований частково або майже відсортований, тоді як сортування за вибором працює краще, коли масив сильно не відсортований.
Підсумовуючи, обидва алгоритми мають однакову часову складність, але методи їх вибору та розміщення відрізняються. Вибір між ними залежить від характеристик вхідних даних і конкретних вимог проблеми, що розглядається.
Переваги сортування вставкою:
- Простий і легкий для розуміння та реалізації.
- Ефективно для невеликих наборів даних або майже відсортованих даних.
- Алгоритм сортування на місці, тобто не вимагає додаткової пам’яті.
- Стабільний алгоритм сортування, тобто підтримує відносний порядок рівних елементів у вхідному масиві.
Недоліки сортування вставкою:
- Неефективно для великих наборів даних або зворотно впорядкованих даних із найгіршою часовою складністю O(n^2).
- Сортування вставленням має багато свопів, що може сповільнювати роботу на сучасних комп’ютерах.
Переваги Selection Sort:
- Простий і легкий для розуміння та реалізації.
- Ефективно для невеликих наборів даних або майже відсортованих даних.
- Алгоритм сортування на місці, тобто не вимагає додаткової пам’яті.
Недоліки Selection Sort:
- Неефективно для великих наборів даних із найгіршою часовою складністю O(n^2).
- Сортування вибору має багато порівнянь, що може уповільнити його на сучасних комп’ютерах.
- Нестабільний алгоритм сортування, тобто він може не підтримувати відносний порядок рівних елементів у вхідному масиві.
У цій статті ми обговоримо різницю між сортуванням вставленням і сортуванням виділенням:
Сортування вставкою це простий алгоритм сортування, який працює подібно до того, як ви сортуєте гральні карти у своїх руках. Масив практично розбитий на відсортовану та невідсортовану частини. Значення з невідсортованої частини вибираються та розміщуються в правильному місці в відсортованій частині.
Алгоритм:
Щоб відсортувати масив розміром n у порядку зростання:
- Ітерація від arr[1] до arr[n] по масиву.
- Порівняти поточний елемент (ключ) з його попередником.
- Якщо ключовий елемент менший за свого попередника, порівняйте його з попередніми елементами. Перемістіть більші елементи на одну позицію вгору, щоб звільнити місце для поміняних елементів.
Нижче наведено зображення для ілюстрації сортування вставкою:
Нижче наведено програму для того ж:
C++
// C++ program for the 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 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]> ключ) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = ключ; } } // Функція для друку масиву розміром N void printArray(int arr[], int n) { int i; // Надрукувати масив for (i = 0; i cout<< arr[i] << ' '; } cout << endl; } // Driver Code int main() { int arr[] = { 12, 11, 13, 5, 6 }; int N = sizeof(arr) / sizeof(arr[0]); // Function Call insertionSort(arr, N); printArray(arr, N); return 0; }> |
>
>
Java
// Java program for the above approach> import> java.util.*;> class> GFG> {> > // Function to sort an array using> // insertion sort> static> void> insertionSort(>int> arr[],>int> n)> {> >int> i, key, j;> >for> (i =>1>; 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]> ключ) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = ключ; } } // Функція для друку масиву розміром N static void printArray(int arr[], int n) { int i; // Надрукувати масив для (i = 0; i System.out.print(arr[i] + ' '); } System.out.println(); } // Код драйвера public static void main(String[ ] args) { int arr[] = { 12, 11, 13, 5, 6 }; // Виклик функції insertionSort(arr, N); Цей код надано code_hunt> |
>
>
Python3
# Python 3 program for the insertion sort> # Function to sort an array using> # insertion sort> def> insertionSort(arr, n):> >i>=> 0> >key>=> 0> >j>=> 0> >for> i>in> range>(>1>,n,>1>):> >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> and> arr[j]>ключ):>> >arr[j>+> 1>]>=> arr[j]> >j>=> j>-> 1> >arr[j>+> 1>]>=> key> # Function to print an array of size N> def> printArray(arr, n):> >i>=> 0> ># Print the array> >for> i>in> range>(n):> >print>(arr[i],end>=> ' '>)> >print>(>'
'>,end>=> '')> # Driver Code> if> __name__>=>=> '__main__'>:> >arr>=> [>12>,>11>,>13>,>5>,>6>]> >N>=> len>(arr)> ># Function Call> >insertionSort(arr, N)> >printArray(arr, N)> > ># This code is contributed by bgangwar59.> |
>
>
C#
// C# program for the above approach> using> System;> class> GFG> {> >// Function to sort an array using> >// insertion sort> >static> void> insertionSort(>int>[] arr,>int> n)> >{> >int> i, key, j;> >for> (i = 1; 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]> ключ) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = ключ; } } // Функція для друку масиву розміром N static void printArray(int[] arr, int n) { int i; // Надрукувати масив для (i = 0; i { Console.Write(arr[i] + ' '); } Console.WriteLine(); } // Код драйвера static public void Main() { int[] arr = new int[] { 12, 11, 13, 5, 6 }; int N = arr.Length; // Виклик функції insertionSort(arr, N); printArray(arr, N); внесок Dharanendra L V> |
>
>
Javascript
> // JavaScript program for the above approach> // Function to sort an array using> // insertion sort> function> insertionSort(arr,n)> {> >let i, key, j;> >for> (i = 1; 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]> ключ) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = ключ; } } // Функція друку масиву розміром N function printArray(arr,n) { let i; // Надрукувати масив для (i = 0; i document.write(arr[i] + ' '); } document.write(' '); } // Код драйвера let arr=[12, 11 , 13, 5, 6]; // Виклик функції: printArray (arr, N); // Цей код створено avanitrachhadiya2155> |
>
>Вихід:
5 6 11 12 13>
The сортування вибору Алгоритм сортує масив шляхом повторного знаходження мінімального елемента (з огляду на зростання) з невідсортованої частини та розміщення його на початку. Алгоритм підтримує два підмасиви в заданому масиві.
- Підмасив уже відсортовано.
- Решту підмасиву не відсортовано.
У кожній ітерації сортування вибору мінімальний елемент (у порядку зростання) з невідсортованого підмасиву вибирається та переміщується до відсортованого підмасиву.
Нижче наведено приклад, який пояснює описані вище дії.
arr[] = 64 25 12 22 11 // Find the minimum element in arr[0...4] // and place it at beginning 11 25 12 22 64 // Find the minimum element in arr[1...4] // and place it at beginning of arr[1...4] 11 12 25 22 64 // Find the minimum element in arr[2...4] // and place it at beginning of arr[2...4] 11 12 22 25 64 // Find the minimum element in arr[3...4] // and place it at beginning of arr[3...4] 11 12 22 25 64>
Нижче наведено програму для того ж:
C++
// C++ program for implementation of> // selection sort> #include> using> namespace> std;> // Function to swap two number> void> swap(>int>* xp,>int>* yp)> {> >int> temp = *xp;> >*xp = *yp;> >*yp = temp;> }> // Function to implement the selection> // sort> void> selectionSort(>int> arr[],>int> n)> {> >int> i, j, min_idx;> >// One by one move boundary of> >// unsorted subarray> >for> (i = 0; i // Find the minimum element // in unsorted array min_idx = i; for (j = i + 1; j if (arr[j] min_idx = j; // Swap the found minimum element // with the first element swap(&arr[min_idx], &arr[i]); } } // Function to print an array void printArray(int arr[], int size) { int i; for (i = 0; i cout << arr[i] << ' '; } cout << endl; } // Driver Code int main() { int arr[] = { 64, 25, 12, 22, 11 }; int n = sizeof(arr) / sizeof(arr[0]); // Function Call selectionSort(arr, n); cout << 'Sorted array:
'; // Print the array printArray(arr, n); return 0; }> |
>
>
Java
// Java program for implementation of> // selection sort> import> java.util.*;> class> GFG> {> // Function to implement the selection> // sort> static> void> selectionSort(>int> arr[],>int> n)> {> >int> i, j, min_idx;> >// One by one move boundary of> >// unsorted subarray> >for> (i =>0>; i 1; i++) { // Find the minimum element // in unsorted array min_idx = i; for (j = i + 1; j if (arr[j] min_idx = j; // Swap the found minimum element // with the first element int temp = arr[min_idx]; arr[min_idx]= arr[i]; arr[i] = temp; } } // Function to print an array static void printArray(int arr[], int size) { int i; for (i = 0; i System.out.print(arr[i]+ ' '); } System.out.println(); } // Driver Code public static void main(String[] args) { int arr[] = { 64, 25, 12, 22, 11 }; int n = arr.length; // Function Call selectionSort(arr, n); System.out.print('Sorted array:
'); // Print the array printArray(arr, n); } } // This code is contributed by aashish1995> |
>
>
Python3
# Python3 program for implementation of> # selection sort> # Function to implement the selection> # sort> def> selectionSort(arr, n):> ># One by one move boundary of> ># unsorted subarray> >for> i>in> range>(n>-> 1>):> ># Find the minimum element> ># in unsorted array> >min_idx>=> i> >for> j>in> range>(i>+> 1>, n):> >if> (arr[j] min_idx = j # Swap the found minimum element # with the first element arr[min_idx], arr[i] = arr[i], arr[min_idx] # Function to print an array def printArray(arr, size): for i in range(size): print(arr[i], end = ' ') print() # Driver Code if __name__ == '__main__': arr = [64, 25, 12, 22, 11] n = len(arr) # Function Call selectionSort(arr, n) print('Sorted array: ') # Print the array printArray(arr, n) # This code is contributed by ukasp> |
>
>
C#
конвертувати об'єкт java в json
// C# program for implementation of> // selection sort> using> System;> public> class> GFG> {> // Function to implement the selection> // sort> static> void> selectionSort(>int> []arr,>int> n)> {> >int> i, j, min_idx;> >// One by one move boundary of> >// unsorted subarray> >for> (i = 0; i { // Find the minimum element // in unsorted array min_idx = i; for (j = i + 1; j if (arr[j] min_idx = j; // Swap the found minimum element // with the first element int temp = arr[min_idx]; arr[min_idx]= arr[i]; arr[i] = temp; } } // Function to print an array static void printArray(int []arr, int size) { int i; for (i = 0; i Console.Write(arr[i]+ ' '); } Console.WriteLine(); } // Driver Code public static void Main(String[] args) { int []arr = { 64, 25, 12, 22, 11 }; int n = arr.Length; // Function Call selectionSort(arr, n); Console.Write('Sorted array:
'); // Print the array printArray(arr, n); } } // This code is contributed by gauravrajput1> |
>
>
Javascript
> // Javascript program for implementation of> // selection sort> // Function to implement the selection> // sort> function> selectionSort(arr, n)> {> >let i, j, min_idx;> > >// One by one move boundary of> >// unsorted subarray> >for>(i = 0; i { // Find the minimum element // in unsorted array min_idx = i; for(j = i + 1; j if (arr[j] min_idx = j; // Swap the found minimum element // with the first element let temp = arr[min_idx]; arr[min_idx]= arr[i]; arr[i] = temp; } } // Function to print an array function printArray(arr, size) { let i; for(i = 0; i { document.write(arr[i] + ' '); } document.write(' '); } // Driver Code let arr = [ 64, 25, 12, 22, 11 ]; let n = arr.length; // Function Call selectionSort(arr, n); document.write('Sorted array: '); // Print the array printArray(arr, n); // This code is contributed by rag2127> |
>
>Вихід:
Sorted array: 11 12 22 25 64>
Таблична різниця між сортуванням вставленням і сортуванням вибору:
| Сортування вставкою | Сортування вибору | |
|---|---|---|
| 1. | Вставляє значення в попередньо відсортований масив для сортування набору значень у масиві. | Знаходить мінімальне/максимальне число зі списку та сортує його в порядку зростання/спадання. |
| 2. | Це стабільний алгоритм сортування. | Це нестійкий алгоритм сортування. |
| 3. | Оптимальна часова складність становить Ω(N), коли масив уже знаходиться в порядку зростання. Він має Θ(N2) у гіршому та середньому випадку. | Для найкращого, гіршого випадку та середнього сортування вибірки мають складність Θ(N2). |
| 4. | Кількість операцій порівняння, виконаних у цьому алгоритмі сортування, менша, ніж виконана заміна. | Кількість операцій порівняння, виконаних у цьому алгоритмі сортування, перевищує кількість виконаних замін. |
| 5. | Це ефективніше, ніж сортування вибором. | Він менш ефективний, ніж сортування вставкою. |
| 6. | Тут елемент відомий заздалегідь, і ми шукаємо правильну позицію для їх розміщення. | Розташування, куди потрібно розмістити елемент, відоме раніше, ми шукаємо елемент для вставки в цю позицію. |
| 7. | Сортування вставкою використовується, коли:
| Сортування вибору використовується, коли
|
| 8. | Сортування вставкою є адаптивним, тобто ефективним для наборів даних, які вже значною мірою відсортовані: часова складність O (кн) коли кожен елемент у вхідних даних не перевищує k місця подалі від свого відсортованого положення | Сортування вибором — це алгоритм сортування порівняння на місці |