introduction sorting techniques c
Перелік різних методів сортування в C ++.
Сортування - це техніка, яка застосовується для упорядкування даних у певному порядку. Сортування потрібне для того, щоб дані, які ми використовуємо, були в певному порядку, щоб ми могли легко отримати необхідну інформацію з купи даних.
Якщо дані недоглянуті та відсортовані, коли нам потрібна певна інформація, тоді нам доведеться кожен раз шукати її по одному, щоб отримати дані.
=> Прочитайте серію навчальних програм Easy C ++.
Таким чином, завжди доцільно зберігати наші дані в певному порядку, щоб пошук інформації, а також інші операції, що виконуються над даними, могли виконуватися легко та ефективно.
Ми зберігаємо дані у формі записів. Кожен запис складається з одного або декількох полів. Коли кожен запис має унікальне значення певного поля, ми називаємо його ключовим полем. Наприклад, в класі Roll No може бути унікальним або ключовим полем.
як побудувати java проект в eclipse - -
Ми можемо сортувати дані за певним ключовим полем, а потім упорядковувати їх за зростанням / збільшенням чи за спаданням / зменшенням.
Так само, у телефонному словнику кожен запис складається з імені людини, адреси та номера телефону. При цьому номер телефону є унікальним або ключовим полем. Ми можемо сортувати дані словника за цим телефонним полем. Крім того, ми також можемо сортувати дані чисельно чи буквено-цифрово.
Коли ми можемо налаштувати дані для сортування в самій основній пам'яті без потреби в іншій допоміжній пам'яті, тоді ми називаємо це як Внутрішнє сортування .
З іншого боку, коли нам потрібна допоміжна пам’ять для зберігання проміжних даних під час сортування, тоді ми називаємо техніку як Зовнішнє сортування .
У цьому підручнику ми детально вивчимо різні методи сортування на C ++.
Що ви дізнаєтесь:
Методи сортування в C ++
C ++ підтримує різні методи сортування, перелічені нижче.
Сортування бульбашок
Сортування за бульбашками - це найпростіша техніка, при якій ми порівнюємо кожен елемент із сусіднім елементом і поміняємо місцями елементи, якщо вони не в порядку. Таким чином, наприкінці кожної ітерації (що називається пропуском) найважчий елемент потрапляє в кінці списку.
Нижче наведено приклад сортування бульбашок.
Масив для сортування:
Як видно вище, оскільки це невеликий масив і майже відсортований, нам вдалося отримати повністю відсортований масив за кілька проходів.
Давайте застосуємо техніку сортування міхурів на мові C ++.
#include using namespace std; int main () { int i, j,temp; int a(5) = {10,2,0,43,12}; cout <<'Input list ...
'; for(i = 0; i<5; i++) { cout < Вихід:
Список введення…
10 2 0 43 12
Відсортований список елементів ...
0 2 10 12 43
Як видно з результату, у техніці сортування бульбашок, з кожним проходом найважчий елемент барботується до кінця масиву, тим самим сортуючи масив повністю.
Сортування вибору
Це проста, але проста у реалізації техніка, в якій ми знаходимо найменший елемент у списку та ставимо його на належне місце. На кожному проході вибирається наступний найменший елемент і розміщується у відповідному положенні.
Візьмемо той самий масив, що і в попередньому прикладі, і виконаємо Selection Sort для сортування цього масиву.
Як показано на наведеній вище ілюстрації, для N кількості елементів ми беремо проходи N-1, щоб повністю відсортувати масив. В кінці кожного проходу найменший елемент масиву розміщується у відповідному положенні у відсортованому масиві.
Далі, давайте реалізуємо Сортування вибору за допомогою C ++.
#include using namespace std; int findSmallest (int(),int); int main () { int myarray(5) = {12,45,8,15,33}; int pos,temp; cout<<'
Input list of elements to be Sorted
'; for(int i=0;i<5;i++) { cout< Вихід:
Вхідний список елементів для сортування
12 45 8 15 33
Відсортований список елементів -
8 12 15 33 45
При сортуванні виділення при кожному проходженні найменший елемент масиву розміщується у відповідному положенні. Отже, наприкінці процесу сортування ми отримуємо повністю відсортований масив.
Сортування вставки
Сортування вставки - це техніка, при якій ми починаємо з другого елемента списку. Ми порівнюємо другий елемент з попереднім (1вул) і розмістіть його на потрібному місці. Під час наступного проходу для кожного елемента ми порівнюємо його з усіма попередніми елементами та вставляємо цей елемент у належне йому місце.
Вищезазначені три методи сортування прості та легкі у реалізації. Ці методи добре працюють, коли розмір списку менший. У міру збільшення списку ці методи не виконують настільки ефективно.
Методика стане зрозумілою, зрозумівши наступну ілюстрацію.
Масив для сортування має такий вигляд:
Тепер для кожного проходу ми порівнюємо поточний елемент з усіма його попередніми елементами. Таким чином, під час першого проходу ми починаємо з другого елемента.
Отже, нам потрібно N кількість проходів, щоб повністю сортувати масив, що містить N кількість елементів.
Давайте реалізуємо техніку Insertion Sort за допомогою C ++.
#include using namespace std; int main () { int myarray(5) = { 12,4,3,1,15}; cout<<'
Input list is
'; for(int i=0;i<5;i++) { cout < Вихід:
Список вводу:
12 4 3 1 15
Відсортований список -
1 3 4 12 15
Наведений вище результат показує повний відсортований масив із використанням сортування вставки.
Швидке сортування
Quicksort - найефективніший алгоритм, який можна використовувати для сортування даних. Ця методика використовує стратегію «розділи і завоюй», в якій проблема ділиться на кілька підзадач, а після вирішення цих підзадач об'єднуються разом для отримання повного відсортованого списку.
У швидкій сортуванні ми спочатку ділимо список навколо елемента опори, а потім розміщуємо інші елементи у відповідних положеннях відповідно до елемента елемента.
Як показано на наведеній вище ілюстрації, в техніці Quicksort ми розділяємо масив навколо елемента повороту таким чином, що всі елементи, менші за поворот, знаходяться ліворуч, а ті, що більші за поворот, знаходяться праворуч. Потім ми беремо ці два масиви самостійно і сортуємо їх, а потім приєднуємось або завойовуємо їх, щоб отримати результуючий відсортований масив.
Ключем до Quicksort є вибір елемента опори. Це може бути перший, останній або середній елемент масиву. Першим кроком після вибору елемента опори є розміщення шарніра в правильному положенні, щоб ми могли належним чином розділити масив.
Давайте реалізуємо техніку швидкого сортування за допомогою C ++.
#include using namespace std; // Swap two elements - Utility function void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; } // partition the array using last element as pivot int partition (int arr(), int low, int high) { int i = (low - 1); for (int j = low; j <= high- 1; j++) { //if current element is smaller than pivot, increment the low element //swap elements at i and j if (arr(j) <= pivot) { i++; // increment index of smaller element swap(&arr(i), &arr(j)); } } swap(&arr(i + 1), &arr(high)); return (i + 1); } //quicksort algorithm void quickSort(int arr(), int low, int high) { if (low < high) { //partition the array int pivot = partition(arr, low, high); //sort the sub arrays independently quickSort(arr, low, pivot - 1); quickSort(arr, pivot + 1, high); } } void displayArray(int arr(), int size) { int i; for (i=0; i < size; i++) cout< Вихід:
Вхідний масив
12 23 3 43 51
Масив відсортований за допомогою Quicksort
3 12 23 43 51
У реалізації швидкого сортування вище ми маємо процедуру розділів, яка використовується для розділення вхідного масиву навколо елемента зведення, який є останнім елементом масиву. Потім ми викликаємо процедуру швидкого сортування рекурсивно для індивідуального сортування підмасивів, як показано на малюнку.
Сортувати злиття
Це ще одна техніка, яка використовує стратегію «Діли і володай». У цій техніці ми ділимо список спочатку на рівні половини. Потім ми виконуємо техніку сортування злиття для цих списків самостійно, щоб обидва списки були відсортовані. Нарешті, ми об’єднуємо обидва списки, щоб отримати повний відсортований список.
Сортування злиття та швидке сортування відбувається швидше, ніж більшість інших методів сортування. Їх ефективність залишається незмінною, навіть коли список збільшується.
Давайте побачимо ілюстрацію техніки сортування злиття.
На наведеній вище ілюстрації ми бачимо, що техніка сортування злиттям багаторазово ділить вихідний масив на підмасиви, поки у кожному підмасиві не буде лише одного елемента. Після цього підмасиви сортуються незалежно та об’єднуються, утворюючи повний відсортований масив.
Далі, давайте реалізуємо Merge Sort за допомогою мови C ++.
#include using namespace std; void merge(int *,int, int , int ); void merge_sort(int *arr, int low, int high) { int mid; if (low num; cout<<'Enter '<myarray(i); } merge_sort(myarray, 0, num-1); cout<<'Sorted array
'; for (int i = 0; i < num; i++) { cout< Вихід:
Введіть кількість елементів для сортування: 5
Введіть 5 елементів для сортування: 10 21 47 3 59
Відсортований масив
3 10 21 47 59
Сортування оболонки
Сортування оболонки - це продовження техніки сортування вставки. У сортуванні вставки ми маємо справу лише з наступним елементом, тоді як при сортуванні оболонки ми надаємо приріст або пробіл, за допомогою якого ми створюємо менші списки з батьківського списку. Елементи в підсписках не повинні бути суміжними, навпаки, вони, як правило, розділені між собою.
Сортування оболонки виконується швидше, ніж сортування вставки та вимагає менше ходів, ніж сортування вставки.
Якщо ми надаємо пробіл, тоді ми матимемо наступні підсписки з кожним елементом, який складається з 3 елементів.
Потім ми сортуємо ці три підсписки.
Вищевказаний масив, який ми отримали після об’єднання відсортованих підмасивів, майже відсортований. Тепер ми можемо виконати сортування вставки на цьому масиві, щоб відсортувати весь масив.
Таким чином, ми бачимо, що як тільки ми розділимо масив на підсписки з використанням відповідного приросту, а потім об’єднаємо їх, ми отримаємо майже відсортований список. Техніка сортування вставки в цьому списку може бути виконана, і масив сортується за меншу кількість ходів, ніж оригінальна сортування вставки.
Нижче наведено реалізацію сортування оболонки в C ++.
#include using namespace std; // shellsort implementation int shellSort(int arr(), int N) { for (int gap = N/2; gap > 0; gap /= 2) { for (int i = gap; i = gap && arr(j - gap) > temp; j -= gap) arr(j) = arr(j - gap); arr(j) = temp; } } return 0; } int main() { int arr() = {45,23,53,43,18}; //Calculate size of array int N = sizeof(arr)/sizeof(arr(0)); cout << 'Array to be sorted:
'; for (int i=0; i Вихід:
Масив для сортування:
45 23 53 43 18
Масив після сортування оболонки:
18 23 43 45 53
Таким чином, сортування оболонки діє як значне покращення порівняно із сортуванням вставки і навіть не робить половини кроків для сортування масиву.
Сортування купи
Хепсорт - це техніка, при якій для сортування списку використовується структура даних купи (min-heap або max-heap). Спочатку ми створюємо купу з несортованого списку, а також використовуємо купу для сортування масиву.
Хепсорт є ефективним, але не таким швидким або сортуванням.
Як показано на наведеній вище ілюстрації, спочатку ми створюємо максимальну купу з елементів сортування, що підлягають сортуванню. Потім ми обходимо купу і поміняємо місцями останній і перший елемент. На цей час останній елемент уже відсортований. Потім ми знову створюємо максимальну купу з решти елементів.
Знову оберніть купу і поміняйте місцями перший і останній елементи і додайте останній елемент до відсортованого списку. Цей процес продовжується, поки в купі не залишиться лише один елемент, який стане першим елементом відсортованого списку.
Давайте тепер реалізуємо Heap Sort за допомогою C ++.
#include using namespace std; // function to heapify the tree void heapify(int arr(), int n, int root) { int largest = root; // root is the largest element int l = 2*root + 1; // left = 2*root + 1 int r = 2*root + 2; // right = 2*root + 2 // If left child is larger than root if (l arr(largest)) largest = l; // If right child is larger than largest so far if (r arr(largest)) largest = r; // If largest is not root if (largest != root) { //swap root and largest swap(arr(root), arr(largest)); // Recursively heapify the sub-tree heapify(arr, n, largest); } } // implementing heap sort void heapSort(int arr(), int n) { // build heap for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // extracting elements from heap one by one for (int i=n-1; i>=0; i--) { // Move current root to end swap(arr(0), arr(i)); // again call max heapify on the reduced heap heapify(arr, i, 0); } } /* print contents of array - utility function */ void displayArray(int arr(), int n) { for (int i=0; i Вихід:
Вхідний масив
4 17 3 12 9
Відсортований масив
3 4 9 12 17
Наразі ми коротко обговорили всі основні методи сортування з ілюстрацією. Кожну з цих технік ми детально вивчимо у наступних навчальних посібниках разом із різними прикладами, щоб зрозуміти кожну техніку.
Висновок
Сортування потрібне, щоб дані були відсортовані та у належному порядку. Доступ до несортованих та недоглянутих може зайняти більше часу, що може вплинути на продуктивність усієї програми. Таким чином, для будь-яких операцій, пов’язаних з даними, такими як доступ, пошук, маніпулювання тощо, нам потрібно сортувати дані.
У програмуванні використовується багато методів сортування. Кожен метод може бути застосований залежно від структури даних, яку ми використовуємо, або часу, зайнятого алгоритмом для сортування даних або місця в пам'яті, зайнятого алгоритмом для сортування даних. Техніка, яку ми використовуємо, також залежить від того, яку структуру даних ми сортуємо.
Методи сортування дозволяють нам сортувати наші структури даних у певному порядку та розташувати елементи у порядку зростання або зменшення. Ми бачили такі методи сортування, як сортування за бульбашками, сортування за виділенням, сортування за допомогою вставки, швидке сортування, сортування за оболонкою, сортування за об’єднанням та купі. Сортування за бульбашками та сортування за вибором простіші та простіші у реалізації.
У наступних підручниках ми детально розглянемо кожен із згаданих методів сортування.
=> Клацніть тут для безкоштовного курсу C ++.
Рекомендована література
- Сортування купи в C ++ з прикладами
- Об’єднати сортування в C ++ із прикладами
- Сортування вставки в C ++ із прикладами
- JMeter Video 1: Вступ, Завантажте та встановіть JMeter
- Вступ до мови програмування Java - Підручник з відео
- Процес введення та встановлення Python
- Команда сортування Unix із синтаксисом, опціями та прикладами
- Метод сортування MongoDB () із прикладами
