What Is Quick Sort in Data Structure?

//

Scott Campbell

Quick Sort is a widely used sorting algorithm in computer science. It is known for its efficient performance and is often favored over other sorting algorithms like Bubble Sort and Insertion Sort. Quick Sort follows the divide-and-conquer approach to sort an array or list of elements.

How does Quick Sort work?

The main idea behind Quick Sort is to select a pivot element from the array and partition the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then recursively sorted.

To understand the process, let’s take an example:

  • Consider an unsorted array: [7, 2, 1, 6, 8, 5]
  • We select a pivot element, which can be any element from the array. Let’s choose the last element as our pivot – in this case, ‘5’.
  • We then rearrange the array in such a way that all elements smaller than the pivot are placed on its left side and all elements greater than the pivot are placed on its right side.

    In our example, after partitioning around the pivot ‘5’, we get: [2, 1] [5] [7, 6, 8].

  • Now we have two sub-arrays – one containing elements smaller than ‘5’ and another containing elements greater than ‘5’. We recursively apply the same process to these sub-arrays.
  • After sorting each sub-array separately using Quick Sort recursively, we finally concatenate them back together with the pivot element in between. In our example: [1, 2] [5] [6, 7 ,8].

Implementing Quick Sort in Code

Let’s take a look at a simple implementation of Quick Sort in Python:


def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[-1]
        smaller = [x for x in arr[:-1] if x <= pivot]
        greater = [x for x in arr[:-1] if x > pivot]
        return quick_sort(smaller) + [pivot] + quick_sort(greater)
        
# Testing the code
arr = [7, 2, 1, 6, 8, 5]
sorted_arr = quick_sort(arr)
print(sorted_arr)

Running this code will output: [1, 2, 5, 6, 7, 8], which is the sorted version of the initial array.

Time Complexity of Quick Sort

The time complexity of Quick Sort depends on the choice of pivot. In the average case, it has a time complexity of O(n log n), where ‘n’ is the number of elements to be sorted.

However, Quick Sort can have a worst-case time complexity of O(n^2) when the chosen pivot is always the smallest or largest element. This can be mitigated by using randomized selection or selecting a median-of-three as the pivot.

Conclusion

Quick Sort is an efficient sorting algorithm that follows the divide-and-conquer approach. It provides faster sorting compared to other algorithms like Bubble Sort and Insertion Sort. Understanding how Quick Sort works and implementing it in your code can greatly improve your efficiency when dealing with large datasets.

Discord Server - Web Server - Private Server - DNS Server - Object-Oriented Programming - Scripting - Data Types - Data Structures

Privacy Policy