Introduction
Sorting algorithms play a crucial role in computer science, as these help us to arrange data in a specific order for efficient searching, analysis, & processing. Among the various sorting algorithms, quick sort & merge sort are very popular among programmers as two popular & efficient methods. The quick sort is known for its speed & efficiency, while the merge sort is recognized for its stability & consistent performance. Both algorithms have unique approaches to sorting data, but understanding their differences is crucial for selecting the appropriate algorithm per the code's demand.
In this article, we will discuss the concepts of quick sort & merge sort, understand their algorithms, provide step-by-step explanations, & compare their characteristics.
Quick Sort
Quick sort is a powerful divide-and-conquer algorithm that efficiently sorts an array by selecting a pivot element and partitioning 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 until the entire array is sorted.
The main idea behind quick sort is to divide the problem into smaller subproblems, solve them recursively, and then combine the solutions to solve the original problem. By selecting a pivot element and partitioning the array around it, quick sort ensures that the pivot element is in its final sorted position, and all elements to its left are smaller, while all elements to its right are larger.
One advantage of quick sort is its efficiency, especially for large arrays. On average, quick sort has a time complexity of O(n log n), which makes it one of the fastest sorting algorithms.
Algorithm of Quick Sort
The quick sort algorithm follows these steps:
1. Choose a pivot element from the array (usually the first, last, or middle element).
2. Partition the array into two sub-arrays: elements less than the pivot & elements greater than the pivot.
3. Recursively apply steps 1 & 2 to the sub-arrays until the sub-arrays are empty or contain only one element.
4. Combine the sorted sub-arrays to obtain the final sorted array.
Note: The main idea of the quick sort algorithm is the partitioning step, which ensures that the pivot element is in its final sorted position & all elements to its left are smaller, while all elements to its right are larger.
Steps to sort an array using the quick sort algorithm
1. Select a pivot element from the array (e.g., the last element).
2. Initialize two pointers, left and right, pointing to the start and end of the array, respectively.
3. Move the left pointer forward until an element greater than the pivot is found.
4. Move the right pointer backward until an element smaller than the pivot is found.
5. Swap the elements at the left & right pointers if the left pointer is less than or equal to the right pointer.
6. Repeat steps 3-5 until the left pointer is greater than the right pointer.
7. Swap the pivot element with the element at the right pointer.
8. Recursively apply steps 1-7 to the sub-array to the left of the right pointer & the sub-array to the right of the right pointer.
9. Repeat until all sub-arrays are sorted.
For example :
def quicksort(arr, low, high):
if low < high:
pivot_index = partition(arr, low, high)
quicksort(arr, low, pivot_index - 1)
quicksort(arr, pivot_index + 1, high)
def partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
arr = [64, 34, 25, 12, 22, 11, 90]
quicksort(arr, 0, len(arr) - 1)
print(arr)
Output:
[11, 12, 22, 25, 34, 64, 90]
The `quicksort` function is called with the array, the low index (initially 0), and the high index (initially the last index of the array). The `partition` function selects the last element as the pivot and partitions the array around it. The algorithm recursively sorts the sub-arrays until the entire array is sorted.
19+ registered 
