Съществуват множество алгоритми за сортиране. Намирането на подходящото за вашето приложение е задача, която изисква кратко разбиране на фактори като производителност, времева сложност, дължина на кода и т.н. на определен алгоритъм. В тази публикация ще разгледаме всички основни концепции, необходими за внедряване на Quicksort в C ++ в следния ред:
- Разбиране на алгоритъма за бързи сортове
- Псевдокод за Quicksort
- Програма на Quicksort в C ++
- Сложност на времето Quicksort
Разбиране на алгоритъма за бързи сортове
Точно като Сливане на сортиране , Quicksort следва стратегията за разделяне и завладяване. Използвайки стратегията „разделяй и владей“, ние разделяме проблема на много подпроблеми и ги решаваме рекурсивно. Първо ще разберем целия процес стъпка по стъпка и след това с помощта на пример ще развием дълбоко разбиране на целия процес.
Първо, ще поискаме несортирания масив от потребителя.
След като получим нашия несортиран масив, трябва да изберем пивотна стойност от масива. Можем да изберем всяка стойност.
След като изберем точката на въртене след това трябва да подредим останалите елементи на масива по такъв начин, че всички елементи, по-малки от стойността на въртене, да бъдат поставени вдясно от стойността на въртене и всички елементи, по-големи от pivot стойност трябва да се постави вдясно от стойността на ос.
Изпълняваме стъпка 3, докато не получим нашия сортиран масив.
Сега, нека да разгледаме пример и да приложим алгоритъма и да видим как работи.
Здравейте [5, 4, 1, 11, 9, 6, 2, 3] за този пример ние винаги ще разглеждаме въртенето като най-десния елемент на списъка.
Нека да преминем през всяка стъпка и да разберем логиката, която използвахме за решаване на проблема.
Първо, ние избрахме „3“ като наш пивот и подредихме всички елементи под „3“ вдясно и всички елементи, по-големи от „3“ вдясно.
В този момент имаме 2 подпроблеми. Нека първо решим подпроблемата вдясно. Избрахме един като наш пивот и поставихме „2“ вдясно.
За да разрешим втората подпроблема, ние избираме „6“ като наш пивот и поставяме елементите, както обсъдихме по-рано.
Имаме още 2 подпроблеми. Първият се решава чрез избор на 4 като пивот, а вторият се решава чрез избор на 9 като пивот. И накрая, имаме нашия сортиран масив с елементите, поставени в индекса за подчертаване.
Забележка- Важният момент, който трябва да разберете тук, е, че всички операции се извършват в един и същ масив. Нови масиви не се създават.
Псевдокод за Quicksort в C ++
QuickSort (масив [], start_index, end_index) {if (start_index Програма на Quicksort в C ++
Разбрахме алгоритъма и разработихме задълбочено разбиране за работата на алгоритъма. Нека внедрим Quicksort в C ++ и напишем програма за сортиране на масив.
#include използвайки пространство от имена std void swap_elements (int * a, int * b) {int temp = * a * a = * b * b = temp} int дял (int array [], int start_index, int end_index) {int pivot = масив [end_index] int i = (start_index - 1) за (int j = start_index j<= end_index- 1 j++) { if (array[j] <= pivot) { i++ swap_elements(&array[i], &array[j]) } } swap_elements(&array[i + 1], &array[end_index]) return (i + 1) } void quickSort(int array[], int start_index, int end_index) { if (start_index < end_index) { int partition_index = partition(array, start_index, end_index) quickSort(array, start_index, partition_index - 1) quickSort(array, partition_index + 1, end_index) } } void printArray(int array[], int number) { int i cout<<'Sorted Array: ' for (i = 0 i < number i++) cout << array[i] << ' ' cout << endl } int main() { int Hello[30] int i int NumberofElements cout<>Разходи на NumberofElements<<'Enter the elements one by one: ' for(i=0i>Здравейте [i]} quickSort (Здравейте, 0, NumberofElements-1) printArray (Здравейте, NumberofElements) върнете 0} Изход:
Сложност във времето
Нека поговорим за най-важния аспект на всеки алгоритъм за сортиране, т.е. сложността на времето. Разказва ни за ефективността на алгоритъма в различни сценарии. Тези стойности могат да ни помогнат да решим дали можем да използваме този алгоритъм за нашето приложение.
- Най-добрият случай- На)
- Среден случай - (nlogn)
- Най-лошия случай- На2)
С това стигнахме до края на тази статия Quicksort в C ++. Ако искате да научите повече, разгледайте от Edureka, доверена компания за онлайн обучение. Курсът за обучение и сертифициране на Java J2EE и SOA на Edureka е предназначен да ви обучи както за основните, така и за разширените Java концепции, заедно с различни Java рамки като Hibernate & Spring.
Имате въпрос към нас? Моля, споменете го в раздела за коментари на този блог и ние ще се свържем с вас възможно най-скоро.
базирана на данни рамка в селен