Разница между сортировкой вставкой и сортировкой по выбору
В этой статье мы обсудим разницу между сортировкой вставкой и сортировкой выбора:
Сортировка вставкой - это простой алгоритм сортировки, который работает аналогично тому, как вы сортируете игральные карты в руках. Массив виртуально разделен на отсортированную и несортированную части. Значения из неотсортированной части выбираются и помещаются в правильное положение в отсортированной части.
Алгоритм:
Чтобы отсортировать массив размера n в порядке возрастания:
- Перейдите от arr [1] к arr [n] по массиву.
- Сравните текущий элемент (ключ) с его предшественником.
- Если ключевой элемент меньше своего предшественника, сравните его с предыдущими элементами. Переместите большие элементы на одну позицию вверх, чтобы освободить место для замененного элемента.
Ниже приведено изображение, иллюстрирующее сортировку вставкой:
Ниже представлена программа для того же:
C ++
// C++ program for the insertion sort #include <bits/stdc++.h> 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] > key) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = key; } } // Function to print an array of size N void printArray( int arr[], int n) { int i; // Print the array for (i = 0; i < 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]); // Function Call insertionSort(arr, N); printArray(arr, N); return 0; } |
Джава
// 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 < 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] > key) { arr[j + 1 ] = arr[j]; j = j - 1 ; } arr[j + 1 ] = key; } } // Function to print an array of size N static void printArray( int arr[], int n) { int i; // Print the array for (i = 0 ; i < n; i++) { System.out.print(arr[i] + " " ); } System.out.println(); } // Driver code public static void main(String[] args) { int arr[] = { 12 , 11 , 13 , 5 , 6 }; int N = arr.length; // Function Call insertionSort(arr, N); printArray(arr, N); } } // This code is contributed by 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] > key): 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 < 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] > key) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = key; } } // Function to print an array of size N static void printArray( int [] arr, int n) { int i; // Print the array for (i = 0; i < n; i++) { Console.Write(arr[i] + " " ); } Console.WriteLine(); } // Driver code static public void Main() { int [] arr = new int [] { 12, 11, 13, 5, 6 }; int N = arr.Length; // Function Call insertionSort(arr, N); printArray(arr, N); } } // This code is contributed by Dharanendra LV |
5 6 11 12 13
Алгоритм сортировки по выбору сортирует массив, многократно находя минимальный элемент (с учетом возрастающего порядка) из неотсортированной части и помещая его в начало. Алгоритм поддерживает два подмассива в данном массиве.
- Подмассив уже отсортирован.
- Остающийся несортированный подмассив.
На каждой итерации сортировки выбора выбирается минимальный элемент (с учетом порядка возрастания) из несортированного подмассива и перемещается в отсортированный подмассив.
Ниже приведен пример, объясняющий вышеуказанные шаги:
arr [] = 64 25 12 22 11 // Находим минимальный элемент в arr [0 ... 4] // и поместим в начало 11 25 12 22 64 // Находим минимальный элемент в arr [1 ... 4] // и поместите его в начало arr [1 ... 4] 11 12 25 22 64 // Находим минимальный элемент в arr [2 ... 4] // и поместите его в начало arr [2 ... 4] 11 12 22 25 64 // Находим минимальный элемент в arr [3 ... 4] // и поместите его в начало arr [3 ... 4] 11 12 22 25 64
Ниже представлена программа для того же:
C ++
// C++ program for implementation of // selection sort #include <bits/stdc++.h> 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 < n - 1; i++) { // Find the minimum element // in unsorted array min_idx = i; for (j = i + 1; j < n; j++) if (arr[j] < arr[min_idx]) 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 < size; 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 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 < n - 1 ; i++) { // Find the minimum element // in unsorted array min_idx = i; for (j = i + 1 ; j < n; j++) if (arr[j] < arr[min_idx]) 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 < size; 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] < arr[min_idx]): 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 #
// 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 < n - 1; i++) { // Find the minimum element // in unsorted array min_idx = i; for (j = i + 1; j < n; j++) if (arr[j] < arr[min_idx]) 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 < size; 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 |
Отсортированный массив: 11 12 22 25 64
Табличная разница между сортировкой вставкой и сортировкой по выбору: Вставка сортировки Выбор Сортировка 1. Вставляет значение в предварительно отсортированный массив для сортировки набора значений в массиве. Находит минимальное / максимальное число из списка и сортирует его в порядке возрастания / убывания. 2. Это стабильный алгоритм сортировки. Это нестабильный алгоритм сортировки. 3. Лучшая временная сложность - O (N), когда массив уже находится в порядке возрастания. Не существует лучшего случая, когда временная сложность составляет O (N 2 ) во всех случаях. 4. Количество операций сравнения, выполняемых в этом алгоритме сортировки, меньше, чем выполняемая подкачка. Количество операций сравнения, выполняемых в этом алгоритме сортировки, больше, чем выполненная замена. 5. Это более эффективно, чем сортировка «Выборка». Он менее эффективен, чем сортировка вставкой. 6. Здесь элемент известен заранее, и мы ищем правильную позицию для его размещения. Место, куда нужно поместить элемент, заранее известно, мы ищем элемент, который нужно вставить в эту позицию.
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.