❮ Python Max List Element Python Os Tcgetpgrp ❯

Python Quick Sort

Python3 Examples

Quick Sort uses the divide and conquer strategy to divide a list into smaller and larger sub-lists, and then recursively sorts the two sub-lists.

The steps are:

Select a pivot: Choose an element from the list, known as the "pivot";
Partition: Reorder the list so that all elements less than the pivot come before it, and all elements greater than the pivot come after it (elements equal to the pivot can be on either side). After this partitioning, the pivot is in its final position;
Recursively sort sub-lists: Recursively apply the above steps to the sub-list of elements with smaller values and separately to the sub-list with greater values.

The base case of the recursion is when the list has zero or one elements, which is inherently sorted.

There are several methods for selecting the pivot, and this choice significantly affects the sorting performance.

Example

def partition(arr, low, high): 
    i = (low - 1)         # Index of the smaller element
    pivot = arr[high]     # Pivot

    for j in range(low, high): 

        # If current element is smaller than or equal to pivot 
        if arr[j] <= pivot: 

            i = i + 1 
            arr[i], arr[j] = arr[j], arr[i] 

    arr[i + 1], arr[high] = arr[high], arr[i + 1] 
    return (i + 1) 


# arr[] --> Array to be sorted
# low  --> Starting index
# high  --> Ending index

# Function to do Quick sort
def quickSort(arr, low, high): 
    if low < high: 

        pi = partition(arr, low, high) 

        quickSort(arr, low, pi - 1) 
        quickSort(arr, pi + 1, high) 

arr = [10, 7, 8, 9, 1, 5] 
n = len(arr) 
quickSort(arr, 0, n - 1) 
print("Sorted array:") 
for i in range(n): 
    print("%d" % arr[i]),

Executing the above code outputs:

Sorted array:
1
5
7
8
9
10

Python3 Examples

❮ Python Max List Element Python Os Tcgetpgrp ❯