Quick sort is one of the most important and widely used sorting algorithm. Quick sort is a very efficient algorithm which if implemented well can run two to three times faster than its competitors merge sort and and heap sort.
The algorithm is a divide and conquer algorithm. The algorithm works by selecting a pivot element, this pivot element is usually the first element and choice of the pivot element affects the running time of the algorithm. The algorithm is basically to select a pivot element and then moving all the element less than the pivot element to its left and all the elements greater than pivot element to its right. Then we divide the array into 2 parts, one on the left of the pivot and other on the right of the pivot and then pass these 2 arrays to the algorithm for further sorting.
Algorithm :
Selection of pivot Element : Pivot element selection affects the running time of the algorithm. the following are the most common choices for selecting the pivot element,
Parallelization : As we divide the array of elements into 2 and separately pass them into the recursive call, we can do this using separate threads and decrease the running time of the algorithm.
Running time :
Let us now see the code
You might also be interested in
Data Encryption using Caesar Cipher
Data Decryption using Caesar Cipher
LCM of 2 numbers
Anagram Strings
Double Linked List
Finding Middle node in a Linked List
Infix to Prefix Conversion
The algorithm is a divide and conquer algorithm. The algorithm works by selecting a pivot element, this pivot element is usually the first element and choice of the pivot element affects the running time of the algorithm. The algorithm is basically to select a pivot element and then moving all the element less than the pivot element to its left and all the elements greater than pivot element to its right. Then we divide the array into 2 parts, one on the left of the pivot and other on the right of the pivot and then pass these 2 arrays to the algorithm for further sorting.
Algorithm :
- Choose a Pivot element.
- Take 2 variables left_marker and right_marker excluding the pivot element.
- Set left_marker as the first element of the array
- Set right_marker as the last element of the array
- while the value at the left_marker is less than pivot keep increasing it.
- While the value at the right_marker is greater than pivot element keep decreasing it.
- if the left_marker is less than the right_marker then swap the elements and go to step 5.
- if the left marker is greater than right marker then stop and swap pivot and the right_marker.
Selection of pivot Element : Pivot element selection affects the running time of the algorithm. the following are the most common choices for selecting the pivot element,
- Selecting first element as the pivot element.
- Selecting last element as the pivot element.
- Selecting median as the pivot element.
- Randomly taking an element as pivot element.
Parallelization : As we divide the array of elements into 2 and separately pass them into the recursive call, we can do this using separate threads and decrease the running time of the algorithm.
Running time :
Worst case performance : O(n^2)
Best case performance : O(n* log(n))
Let us now see the code
C Program
C++ Program
Sample input and output to check the program
You might also be interested in
Data Encryption using Caesar Cipher
Data Decryption using Caesar Cipher
LCM of 2 numbers
Anagram Strings
Double Linked List
Finding Middle node in a Linked List
Infix to Prefix Conversion
Comments
Post a Comment