EDUCBA

EDUCBA

MENUMENU
  • Blog
  • Free Courses
  • All Courses
  • All in One Bundle
  • Login
Home Software Development Software Development Tutorials Software Development Basics Quick sort algorithm

Quick sort algorithm

Updated March 31, 2023

Quick sort algorithm

Introduction to Quick sort algorithm

Quick Sort is a sorting technique that sorts the given range of elements and returns that range in sorted order as output. This Algorithm takes an array as input and divides it into many sub-arrays until it matches a suitable condition, merges the elements then returns a sorted array.

Start Your Free Software Development Course

Web development, programming languages, Software testing & others

Quick Sort follows the divide and conquers approach since the pivot element first divides the range of numbers into sub-arrays and then returns a sorted array as the final step by gathering all the numbers.

How does Quick Sort Algorithm Work?

Before moving on to the algorithm, let’s see how Quick Sort works by taking an example of an array of 7 elements.

The input array is shown in the below figure.

Q1

1. The very first step in Quick Sort includes selecting an element as a pivot element. A pivot element is an element from the array which is selected to act as a division to a range of numbers. If we select ‘n’ as our pivot element, so the numbers from the array which are less than ‘n’ settle at the left side of n, and numbers that are greater than n go to the right of the pivot element. That’s why our first step in Quick Sort is to select an element as a pivot element. The pivot element can be selected in many ways in which some are listed below:

  • Pick the first element as the pivot.
  • Pick the last element as the pivot.
  • Pick a random element as the pivot.
  • Pick median as the pivot.

In our example, let’s select the last element as the pivot element and continue the process.

Q2

2. The fundamental process in quicksort is a partition(). After selecting the pivot element, we need to rearrange the elements by moving elements that are less than pivot to the left side of the pivot and which are greater than the pivot to the right of the pivot.

The process is shown below:

  • A pointer must be fixed at the pivot element.

Q3

  • Then the pivot element is compared with elements from the beginning.

Q4

  • If the element is greater than the pivot, a second pointer is set for that element. Now, the pivot element is compared with other elements. If an element smaller than the pivot is found, then it is swapped with the greater element, which is in the second pointer.

Q5

  • Again the same process continues to set the next greater element as the second pointer. And it is swapped with the next smaller element.

Q6

  • The process will continue until the second last element is reached.

Q7

Q8

  • When the second last element is reached, the pivot element will be swapped with the second pointer.

Q9

Q10

3. Now, the array has been divided into two parts, the first part with elements less than the pivot, second part with elements greater than the pivot.

Q11

  • Pivot elements are chosen for the left and right sub-arrays separately, and the above process is called recursively for each part until each sub-array is formed into a single element. When this point occurs, the array is already sorted, and the final array is shown below.

Q12

Algorithm of Quick Sort

Before moving on to the actual implementation of the QuickSort, let us look at the algorithm.

Step 1: Consider an element as a pivot element.

Step 2: Assign the lowest and highest index in the array to low and high variables and pass it in the QuickSort function.

Step 3: Increment low until array[low] greater than pivot then stop.

Step 4: Decrement high until array[high] less than pivot then stop.

Step 5: Swap low and high and repeat the process until the second last element.

Step 6: Swap pivot and second last element then you will get an array that completed the first partition.

Step 7: Repeat the same process for the two arrays that are obtained until you can no more divide the array.

QuickSort Source Code

# Quick sort in Python
# function to find the partition position
def arraypartition(array, low, high):
# choose the last element as pivot
pivot = array[high] # second pointer for greater element
i = low - 1
# traverse through all elements by comparing each element with pivot
for j in range(low, high):
if array[j] <= pivot:
# if element smaller than pivot is found then swap it with the greater element    pointed by i
i = i + 1
# swapping element at i with element at j
(array[i], array[j]) = (array[j], array[i])
# swap the pivot element with the greater element specified by i
(array[i + 1], array[high]) = (array[high], array[i + 1])
# return the position of partition
return i + 1
# function to perform quicksort
def quickSort(array, low, high):
if low < high:
# find pivot element such that
# element smaller than pivot are on the left
# element greater than pivot are on the right
pi = arraypartition(array, low, high)
# recursive call on the left of pivot
quickSort(array, low, pi - 1)
# recursive call on the right of pivot
quickSort(array, pi + 1, high)
array = [10, 9, 8, 3, 2, 11, 4] print("The Unsorted Array is: ")
print(array)
quickSort(array, 0, len(array) - 1)
print('Sorted Array in Ascending Order:')
print(array)

Output:

Quick sort algorithm output

Time Complexities

Worst-case complexity

Worst Case Complexity O(n2) occurs when the pivot element is either the greatest or the smallest among all the elements in the array. This leads to the case in which the pivot element lies at the end of the array.

Best Case Complexity

Best Case Complexity  O(n*log n) occurs when the pivot element lies in the middle or near the middle element in the array.

Average Case Complexity

Average Case Complexity  O(n*log n) occurs when we don’t exactly get evenly balanced partitions of the array.

Conclusion

  • Quick Sort follows the divide and conquers approach and sorts the given range of elements and returns that range in sorted order as output.
  • A pivot element is an element from the array which is selected to act as a division to a range of numbers.
  • You can select any element as a pivot element.

Recommended Articles

This is a guide to Quick sort algorithm. Here we discuss How does Quick Sort Algorithm Work along with the codes and outputs. You may also have a look at the following articles to learn more –

  1. DFS Algorithm in C
  2. Minimax Algorithm
  3. RSA Algorithm
  4. Line Drawing Algorithm
All in One Excel VBA Bundle
500+ Hours of HD Videos
15 Learning Paths
120+ Courses
Verifiable Certificate of Completion
Lifetime Access
Financial Analyst Masters Training Program
2000+ Hours of HD Videos
43 Learning Paths
550+ Courses
Verifiable Certificate of Completion
Lifetime Access
All in One Data Science Bundle
2000+ Hour of HD Videos
80 Learning Paths
400+ Courses
Verifiable Certificate of Completion
Lifetime Access
All in One Software Development Bundle
5000+ Hours of HD Videos
149 Learning Paths
1050+ Courses
Verifiable Certificate of Completion
Lifetime Access
Primary Sidebar
All in One Software Development Bundle5000+ Hours of HD Videos | 149 Learning Paths | 1050+ Courses | Verifiable Certificate of Completion | Lifetime Access
Financial Analyst Masters Training Program2000+ Hours of HD Videos | 43 Learning Paths | 550+ Courses | Verifiable Certificate of Completion | Lifetime Access
Footer
About Us
  • Blog
  • Who is EDUCBA?
  • Sign Up
  • Live Classes
  • Certificate from Top Institutions
  • Contact Us
  • Verifiable Certificate
  • Reviews
  • Terms and Conditions
  • Privacy Policy
  •  
Apps
  • iPhone & iPad
  • Android
Resources
  • Free Courses
  • Java Tutorials
  • Python Tutorials
  • All Tutorials
Certification Courses
  • All Courses
  • Software Development Course - All in One Bundle
  • Become a Python Developer
  • Java Course
  • Become a Selenium Automation Tester
  • Become an IoT Developer
  • ASP.NET Course
  • VB.NET Course
  • PHP Course

ISO 10004:2018 & ISO 9001:2015 Certified

© 2023 - EDUCBA. ALL RIGHTS RESERVED. THE CERTIFICATION NAMES ARE THE TRADEMARKS OF THEIR RESPECTIVE OWNERS.

Let’s Get Started

By signing up, you agree to our Terms of Use and Privacy Policy.

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you

EDUCBA
Free Software Development Course

Web development, programming languages, Software testing & others

By continuing above step, you agree to our Terms of Use and Privacy Policy.
*Please provide your correct email id. Login details for this Free course will be emailed to you

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA Login

Forgot Password?

By signing up, you agree to our Terms of Use and Privacy Policy.

This website or its third-party tools use cookies, which are necessary to its functioning and required to achieve the purposes illustrated in the cookie policy. By closing this banner, scrolling this page, clicking a link or continuing to browse otherwise, you agree to our Privacy Policy

Loading . . .
Quiz
Question:

Answer:

Quiz Result
Total QuestionsCorrect AnswersWrong AnswersPercentage

Explore 1000+ varieties of Mock tests View more