EDUCBA

EDUCBA

MENUMENU
  • Free Tutorials
  • Free Courses
  • Certification Courses
  • 600+ Courses All in One Bundle
  • Login

Quick Sort in Python

Home » Software Development » Software Development Tutorials » Python Tutorial » Quick Sort in Python

Quick Sort in Python

Introduction to Quick Sort in Python

In python, Quick sort is defined as a sorting algorithm which follows the divide and conquer method to select the pivot element based on which the remaining array will be divided into two sub-arrays elements which are less than pivot will be in left sub-array and elements which are greater than pivot will be in right sub-array and the process will repeat recursively until all sub-arrays got sorted without using auxiliary array’s or extra space is called Quick sort. Quick sort is an efficient and most used sorting algorithm which is better than similar algorithms if it is implemented well. It has an average-case time complexity of O(NlogN) and worst-case time complexity is O(n^2).

Logic behind Quick Sort in Python

Quick sort algorithm is an in-place sorting algorithm without the need of extra space or auxiliary array as all operations will be done in the same list, as we divided the given list into three parts as pivot element, elements less than pivot as a one sub-list and elements greater than pivot as another sub-list. This is also called as a partition-exchange sort. The quicksort is better sorting algorithm and in most programming languages available as a built-in sorting algorithm

Start Your Free Software Development Course

Web development, programming languages, Software testing & others

Given below are the main steps for the logic of quick sort implementation:

1. First, we will select the pivot element from the given list.

We can select the pivot element in different ways as below:

  • We can select the first element of the list as a pivot.
  • We can select the last element of the list as a pivot.
  • We can select some random element of the list as a pivot.
  • Finally, we can select the median of the elements of the list as a pivot.

2. In partitioning we will rearrange the list in such a way that all the elements of the list which are less than pivot will be in the left side and all the elements of the list which are greater than pivot will be in the right side and same elements will be on any one of the sides of the pivot. This process is called partitioning. After the end of the partition process, the pivot element will be in its final position on the list.

Popular Course in this category
Python Training Program (36 Courses, 13+ Projects)36 Online Courses | 13 Hands-on Projects | 189+ Hours | Verifiable Certificate of Completion | Lifetime Access
4.8 (8,308 ratings)
Course Price

View Course

Related Courses
Programming Languages Training (41 Courses, 13+ Projects, 4 Quizzes)Angular JS Training Program (9 Courses, 7 Projects)

3. We will apply the above steps recursively on both sub-arrays until all the sub-arrays are sorted.

Example:

Take a list with 6 elements as 9 7 15 10 2 5. Here we will take the first element of the list as pivot element and start as starting off the list and end as the end of the list.

Step 1: Pivot = 9    start = 9      end = 5

9  7  15   10  2    5

Now we will call the partitioning process on the given list and we will get rearranged list with pivot element being in its final position as below:

5 7  2  9  15  10

As we are seeing pivot element is in its final sorted position. Now we will apply the same steps to the left and right sub-lists of the pivot element.

Step 2: pivot = 5 start = 5  end =2 ( left sub-list)

2 5 7

pivot = 15 start = 15 end = 10 (right sub-list)

10  15

In the above step, we have called the partitioning method on both left and right sub-lists and we got the re-arranged as below:

2  5  7  9  10  15

If we observe the list which we got in the above step, all elements are in its sorted positions.

So by following the above logic, we can implement the quick sort and this is one of the ways of implementation of quick sort which has an average case time complexity of O(NlogN) and worst case time complexity being O(n2). If we observe above sorting is happened in-place without using any extra space.

Examples of Quick Sort in Python

Given below are the examples:

Example #1

Quick sort implementation using the last element of the list as a pivot element.

Code:

defpartition(my_arr, start, end):
pivot = my_arr[end] i = start-1
for j in range(start, end):
if my_arr[j]<=pivot:
i=i+1
my_arr[i], my_arr[j] = my_arr[j], my_arr[i] my_arr[i+1], my_arr[end] = my_arr[end], my_arr[i+1] return i+1
defquicksort(my_arr, start, end):
if start<end:
q = partition(my_arr, start, end)
quicksort(my_arr, start, q-1)
quicksort(my_arr, q+1, end)
arr = [15, 9, 11, 2 ,21,12] quicksort(arr, 0, 5)
print(arr)

In the above implementation, we have defined two functions partition() and quick sort(), where partition function will do the operations on the list to re-arrange the list such that pivot element will be in sorted position, quick sort() function will divide the list into sub-lists and calls the partition function recursively such that all sub-lists will get sorted.

Output:

quick sort in python 1

Example #2

Implementation of quick sort using first element as pivot element.

Code:

defpartition(my_arr, start, end):
pivot = my_arr[start] low = start+1
hight = end
while True:
while low <=high and my_arr[high] >= pivot:
high = high - 1
while low <= high and my_arr[low] <= pivot:
low = low -1
if low <= high:
my_arr[low], my_arr[high] = my_arr[high], my_arr[low] else:
break
my_arr[start], my_arr[high]= my_arr[high], my_arr[start] return high
defquicksort(my_arr, start, end):
if start<end:
q = partition(my_arr, start, end)
quicksort(my_arr, start, q-1)
quicksort(my_arr, q+1, end)
arr = [15, 9, 11, 2 ,21,12,7] quicksort(arr, 0, 6)
print(arr)

In the above quick sort implementation, we have taken pivot as starting element of the list and quick sort() function is similar as the first method of implementation where we will call sub-lists recursively and partition() function is modified based on the pivot element.

Output:

quick sort in python 2

Conclusion

Finally, it is all about a quick sort algorithm in python. So far, we have seen the definition of quick sort, what is the logic behind quick sort implementation with step by step explanation, and how quick sort can be implemented using various methods in python with examples and corresponding outputs.

Recommended Articles

This is a guide to Quick Sort in Python. Here we discuss the introduction to Quick Sort, logic behind quick sort and examples. You may also have a look at the following articles to learn more –

  1. Merge Sort in Python
  2. Priority Queues in Python
  3. Python Map Function
  4. Python Pandas Join

Python Training Program (36 Courses, 13+ Projects)

36 Online Courses

13 Hands-on Projects

189+ Hours

Verifiable Certificate of Completion

Lifetime Access

Learn More

0 Shares
Share
Tweet
Share
Primary Sidebar
Python Tutorial
  • Sorting
    • Sorting in Python
    • Sorting Algorithms in Python
    • Bubble Sort in Python
    • Merge Sort in Python
    • Heap Sort in Python
    • Quick Sort in Python
    • Python Sorted Function
  • Basics Part I
    • Introduction To Python
    • What Is Python
    • Careers in Python
    • Advantages of Python
    • Uses of Python
    • Python Features
    • Python Fast And python psyco
    • Python ImportError
    • Benefits and Limitations of Using Python
    • What can I do with?Python
    • Is Python a scripting language
    • Is Python Object Oriented
    • Is Python Open Source
    • Python Socket Programming
    • Useful Tips on Python Programming
    • Python You Should Be Using It
    • Python Web Development
    • Python Programming Beginners Tutorails
    • Practical Python Programming for Non-Engineers
    • Python Programming for the Absolute Beginner
    • Versions of?Python
  • Basic Part II
    • Comments in Python
    • Finally in Python
    • Python Multiline Comment
    • Python Data Types
    • Python Variables
    • Python Variable Types
    • Python Global Variable
    • Python Variable Scope
    • Python Private Variables
    • Python Default Arguments
    • Python Command-line Arguments
    • Indentation in Python
    • Object in Python
    • Python Keywords
    • Python Literals
    • Pointers in Python
    • Iterators in Python
    • Python User Input
    • Python Enumerate
    • Python Commands
    • Type Casting in Python
    • Python Identifiers
    • Python Constants
    • What is NumPy in Python?
    • Cheat Sheet Python
  • Frameworks
    • Python Frameworks
    • Python Compilers
    • Python Editors
    • Best Compiler for Python
    • Python IDE for Windows
    • Python IDE on Linux
  • Installation
    • How To Install Python
    • Install Python on Linux
    • Install Python on Windows
    • Install Anaconda Python
  • Operator
    • Python Operators
    • Arithmetic Operators in Python
    • Python Comparison Operators
    • Logical Operators in Python
    • Assignment Operators in Python
    • Unary Operators in Python
    • String Operators in Python
    • Boolean Operators in Python
    • Identity Operators in Python
    • Python Bitwise Operator
    • Python Remainder Operator
    • Python Modulus Operator
  • Control Statement
    • Conditional Statements in Python
    • Control Statements in Python
    • If Condition in Python
    • If Statement in Python
    • If Else Statement in Python
    • else if Statement in Python
    • Nested IF Statement in Python
    • Break Statement in Python
    • Python Switch Statement
  • Loops
    • Loops in Python
    • For Loop in Python
    • While Loop in Python
    • Do While Loop in Python
    • Python Nested Loops
    • Python Infinite Loop
    • Python Event Loop
  • Function
    • Python Built-in Functions
    • Math Functions in Python
    • Python String Functions
    • Trigonometric Functions in Python
    • Python Input Function
    • Python Input String
    • Python String Operations
    • Python Stream
    • Python Multiline String
    • Python Regex
    • Python Regex Tester
    • Python regex replace
    • Python File Methods
    • Python Import CSV
    • Python Read CSV File
    • Python write CSV file
    • Python Delete File
    • Python File readline
    • Python if main
    • Python Main Method
    • List Method in Python
    • Python List Length
    • Recursive Function in Python
    • Copy List in Python
    • Python Range Function
    • Python Substring
    • Python list remove()
    • Python List Index
    • Python Set Function
    • Python len Function
    • Python eval()
    • Python Counter
    • ord Function in Python
    • strip Function in Python
    • Split Function in Python
    • Python Round Function
    • Python Map Function
    • Python String Join
    • Python format() Function
    • Python Contextlib
    • Python Compare Strings
    • Python Return Value
    • Python List count
    • Filter in Python
    • Python Slice String
    • Python Absolute Value
    • Python Trim String
    • Python Type Function
    • Lowercase in Python
    • Python xrange
    • Python yield
    • Python Find String
    • Max Function in Python
    • Python Power Function
    • pop() in Python
    • Python argparse
    • Python Pickle
    • Python Zip Function
    • Python Split String
    • super() in Python
    • Python Extend
    • Python String Replace
    • Python PEP8
    • Python Filter Function
    • Python if then else
    • Lambda in Python
    • Python BeautifulSoup
    • Python Sleep
    • Python Function Generator
    • Python @classmethod decorator
    • Python Endswith
    • Python BufferedReader
    • Python Async
    • Python Parser
    • Python SystemExit
    • Python pip
    • Python kwargs
  • Array
    • Arrays in Python
    • 2D Arrays In Python
    • 3d Arrays in Python
    • Multidimensional Array in Python
    • Python Array Functions
    • String Array in Python
    • Python Sort Array
    • Python Array Length
  • Inheritance
    • Inheritance in Python
    • Single Inheritance in Python
    • Multiple Inheritance in Python
    • Interface in Python
  • Exception
    • Python Exception Handling
    • Custom Exception in Python
    • Indentation Error in Python
    • Python IOError
    • Python EOFError
    • Python NotImplementedError
    • Python TypeError
    • Python ValueError
    • Python AssertionError
    • Python Unicode Error
    • Python NameError
    • Python StopIteration
    • Python OverflowError
    • Python KeyboardInterrupt
  • Advanced
    • Scope in Python
    • Python Collections
    • Constructor in Python
    • Destructor in Python
    • Python Overloading
    • Overriding in Python
    • Function Overloading in Python
    • Method Overloading in Python
    • Operator Overloading in Python
    • Method Overriding in Python
    • Encapsulation in Python
    • Static Method in Python
    • Assert in Python
    • Python References
    • Python Virtualenv
    • Python mkdir
    • Logistic Regression in Python
    • Dictionary in Python
    • Regular Expression in Python
    • Python Import Module
    • Python OS Module
    • Python Sys Module
    • Python Generators
    • Abstract Class in Python
    • Python File Operations
    • Sequences in Python
    • Stack in Python
    • Queue in Python
    • Tuples in Python
    • Python Magic Method
    • Python Sets
    • Python Set Methods
    • Priority Queues in Python
    • Reverse Engineering with Python
    • String Formatting in Python
    • Python isinstance
    • String Length Python
    • Python Concurrency
    • Python List
    • Python Initialize List
    • Python Unique List
    • Python Sort List
    • Python Reverse List
    • Python Empty List
    • List Comprehensions Python
    • List Operations in Python
    • Python Database Connection
    • Python SQLite
    • Python SQLite Create Database
    • Send Mail in Python
    • Bash Scripting and Python
    • Violent Python Book
    • NLP in Python
    • Matplotlib In Python
    • Gray Hat Python: Security
    • Python Subprocess
    • Python Threading Timer
    • Python Threadpool
    • Python Statistics Module
    • How to Call a Function in Python?
    • Python Curl
    • JSON in Python
    • Python json.dumps
    • Python Turtle
    • Python Unit Test
    • pass Keyword in Python
    • Tokenization in Python
    • Random Module in Python
    • Python Multiprocessing
    • Python getattr
    • Collection Module in Python
    • Print Statement in Python
    • Python Countdown Timer
    • Python Context Manager
    • File Handling in Python
    • Python Event Handler
    • Python Print Table
    • Python Docstring
    • Python Dictionary Keys
    • Python Iterator Dictionary
    • Python Class Attributes
    • Python Dictionary Methods
    • Namedtuple Python
    • Namedtuple Python
    • Namedtuple Python
    • Python Class Constants
    • Python Validation
    • Python Switch Case
    • Python Rest Server
    • Python Yield vs Return
    • Python Pickle vs JSON
  • Tkinter
    • Tkinter Widgets
    • Python Tkinter Button
    • Python Tkinter Canvas
    • Tkinter Frame
    • Tkinter LabelFrame
    • Python Tkinter Label
    • Tkinter Scrollbar
    • Tkinter Listbox
    • Tkinter Spinbox
    • Tkinter Checkbutton
    • Tkinter Menu
    • Tkinter Menubutton
    • Tkinter OptionMenu
    • Tkinter Messagebox
    • Tkinter Grid
    • Python Tkinter Entry
    • Tkinter after
    • Tkinter Colors
    • Tkinter Font
    • Tkinter PhotoImage
    • Tkinter TreeView
    • Tkinter Notebook
    • Tkinter Bind
    • Tkinter Icon
    • Tkinter Window Size
    • Tkinter Color Chart
    • Tkinter Slider
    • Tkinter Calculator
  • Programs
    • Patterns in Python
    • Star Patterns in Python
    • Swapping in Python
    • Factorial in Python
    • Fibonacci Series in Python
    • Reverse Number in Python
    • Palindrome in Python
    • Random Number Generator in Python
    • Prime Numbers in Python
    • Armstrong Number in Python
    • Strong Number in Python
    • Leap Year Program in Python
    • Square Root in Python
    • Python Reverse String
    • Python Object to String
    • Python Object to JSON
    • Python Classmethod vs Staticmethod
  • Python 3
    • Python 3 Commands
    • Python 3 cheat sheet
  • Interview Question
    • Python Interview Questions And Answers

Related Courses

Python Certification Course

Programming Languages Courses

Angular JS Certification Training

Footer
About Us
  • Blog
  • Who is EDUCBA?
  • Sign Up
  • Corporate Training
  • 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

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

EDUCBA
Free Software Development Course

Web development, programming languages, Software testing & others

*Please provide your correct email id. Login details for this Free course will be emailed to you
Book Your One Instructor : One Learner Free Class

Let’s Get Started

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

EDUCBA

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

Forgot Password?

EDUCBA
Free Software Development Course

Web development, programming languages, Software testing & others

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

Special Offer - Python Training Program (36 Courses, 13+ Projects) Learn More