Here are a few sorting algorithms I found interesting, and it will be good to know, which is a different thought process from these commonly used sorting algorithms. E.g. bubble sort, selection sort, insertion sort, quick sort, merge sort.
1. Pancake Sort
LeetCode 969. Pancake Sorting (Medium):
https://leetcode.com/problems/pancake-sorting/
- Description in short:
Given an array of integers arr, sort the array by performing a series of pancake flips.In one pancake flip we do the following steps:
- Choose an integer k where 1 <= k <= arr.length.
- Reverse the sub-array arr[1...k].For example, if arr = [3,2,1,4] and we performed a pancake flip choosing k = 3, we reverse the sub-array [3,2,1], so arr = [1,2,3,4] after the pancake flip at k = 3Return the k-values corresponding to a sequence of pancake flips that sort arr. Any valid answer that sorts the array within 10 * arr.length flips will be judged as correct.Input: arr = [3,2,4,1]
Output: [4,2,4,3]
Explanation:
We perform 4 pancake flips, with k values 4, 2, 4, and 3.
Starting state: arr = [3, 2, 4, 1]
After 1st flip (k = 4): arr = [1, 4, 2, 3]
After 2nd flip (k = 2): arr = [4, 1, 2, 3]
After 3rd flip (k = 4): arr = [3, 2, 1, 4]
After 4th flip (k = 3): arr = [1, 2, 3, 4], which is sorted.
Notice that we return an array of the chosen k values of the pancake flips.
- Diagram:
n1 n2 n3 n4 n5 n6
-- k=1
----- k=2
-------- k=3
----------- k=4
-------------- k=5
----------------- k=6If we look above patterns, we can only flip the pancake starting from beginning, so we kind get intuitive to do:Make the last element into the position first, then second last element etc.
step 1: flip the element to the front first
step 2: flip the element to the positionI like to think the above approach as rocket launch. First, pick the rocket, and place in the base position (index 0). Second, Launch the rocket to the right position.E.g. 3, 2, 4, 1
-> 4, 2, 3, 1 k=3 (step 1)
-> 1, 3, 2, 4 k=4 (step 2)
--
-> 3, 1, 2, 4 k=2 (step 1)
-> 2, 1, 3, 4 k=3 (step 2)
----
-> 1, 2, 3, 4 k=2 (step 2, since 1 is already in the index 0 position)
output = [3, 4, 2, 3, 2]
To pancake sort an array of size n, need maximum 2N flips. Because for each item, we ended up flip maximum 2 steps, and there are n items.
- Code:
# Time O(N^2) Space O(1)
# Note. it's maximum 2N flips, but for each flip, we are using reverse function of O(N) time complexity, so it is total O(2N^2)Time.
def pancakeSort(self, A: List[int]) -> List[int]:
if not A: return None
# Time O(N), Space O(1)
def reverse(i,j):
while i < j:
A[i],A[j] = A[j],A[i]
i += 1
j -= 1
size = len(A)
max_value = size
result = []
for e in range(size-1, 0, -1): #find the element need to be placed
max_index = A.index(max_value) if max_index != e: #reverse the element to the front
if max_index != 0:
reverse(0, max_index)
result.append(max_index+1) #reverse the element to the correct position
reverse(0,e)
result.append(e+1)
max_value -= 1return result
2. Sort Colors (Dutch National Flag Problem)
LeetCode 75. Sort Colors: https://leetcode.com/problems/sort-colors/
- Description in short:
Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.Follow up:
- Could you solve this problem without using the library's sort function?
- Could you come up with a one-pass algorithm using only O(1) constant space?
- Diagram:
pR pG pB
| | |
[0, 0, 0, 1, 1, 1, 2, 2, 2]Since we need to solve this problem in O(1) space, we can use pointers. The simpliest way is that we can use 3 pointers, each pointer mark the start of each R,G,B index position. This can be optimized using 2 pointers, p0 is the rightmost boundary of 0s, p2 is the leftmost boundry of 2s. And we have pointer i, iterate the array from left to right.We can also imagine everything outside the array range is already sorted.Dutch National Flag Problem
p0 p2
| |
0, 0 [2, 0, 2, 1, 1, 0] 2, 2
|
i
- Code:
# Time O(N) Space O(1)
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
def swap(i, j):
nums[i], nums[j] = nums[j], nums[i]
# p0 is the rightmost boundary of 0s, p2 is the leftmost boundary of 2s
p0, p2 = 0, len(nums) - 1
index = 0
while index <= p2:
cur = nums[index]
if cur == 0:
swap(index, p0)
index += 1
p0 += 1
elif cur == 1:
index += 1
else:
swap(index, p2)
p2 -= 1