Quick Sort

Quicksort is a popular sorting algorithm that is widely used in computer science and programming. It is an efficient, in-place sorting algorithm that is based on the divide-and-conquer approach. Quicksort is a comparison-based sorting algorithm, meaning that it sorts elements by comparing them to each other. It is a recursive algorithm, meaning that it breaks down a problem into smaller problems and solves them. Quicksort is often used for sorting large datasets, due to its efficiency. In this article, we will discuss the basics of Quicksort, its time and space complexity, and provide some code examples in Python.

What is Quicksort?

Quicksort is a sorting algorithm that works by partitioning a list of elements into two parts – one part with elements that are less than a given pivot element, and the other part with elements that are greater than the pivot element. The algorithm then recursively sorts the two parts. Quicksort has the following steps:

• Select a pivot element from the list.
• Partition the list around the pivot element.
• Recursively sort the two parts.

Let’s look at an example of Quicksort in action.

Example of Quicksort

Suppose we have a list of numbers: [8, 4, 1, 6, 5, 7, 3, 2] and we want to sort them in ascending order. We can use Quicksort to do this.

First, we select a pivot element. For this example, let’s select the first element, 8. Next, we partition the list around the pivot element. This means that we move all elements that are less than 8 to the left of 8 and all elements greater than 8 to the right of 8. This results in the following partitioned list: [4, 1, 6, 5, 7, 3, 2, 8].

Finally, we recursively sort the two parts. We apply Quicksort to the left part [4, 1, 6, 5, 7, 3, 2] and the right part [8]. This results in the following sorted list: [1, 2, 3, 4, 5, 6, 7, 8].

How does Quicksort Work?

Quicksort is an efficient sorting algorithm that uses a divide-and-conquer approach. It works by picking a pivot element from the array and then partitioning the array into two sub-arrays. The elements in the first sub-array are all less than the pivot element while the elements in the second sub-array are all greater than the pivot element. The two sub-arrays are then sorted recursively using quicksort until all elements in the array are sorted.

The steps of Quicksort are as follows:

• Pick a pivot element from the array. This is usually the first or the last element.
• Partition the array into two sub-arrays. All elements in the first sub-array should be less than the pivot element while all elements in the second sub-array should be greater than the pivot element.
• Recursively apply Quicksort to the two sub-arrays.
• When all elements in the sub-arrays have been sorted, combine the sorted sub-arrays and return the sorted array.

The advantages of Quicksort are that it is relatively easy to understand, fast, and can be implemented in place. The disadvantages are that it is not stable and can be vulnerable to worst-case scenarios.

Time Complexity of Quicksort

The time complexity of Quicksort depends on whether it is implemented as an in-place algorithm or not. The best, average, and worst case time complexities of Quicksort are given below.

Best Case: O(n log n)

The best case time complexity of Quicksort occurs when the partitioning process always results in two equal-sized subarrays. In this case, Quicksort has a time complexity of O(n log n).

Average Case: O(n log n)

The average case time complexity of Quicksort is also O(n log n). This is because the partitioning process is random and the size of the two subarrays produced is mostly equal.

Worst Case: O(n^2)

The worst case time complexity of Quicksort occurs when the partitioning process always produces two subarrays of unequal size. In this case, Quicksort has a time complexity of O(n^2).

Space Complexity of Quicksort

The space complexity of Quicksort is O(log n). This is because Quicksort is an in-place sorting algorithm and it only requires a constant amount of extra space for the partitioning process.

Example of Quicksort in Python

We can implement Quicksort in Python using the following code:

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)

arr = [8, 4, 1, 6, 5, 7, 3, 2]
sorted_arr = quicksort(arr)

print(sorted_arr)

# Output: [1, 2, 3, 4, 5, 6, 7, 8]

Conclusion

Quicksort is a popular sorting algorithm that is based on the divide-and-conquer approach. It is an efficient, in-place sorting algorithm that has a time complexity of O(n log n) in the best, average, and worst cases and a space complexity of O(log n). Quicksort is often used for sorting large datasets due to its efficiency.

Exercises

def quicksort(arr): 
  if len(arr) <= 1: 
    return arr 
  pivot = arr[len(arr) // 2] 
  left = [x for x in arr if x < pivot] 
  middle = [x for x in arr if x == pivot] 
  right = [x for x in arr if x > pivot] 
  return quicksort(left) + middle + quicksort(right) 

def quicksort_time_complexity(arr): 
  if len(arr) <= 1: 
    return 0 
  else: 
    return len(arr) * quicksort_time_complexity(arr[len(arr) // 2:]) + quicksort_time_complexity(arr[:len(arr) // 2])

def quicksort_space_complexity(arr): 
  if len(arr) <= 1: 
    return 0 
  else: 
    return len(arr) + quicksort_space_complexity(arr[len(arr) // 2:]) + quicksort_space_complexity(arr[:len(arr) // 2])

def quicksort(arr): 
  if len(arr) <= 1: 
    return arr 
  pivot = arr[len(arr) // 2] 
  left = [x for x in arr if x < pivot] 
  middle = [x for x in arr if x == pivot] 
  right = [x for x in arr if x > pivot] 
  return quicksort(left) + middle + quicksort(right) 

def partition(arr, pivot): 
  left = [x for x in arr if x < pivot] 
  right = [x for x in arr if x > pivot] 
  return left, right