Quick Sort Pseudocode
Quick Sort is a divide and conquer algorithm that selects a pivot element and partitions the array so that elements less than the pivot are on the left, and those greater than the pivot are on the right. Then it recursively sorts the left and right parts.
Pseudocode:
QuickSort(arr, low, high)
1. If low < high:
pivot = Partition(arr, low, high) // Partition the array around the pivot
QuickSort(arr, low, pivot-1) // Recursively sort left side
QuickSort(arr, pivot+1, high) // Recursively sort right side
Partition(arr, low, high)
1. pivot = arr[high] // Choose last element as pivot
2. i = low - 1
3. For j = low to high-1:
If arr[j] <= pivot:
i = i + 1
Swap arr[i] and arr[j]
4. Swap arr[i+1] and arr[high]
5. Return i+1 // Return pivot indexTime Complexity:
- Best/Average case: When the partitioning divides the array evenly, the time complexity is
O(n log n). - Worst case: When the pivot is the smallest or largest element (poor partitioning), the time complexity becomes
O(n²).
Merge Sort Pseudocode
Merge Sort is another divide and conquer algorithm. It divides the array into two halves, recursively sorts each half, and then merges the two sorted halves.
Pseudocode:
MergeSort(arr, low, high)
1. If low < high:
mid = (low + high) / 2
MergeSort(arr, low, mid) // Sort left half
MergeSort(arr, mid+1, high) // Sort right half
Merge(arr, low, mid, high) // Merge the two halves
Merge(arr, low, mid, high)
1. Create temporary arrays Left[] and Right[]
2. Copy elements from arr[low..mid] into Left[] and arr[mid+1..high] into Right[]
3. Merge the temporary arrays back into arr[low..high] by comparing elements
4. Copy remaining elements from Left[] and Right[] (if any)Time Complexity:
- Best, Average, and Worst case: Since Merge Sort always divides the array into two halves and merges them, the time complexity is always
O(n log n).
Space Complexity:
Merge Sort uses extra space for the temporary arrays, so its space complexity is O(n).
0 Comments