Comparison of Quick Sort, Merge Sort and Heap Sort
Data Structures and Algorithms Note
Quick Sort and Merge Sort are Divide and Conquer algorithm
Quick Sort
Step
- pick a pivot (in this example will always pick the last element as a pivot)
- do partition then return the pivot index
- do quick sort for array before the pivot
- do quick sort for array after the pivot
when all subarray finished with partition, the array sorted
def quick_sort(array, start, end):
if (start < end):
# p is partitioning index, array[p]
# is at right place
p_index = partition(array, start, end)
# Sort elements before partition
# and after partition
quick_sort(array, start, p_index- 1)
quick_sort(array, p_index + 1, end)Note: if (start < end) can prevent doing quick_sort when start and pivot both are 0 and end is 1-> quick_sort(array, start=0, (0-1)= -1) or quick_sort(array, (0+1)=1, end=1) , like array = [1,2]
How to implement partition
Find the item from the start index that value is greater than the pivot, it should be put on the right side, while finding the position from the end index that value is less than the pivot and it should be put on the left side. Swap these two items (left to right and right to left), but we need to set a condition before the swap, that is only if start index < end, otherwise the start index is already at the right side of the end index item, no need to swap.
When all the other items are put in the correct position, swap the pivot to the index start.
# set pivot as end value
def partition(array, start, end):
pivot = array[end]
p_index = end
while start < end:
while start < len(array) and array[start] < pivot:
start += 1
while array[end] >= pivot:
end -= 1
if start < end:
array[start], array[end] = array[end], array[start]
array[p_index], array[start] = array[start], array[p_index]
return p_index# set pivot as start value
def partition(arr,start,end):
pivot = arr[start]
p_index = start
while start < end:
while start < len(arr) and arr[start] <= pivot:
start += 1
while arr[end] > pivot:
end -= 1
if start < end:
arr[start], arr[end] = arr[end], arr[start]
arr[p_index], arr[end] = arr[end], arr[p_index]
return endTime Complexity: O(n logn)
Space Complexity: O(n²)
Merge Sort
Step
- Find the middle point to divide the array into two halves:
mid = len(arr)//2 - Call merge sort for left half:
left_arr = arr[:mid]
Call merge_sort(left_arr) - Call merge sort for second half:
right_arr = arr[mid:]
Call merge_sort(right_arr) - Merge the two halves sorted in step 2 and 3:
Call merge(left_arr, right_arr)
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
left_arr = arr[:mid]
right_arr = arr[mid:]
merge_sort(left_arr)
merge_sort(right_arr)
#merge
i = 0
j = 0
k = 0
while i < len(left_arr) and j < len(right_arr):
if left_arr[i] < right_arr[j]:
arr[k] = left_arr[i]
i += 1
else:
arr[k] = right_arr[j]
j += 1
k += 1
while i < len(left_arr):
arr[k] = left_arr[i]
i +=1
k +=1
while j < len(right_arr):
arr[k] = right_arr[j]
j += 1
k += 1
return arrTime Complexity: O(n logn)
Space Complexity: O(n)
Heap Sort
Heap sort is based on Binary Heap data structure. A Binary Heap is a Complete Binary Tree (every level, except the level of leaves, is completely filled, the children can be two or one at the leaf level, and all nodes are as far left as possible.
And it can be created as an array that has this feature:
If the parent node is stored at index I, the left child can be calculated by 2 * I + 1 and the right child by 2 * I + 2
Heapify
The process of reshaping a binary tree into a heap data structure. Heapify procedure must be performed in the bottom-up order when children nodes are heapified.
Heap sort function
def heapify(arr, n, i):
largest = i # Initialize largest as root
l = 2 * i + 1 # left = 2*i + 1
r = 2 * i + 2 # right = 2*i + 2
# See if left child of root exists and is
# greater than root
if l < n and arr[largest] < arr[l]:
largest = l
# See if right child of root exists and is
# greater than root
if r < n and arr[largest] < arr[r]:
largest = r
# Change root, if needed
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i] # swap
# Heapify the root.
heapify(arr, n, largest)
# The main function to sort an array of given size
def heapSort(arr):
n = len(arr)
# Build a maxheap.
for i in range(n//2 - 1, -1, -1):
heapify(arr, n, i)
# One by one extract elements
for i in range(n-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i] # swap
heapify(arr, i, 0)
# Driver code
arr = [12, 11, 13, 5, 6, 7]
heapSort(arr)
n = len(arr)
print("Sorted array is")
for i in range(n):
print("%d" % arr[i],end=" ")Time Complexity: The time complexity of heapify is O(logn). The time complexity of heapSort() is O(n) and the overall time complexity of Heap Sort is O(n logn).
