QuickSort

QuickSort is one of the most commonly used sorting algorithms, known for its efficiency and simplicity. It belongs to the category of divide and conquer algorithms.

The algorithm works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot.

This process is performed recursively on the sub-arrays until the entire array is sorted.

How QuickSort Works

1. Choose a pivot element from the array. This element will be used to partition the array.
2. Partition the array into two sub-arrays - one containing elements less than the pivot and the other containing elements greater than the pivot.
3. Recursively apply the same process to the sub-arrays until the entire array is sorted.

Python Implementation

Here's a Python implementation of the QuickSort algorithm:

1import random
2
3# Function to perform QuickSort
4
5def quick_sort(arr):
6    if len(arr) <= 1:
7        return arr
8    else:
9        pivot = arr[0]
10        lesser = [x for x in arr[1:] if x <= pivot]
11        greater = [x for x in arr[1:] if x > pivot]
12        return quick_sort(lesser) + [pivot] + quick_sort(greater)
13
14
15if __name__ == '__main__':
16    # Generate a random list
17    lst = [random.randint(0, 100) for _ in range(10)]
18    print('Original List:', lst)
19    sorted_lst = quick_sort(lst)
20    print('Sorted List:', sorted_lst)

In this example, we define a function quick_sort that recursively partitions the input list and sorts it in ascending order. We then generate a random list and sort it using the quick_sort function.

Feel free to modify the code and experiment with different input lists to see how QuickSort works.

xxxxxxxxxx

import random

​

# Function to perform QuickSort

​

def quick_sort(arr):

    if len(arr) <= 1:

        return arr

    else:

        pivot = arr[0]

        lesser = [x for x in arr[1:] if x <= pivot]

        greater = [x for x in arr[1:] if x > pivot]

        return quick_sort(lesser) + [pivot] + quick_sort(greater)

​

​

if __name__ == '__main__':

    # Generate a random list

    lst = [random.randint(0, 100) for _ in range(10)]

    print('Original List:', lst)

    sorted_lst = quick_sort(lst)

    print('Sorted List:', sorted_lst)