quick sort c with examples
Швидке сортування на C ++ з ілюстрацією.
Quicksort - це широко використовуваний алгоритм сортування, який вибирає певний елемент, який називається “pivot”, і розділяє масив або список на дві частини на основі цього pivot s0, щоб елементи, менші за pivot, знаходились ліворуч від списку та елементів більше, ніж опорні точки, розташовані праворуч від списку.
Таким чином, список розділений на два підсписки. Підсписки можуть бути не потрібні для однакового розміру. Потім Quicksort викликає себе рекурсивно, щоб відсортувати ці два підсписки.
=> Ознайомтесь з Ідеальним навчальним посібником для C ++ тут.
Що ви дізнаєтесь:
- Вступ
- Загальний алгоритм
- Псевдокод для швидкого сортування
- Ілюстрація
- Приклад С ++
- Приклад Java
- Аналіз складності алгоритму швидкого сортування
- 3-х сторонній Quicksort
- Рандомізована Quicksort
- Quicksort проти Merge Sort
- Висновок
- Рекомендована література
Вступ
Quicksort працює ефективно, а також швидше навіть для більших масивів або списків.
У цьому підручнику ми розглянемо докладніше про роботу Quicksort разом із деякими прикладами програмування алгоритму швидкої сортування.
В якості основного значення ми можемо вибрати перше, останнє або середнє значення, або будь-яке випадкове значення. Загальна ідея полягає в тому, що в кінцевому підсумку значення зведеного елемента розміщується у відповідному положенні в масиві шляхом переміщення інших елементів масиву вліво або вправо.
Загальний алгоритм
Загальний алгоритм Quicksort наведено нижче.
quicksort(A, low, high) begin Declare array A(N) to be sorted low = 1st element; high = last element; pivot if(low Погляньмо тепер на псевдокод для техніки Quicksort.
Псевдокод для швидкого сортування
//pseudocode for quick sort main algorithm procedure quickSort(arr(), low, high) arr = list to be sorted low – first element of array high – last element of array begin if (low Робота алгоритму розділення описана нижче на прикладі.
На цій ілюстрації ми приймаємо останній елемент як опорну. Ми бачимо, що масив послідовно розділяється навколо елемента опори, поки в масиві не буде одного елемента.
Тепер ми представляємо ілюстрацію Quicksort нижче, щоб краще зрозуміти концепцію.
Ілюстрація
Побачимо ілюстрацію алгоритму швидкого сортування. Розглянемо наступний масив з останнім елементом як зведення. Крім того, перший елемент позначений низьким, а останній - високим.
Як створити новий файл Java в eclipse - -
З ілюстрації видно, що ми рухаємо вказівники вгору і внизу на обох кінцях масиву. Щоразу, коли низькі точки до елемента більше, ніж опорна точка, і високі точки до елемента, менша від опорного, ми обмінюємося позиціями цих елементів і просуваємо нижній та високий покажчики у відповідних напрямках.
Це робиться до тих пір, поки низький і високий покажчики не перетинатимуть один одного. Як тільки вони перетинаються між собою, поворотний елемент розміщується у відповідному положенні, а масив розділяється на дві частини. Потім обидва ці підмасиви сортуються незалежно за допомогою швидкої сортування рекурсивно.
Приклад С ++
Нижче наведено реалізацію алгоритму 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 pivot = arr(high); // pivot 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 35 19 45
Масив відсортований за допомогою швидкого сортування
3 12 19 23 35 43 45 51
Тут у нас є кілька процедур, які використовуються для розділення масиву та виклику швидкого сортування рекурсивно для сортування розділу, базової функції швидкого сортування та службових функцій для відображення вмісту масиву та відповідного обміну двома елементами.
Спочатку ми викликаємо функцію швидкого сортування з масивом введення. Усередині функції швидкого сортування ми називаємо функцію розділення. У функції розділу ми використовуємо останній елемент як опорний елемент для масиву. Після прийняття рішення щодо обертання масив розділений на дві частини, а потім викликається функція швидкого сортування для самостійного сортування обох підмасивів.
Коли функція швидкого сортування повертається, масив сортується таким чином, що елемент обертання знаходиться в правильному розташуванні, а елементи, менші за розворот, знаходяться ліворуч від зведення, а елементи, більші за розворот, - праворуч від зведення.
Далі ми реалізуємо алгоритм швидкого сортування на Java.
Приклад Java
// Quicksort implementation in Java class QuickSort { //partition the array with last element as pivot int partition(int arr(), int low, int high) { int pivot = arr(high); int i = (low-1); // index of smaller element for (int j=low; j Вихід:
Вхідний масив
12 23 3 43 51 35 19 45
найкраще безкоштовне програмне забезпечення для очищення ПК - -
Масив після сортування за допомогою швидкого сортування
3 12 19 23 35 43 45 51
У реалізації Java ми також використовували ту ж логіку, що і в реалізації С ++. Ми використовували останній елемент у масиві, оскільки шарнірна та швидка сортування виконуються в масиві, щоб розташувати елемента опорного елемента у правильному положенні.
Аналіз складності алгоритму швидкого сортування
Час, необхідний швидкому сортуванню для сортування масиву, залежить від вхідного масиву та стратегії чи методу розділення.
Якщо k - кількість елементів, менших за опору, а n - загальна кількість елементів, то загальний час, зайнятий швидкою сортуванням, може бути виражений наступним чином:
T (n) = T (k) + T (n-k-1) + O (n)
Тут T (k) і T (n-k-1) - це час, зайнятий рекурсивними викликами, а O (n) - час, зайнятий викликом розділення.
Давайте детально проаналізуємо складність цього часу для швидкого сортування.
# 1) Найгірший випадок : Найгірший випадок у техніці швидкого сортування трапляється здебільшого, коли ми вибираємо найнижчий або найвищий елемент масиву як опорну точку. (На наведеній вище ілюстрації ми вибрали найвищий елемент як опору). У такій ситуації найгірший випадок трапляється, коли масив, що підлягає сортуванню, вже відсортований за зростанням або спаданням.
Звідси наведений вище вираз для загального часу, що приймається, змінюється як
T (n) = T (0) + T (n-1) + O (n) що вирішує O (nдва)
# 2) Кращий випадок: Найкращий випадок для швидкого сортування завжди виникає, коли вибраний елемент зсуву знаходиться в середині масиву.
Таким чином, повторення для найкращого випадку:
безкоштовне програмне забезпечення для конвертації відео для Windows 10
T (n) = 2T (n / 2) + O (n) = O (nlogn)
# 3) Середній випадок: Щоб проаналізувати середній випадок для швидкого сортування, нам слід розглянути всі перестановки масиву, а потім обчислити час, який займає кожна з цих перестановок. У двох словах, середній час для швидкого сортування також стає O (nlogn).
Нижче наведено різні складності техніки швидкого сортування:
Найгірша складність часу O (n 2) стабільність Не стабільний, оскільки два елементи з однаковими значеннями не будуть розміщені в однаковому порядку. Стабільний - два елементи з однаковими значеннями відображатимуться в однаковому порядку у відсортованому виведенні. Найкраща складність часу O (n * log n) Середня часова складність O (n * log n) Складність простору O (n * log n)
Ми можемо реалізувати швидке сортування різними способами, просто змінивши вибір елемента опори (середнього, першого або останнього), однак найгірший випадок рідко трапляється для швидкого сортування.
3-х сторонній Quicksort
В оригінальній техніці швидкої сортування ми зазвичай вибираємо елемент зведення, а потім ділимо масив на підмасиви навколо цього зведення таким чином, щоб один підмасив складався з елементів, менших за зведений, а інший - з елементів, більших за зведений.
Але що, якщо ми виділимо елемент зведеного елемента і в масиві буде більше одного елемента, який дорівнює зведеному?
Наприклад, розглянемо наступний масив {5,76,23,65,4,4,5,4,1,1,2,2,2,2}}. Якщо ми виконуємо просту швидку сортування для цього масиву і вибираємо 4 як елемент зведення, то ми виправляємо лише одне входження елемента 4, а решта буде розділено разом з іншими елементами.
Натомість, якщо ми використовуємо тристоронній швидкий сортування, то ми розділимо масив (l ... r) на три підмасиви таким чином:
- Масив (l… i) - тут i є стержнем, і цей масив містить елементи, менші за зведення.
- Масив (i + 1… j-1) - Містить елементи, які дорівнюють опорі.
- Масив (j… r) - Містить елементи, більші за опорну.
Таким чином, триходова швидка сортування може бути використана, коли в масиві є більше одного зайвого елемента.
Рандомізована Quicksort
Техніка швидкого сортування називається технікою рандомізованої сортування, коли ми використовуємо випадкові числа для вибору елемента опори. У рандомізованій швидкій сортирці це називається “центральний шарнір”, і він ділить масив таким чином, що кожна сторона має принаймні ¼ елементів.
Псевдокод для рандомізованого швидкого сорту наведено нижче:
// Sorts an array arr(low..high) using randomized quick sort randomQuickSort(array(), low, high) array – array to be sorted low – lowest element in array high – highest element in array begin 1. If low >= high, then EXIT. //select central pivot 2. While pivot 'pi' is not a Central Pivot. (i) Choose uniformly at random a number from (low..high). Let pi be the randomly picked number. (ii) Count elements in array(low..high) that are smaller than array(pi). Let this count be a_low. (iii) Count elements in array(low..high) that are greater than array(pi). Let this count be a_high. (iv) Let n = (high-low+1). If a_low >= n/4 and a_high >= n/4, then pi is a central pivot. //partition the array 3. Partition array(low..high) around the pivot pi. 4. // sort first half randomQuickSort(array, low, a_low-1) 5. // sort second half randomQuickSort(array, high-a_high+1, high) end procedureУ наведеному вище коді на “randomQuickSort”, на кроці №2 ми вибираємо центральну опору. На кроці 2 ймовірність того, що вибраний елемент є центральним стрижнем, дорівнює ½. Отже, цикл на кроці 2 передбачається запустити 2 рази. Таким чином, часова складність для кроку 2 у рандомізованій швидкій сорти становить O (n).
Використання циклу для вибору центрального стовпа не є ідеальним способом реалізації рандомізованого швидкого сортування. Натомість ми можемо випадковим чином обрати елемент і назвати його центральним розворотом або змінити елементи масиву. Очікувана найгірша часова складність для рандомізованого алгоритму швидкого сортування - O (nlogn).
Quicksort проти Merge Sort
У цьому розділі ми обговоримо основні відмінності між швидким сортуванням та об’єднанням.
Параметр порівняння Швидке сортування Сортувати злиття розділення Масив розділений на шарнірний елемент і не завжди завжди на дві половини. Його можна розділити в будь-якому співвідношенні. Масив розділений на дві половини (n / 2). Найгірша складність випадку O (n 2) - у найгіршому випадку потрібно багато порівнянь. O (nlogn) - те саме, що і середній випадок Використання наборів даних Не вдається добре працювати з більшими наборами даних. Добре працює з усіма наборами даних незалежно від розміру. Додатковий простір На місці - не потребує додаткового простору. Не на місці - потрібен додатковий простір для зберігання допоміжного масиву. Метод сортування Внутрішня - дані сортуються в основній пам’яті. Зовнішня - використовує зовнішню пам’ять для зберігання масивів даних. Ефективність Швидше та ефективніше для списків невеликих розмірів. Швидкий та ефективний для більших списків. Масиви / пов'язані списки Більш переважна для масивів. Добре працює для пов'язаних списків.
Висновок
Як випливає з назви, quicksort - це алгоритм, який сортує список швидко, ніж будь-які інші алгоритми сортування. Так само, як сортування злиттям, швидке сортування також приймає стратегію поділу та завоювання.
Як ми вже бачили, за допомогою швидкого сортування ми ділимо список на підмасиви за допомогою елемента pivot. Потім ці підмасиви самостійно сортуються. В кінці алгоритму весь масив повністю сортується.
Quicksort працює швидше і ефективно працює для сортування структур даних. Quicksort - популярний алгоритм сортування, який іноді навіть кращий за алгоритм сортування злиттям.
У нашому наступному уроці ми детально обговоримо сортування Shell.
=> Зверніть увагу на прості навчальні серії C ++ тут.
Рекомендована література
- Метод сортування MongoDB () із прикладами
- Команда сортування Unix із синтаксисом, опціями та прикладами
- Об’єднати сортування в C ++ із прикладами
- Сортування купи в C ++ з прикладами
- Сортування оболонки в C ++ з прикладами
- Сортування виділення в C ++ із прикладами
- Сортування міхура в C ++ із прикладами
- Сортування вставки в C ++ із прикладами
