Quicksort program in Python
In this post, you will learn about the Quick Sort and how to write a quick sort program using the Python programming language.
Quick sort is widely used sorting algorithm, it is developed by C.A.R.
In quick sort, it first selects one element called a pivot. After that, it rearranges the elements in the array in such a way that all the elements less than the pivot element are appearing before the pivot and all the elements greater than the pivot are appearing after the pivot. After this, partitioning the pivot is in the final position.
Quick sort is the fastest algorithm and is the best choice. It is faster than other algorithms like bubble sort, selection sort, and insertion sort. But this can be complex on the flip side.
Quick Sort Example
These are the quick sorting techniques.
We choose the first element as a pivot. So set loc at 0 index, left at 0 index and right at 5th index.
Now scan from right to left until a[loc] < a[right], then decrease the value of right.
Since a[loc] > a[right], interchange the two values and set loc = right.
Now scan from left to right until a[loc] > a[left], then increment the value of left.
Since a[loc] < a[left], interchange the values and set loc = left.
Since from right to left, since a[loc] < a[right], decrease the value of right.
Start scanning from left to right. Since a[loc] > a[left], increment the value of left.
Since a[loc] > a[right], interchange the two values and set loc = right.
Complexity of Quick sort
Suppose n is the number of elements in an array.
Best Time Complexity - O(n log(n))
Worst Time Complexity - O(n2)
Quick sort program in Python
def QuickSort(arr):
arr_len = len(arr)
if arr_len < 2:
return arr
# Position of the partitioning element
pos = 0
# for loop
for i in range(1, arr_len):
if arr[i] <= arr[0]:
pos += 1
temp = arr[i]
arr[i] = arr[pos]
arr[pos] = temp
temp = arr[0]
arr[0] = arr[pos]
arr[pos] = temp
# Sorts the elements to the left of pivot
left = QuickSort(arr[0:pos])
# Sorts the elements to the right of pivot
right = QuickSort(arr[pos+1:arr_len])
# Merging everything together
arr = left + [arr[pos]] + right
return arr
# Sorted array
sorted_array = [98,43,25,78,94,39]
print("Original Array: ",sorted_array)
print("Sorted Array: ",QuickSort(sorted_array))
Output of the above code:
Original Array: [98, 43, 25, 78, 94, 39]
Sorted Array: [25, 39, 43, 78, 94, 98]
Related Articles
Convert Python list to numpy arrayConvert string to list Python
Python program to list even and odd numbers of a list
Python loop through list
Sort list in descending order Python
Convert array to list Python
Python take screenshot of specific window
Web scraping Python BeautifulSoup
Check if two strings are anagrams Python
Python program to add two numbers
Print new line python
Python for loop index
Convert List to Dataframe Python
numpy random choice
Dictionary inside list python
Check if list is empty Python
Python raise keyword
Python program to get the largest number from a list
Python program to map two lists into a dictionary