quick sort c with examples
Quicksort в C ++ с илюстрация.
Quicksort е широко използван алгоритъм за сортиране, който избира специфичен елемент, наречен „pivot“ и разделя масива или списъка, за да бъде сортиран на две части въз основа на този pivot s0, че елементите, по-малки от pivot, са вляво от списъка и елементите по-големи от въртенето са вдясно от списъка.
По този начин списъкът е разделен на два подлиста. Подлистите може да не са необходими за същия размер. Тогава Quicksort се извиква рекурсивно, за да сортира тези два подлиста.
=> Вижте Перфектното ръководство за обучение на C ++ тук.
Какво ще научите:
- Въведение
- Общ алгоритъм
- Псевдо код за 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.
Псевдо код за 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 по-долу, за да разберем по-добре концепцията.
Илюстрация
Нека да видим илюстрация на алгоритъма за бързо сортиране. Разгледайте следния масив с последния елемент като pivot. Също така първият елемент е обозначен с нисък, а последният е с висок.
създайте нов java проект в eclipse
От илюстрацията можем да видим, че преместваме указателите високо и ниско в двата края на масива. Винаги, когато ниските точки към елемента са по-големи от въртенето и високите точки към елемента, по-малки от въртенето, тогава обменяме позициите на тези елементи и придвижваме ниските и високите указатели в съответните им посоки.
Това се прави, докато ниските и високите указатели се пресичат. След като се пресичат, въртящият елемент се поставя в правилното му положение и масивът се разделя на две. След това и двата под-масива се сортират независимо, като се използва рекордно бързо сортиране.
Пример за C ++
По-долу е дадено изпълнението на алгоритъма 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, ние използвахме същата логика, която използвахме при реализацията на C ++. Използвахме последния елемент в масива, тъй като въртенето и бързата сортировка се изпълняват върху масива, за да поставим елемента на въртене в правилното му положение.
Анализ на сложността на алгоритъма за бързи сортове
Времето, необходимо на quicksort за сортиране на масив, зависи от входния масив и стратегията или метода на разделяне.
Ако k е броят на елементите, по-малък от ос и n е общият брой на елементите, тогава общото време, отнемано от quicksort може да бъде изразено, както следва:
T (n) = T (k) + T (n-k-1) + O (n)
Тук T (k) и T (n-k-1) са времето, необходимо за рекурсивни повиквания, а O (n) е времето, необходимо за разделяне на повикването.
Въпроси и отговори за интервю за мрежов инженер в cisco
Нека анализираме подробно тази сложност на времето за бърза сортировка.
# 1) Най-лошият случай : Най-лошият случай в техниката на бърза сортировка възниква най-вече, когато изберем най-ниския или най-високия елемент в масива като опорна точка. (В горната илюстрация сме избрали най-високия елемент като опора). В такава ситуация се случва най-лошият случай, когато масивът, който ще се сортира, вече е сортиран във възходящ или низходящ ред.
Следователно горният израз за общото време се променя като:
T (n) = T (0) + T (n-1) + O (n) което решава до Надве)
# 2) Най-добрият случай: Най-добрият случай за бърза сортировка винаги възниква, когато избраният пивотен елемент е в средата на масива.
По този начин повторението за най-добрия случай е:
най-добрият уебсайт за гледане на безплатни аниме
T (n) = 2T (n / 2) + O (n) = O (nlogn)
# 3) Среден случай: За да анализираме средния случай за бърза сортировка, трябва да разгледаме всички пермутации на масива и след това да изчислим времето, необходимо за всяка от тези пермутации. Накратко, средното време за бърза сортировка също става O (nlogn).
По-долу са дадени различните сложности на техниката Quicksort:
Най-лошата времева сложност O (n 2) стабилност Нестабилен, тъй като два елемента с еднакви стойности няма да бъдат поставени в същия ред. Стабилен - два елемента с еднакви стойности ще се появят в същия ред в сортирания изход. Най-добрата сложност във времето O (n * log n) Средна времева сложност O (n * log n) Космическа сложност O (n * log n)
Можем да реализираме quicksort по много различни начини само чрез промяна на избора на шарнирния елемент (среден, първи или последен), но най-лошият случай рядко се случва за quicksort.
3-посочен Quicksort
В оригиналната техника за бърза сортировка обикновено избираме пивотен елемент и след това разделяме масива на подмасиви около този пивот, така че един подмасив се състои от елементи, по-малки от пивота, а друг се състои от елементи, по-големи от пивота.
Но какво ще стане, ако изберем pivot елемент и в масива има повече от един елемент, който е равен на pivot?
Например, разгледайте следния масив {5,76,23,65,4,4,5,4,1,1,2,2,2,2}. Ако изпълним обикновена бърза сортировка на този масив и изберете 4 като обобщен елемент, тогава ще коригираме само едно появяване на елемент 4, а останалите ще бъдат разделени заедно с останалите елементи.
Вместо това, ако използваме трипосочна бърза сортировка, тогава ще разделим масива (l ... r) на три под-масива, както следва:
- Масив (l… i) - Тук i е въртенето и този масив съдържа елементи, по-малки от pivot.
- Масив (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 ++ с примери
