Master the divide-and-conquer approach with Quicksort and Merge Sort. Learn how these efficient algorithms tackle complex sorting problems.
def quick_sort(arr, left=0, right=None):
if right is None:
right = len(arr) - 1
if left < right:
pivot_index = partition(arr, left, right)
quick_sort(arr, left, pivot_index - 1)
quick_sort(arr, pivot_index + 1, right)
return arr
def partition(arr, left, right):
pivot = arr[right]
i = left - 1
for j in range(left, right):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[right] = arr[right], arr[i + 1]
return i + 1def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return resultarr1 = [64, 34, 25, 12, 22, 11, 90]
print('Quicksort:', quick_sort(arr1.copy()))
print('Merge sort:', merge_sort(arr1.copy()))Implement a hybrid sorting algorithm that uses both Quicksort and Insertion Sort.
Extend the merge sort algorithm to handle k sorted arrays simultaneously.
arrays = [
[1, 4, 7],
[2, 5, 8],
[3, 6, 9]
]
def k_way_merge(arrays):
import heapq
result = []
heap = []
for i, arr in enumerate(arrays):
if arr:
heapq.heappush(heap, (arr[0], i, 0))
while heap:
val, arr_idx, elem_idx = heapq.heappop(heap)
result.append(val)
if elem_idx + 1 < len(arrays[arr_idx]):
next_tuple = (arrays[arr_idx][elem_idx + 1], arr_idx, elem_idx + 1)
heapq.heappush(heap, next_tuple)
return result
print(k_way_merge(arrays)) # Output: [1, 2, 3, 4, 5, 6, 7, 8, 9]Modify both sorting algorithms to work with custom comparison functions.
people = [
{ 'name': 'Alice', 'age': 30 },
{ 'name': 'Bob', 'age': 25 },
{ 'name': 'Charlie', 'age': 35 }
]
# Sort by age
people_sorted_by_age = sorted(people, key=lambda x: x['age'])
# Sort by name
people_sorted_by_name = sorted(people, key=lambda x: x['name'])The following LeetCode problems are excellent resources for practicing sorting algorithms and preparing for technical interviews.
Note: Previously, this course referenced the CodeSignal Arcade, which is no longer available. The LeetCode problems above follow the same principles and are an excellent alternative for practicing sorting algorithms and preparing for technical interviews.