Sitemap

Sorting Algorithms

6 min readMay 5, 2020

--

Dive into Sorting Algorithms in Pseudocode

Press enter or click to view image in full size
Algorithms are a series of step by step instructions for solving a problem.

Pseudocode is an algorithm written in a way that resembles computer code. I am trying to understand the key ideas of each sorting algorithm as many as I can. It’s not easy to grasp at first. Probably, I could better understand these algorithms writing with my pen on papers. For implementing the more efficient algorithms, I need to study advanced data structures like Heap. I will keep studying algorithms and data structures.

Basic Sorting Algorithms

  • Bubble Sort
Bubble Sort (image credit: Rithm School)
// BubbleSort: compare with and swap the very next element each passfor pass = 1 to n-1
for i = 1 to n-pass
if (Arr[i - 1] > Arr[i]) // if leftElement > rightElement
Arr[i - 1] <-> Arr[i] // swap(leftElement, rightElement)
return Arr
  • Selection Sort
Selection Sort (image credit: Rithm School)
// SelectionSort: find min value, swap with Arr[i], move to the leftfor i = 0 to n-2
min = i // min: array index to have minimum value
for j = i+1 to n-1 { // find min in Arr[i] ~ Arr[n-1]
if (Arr[j] < Arr[min])
min = j
}
Arr[i] <-> Arr[min]
return Arr
// another pseudocoderepeat (numOfElements - 1) times
set the first unsorted element as the minimum
for each of the unsorted elements
if element < currentMinimum
set element as new minimum
swap minimum with first unsorted position
  • Insertion Sort
Insertion Sort (image credit: Rithm School)
// InsertionSort: compare the first element in the right unsorted area with the last element in the left sorted area, find a spot to be inserted. for i = 1 to n-1 {
CurrentElement = Arr[i]
j <- i - 1
while (j >= 0) and (Arr[j] > CurrentElement) {
Arr[j + 1] = Arr[j] // shift to the right
j <- j - 1
}
Arr[j + 1] <- CurrentElement
}
return Arr
// another pseudocodefor i <- 2 to length[Arr]
do key <- Arr[i]
insert Arr[i] into the sorted
sequence Arr[1 ... i-1].
j <- i - 1
while j > 0 and Arr[j] > key
do Arr[j + 1] <- Arr[j]
j <- j - 1
Arr[j + 1] <- key

More efficient Sorting Algorithms

  • Merge Sort
Merge Sort
MergeSort(arr[], l,  r) If r > l
1. Find the middle point to divide the array into two halves:
middle mid = (l+r)/2
2. Call mergeSort for first half:
mergeSort(arr, l, mid)
3. Call mergeSort for second half:
mergeSort(arr, mid+1, r)
4. Merge the two halves sorted in step 2 and 3:
merge(arr, l, mid, r)
// MergeSort: split into two subarrays. Divide-and-conquer algorithmmergeSort(arr, l, r){ if (l < r) { // arr[l...r]
mid = r <- (l + r) / 2
mergeSort(arr, l, mid)
mergeSort(arr, mid+1, r)
merge(arr[l...mid], arr[mid+1, r]) // merge the subarrays
}
}
merge(arr[l...mid], arr[mid+1, r]){ 1. Create temporary sorted arrays
2. Copy data to temp arrays L[] and R[]
3. Merge the temp arrays back into arr[l..r]
4. Copy the remaining elements of L[], if there are any
5. Copy the remaining elements of R[], if there are any
}
  • Quick Sort
Press enter or click to view image in full size
Quick Sort (image credit: GeeksforGeeks)

QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways. (src: GeeksforGeeks)

Get Youra Cho’s stories in your inbox

Join Medium for free to get updates from this writer.

The ways of picking a pivot are below:

  1. Always pick first element as pivot.
  2. Always pick last element as pivot (implemented below).
  3. Pick a random element as pivot.
  4. Pick median as pivot.
// QuickSort: partition an array with a pivot. Divide-and-conquer algorithmStep 1 − Make the right-most index value pivot
Step 2 − partition the array using pivot value
Step 3 − quicksort left partition recursively
Step 4 − quicksort right partition recursively
------------------------------------------------------------------
quickSort(A, left, right) {

if (left < right) { // A[left ... right]

pi = partition(A, left, right) // pivot index
quickSort(A, left, pi-1) // smaller group than pivot
quickSort(A, pi+1, right) // larger group than pivot
}
}
partition(A, left, right) {
pivot = A[right] // pick the last element as pivot here
i = left - 1 // i: index of smaller element
for (j = left; j <= right- 1; j++) // j: loop variable
{
// If current element is smaller than the pivot
if (A[j] < pivot)
{
i = i + 1; // increment index of smaller element
swap A[i] and A[j]
}
}
swap A[i + 1] and A[right]
return i + 1
}

Illustration of the partition(arr, left, right)

arr[] = {10, 80, 30, 90, 40, 50, 70}
Indexes: 0 1 2 3 4 5 6

left = 0, right = 6, pivot = arr[right] = 70
Initialize index of smaller element, i = -1

Traverse elements from j = left to right -1
j = 0 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])
i = 0
arr[] = {10, 80, 30, 90, 40, 50, 70} // No change as i and j
// are same

j = 1 : Since arr[j] > pivot, do nothing
// No change in i and arr[]

j = 2 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])
i = 1
arr[] = {10, 30, 80, 90, 40, 50, 70} // We swap 80 and 30

j = 3 : Since arr[j] > pivot, do nothing
// No change in i and arr[]

j = 4 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])
i = 2
arr[] = {10, 30, 40, 90, 80, 50, 70} // 80 and 40 Swapped
j = 5 : Since arr[j] <= pivot, do i++ and swap arr[i] with arr[j]
i = 3
arr[] = {10, 30, 40, 50, 80, 90, 70} // 90 and 50 Swapped

We come out of loop because j is now equal to right-1.
Finally we place pivot at correct position by swapping arr[i+1] and arr[right] (or pivot) arr[] = {10, 30, 40, 50, 70, 90, 80} // 80 and 70 Swapped
Quick Sort (Source: GeeksforGeeks)
  • Heap Sort
Heap Sort (Source: GeeksforGeeks)
  • Counting Sort
Step 1: Take a count array to store the count of each unique object.
Step 2:
Modify the count array such that each element at each index
stores the sum of previous counts.
Step 3: Output each object from the input sequence followed by
decreasing its count by 1.
To take negative numbers as well, find the minimum element and store count of that minimum element at zero index.
Counting Sort (Source: GeeksforGeeks)
const k = 10; // k: range, c[0,…k]
var sortArray = function(nums) {
let sorted = new Array(nums.length).fill(0);
// 1. Create a count array to store count of individual
let count = new Array(k+1).fill(0);
// 2.Store counts of each number
for (let i = 0; i < nums.length; i++) {
count[nums[i]]++ ; // ++count[5] : 1
}
// 3.Modify count[i] so that count[i] now contains actual
// position of this number in output array
for (let i = 1; i <= k; i++) {
count[i] += count[i-1];
}
// 4. Build the sorted array
for (let i = 0; i < nums.length; i++) {
sorted[count[nums[i]]-1] = nums[i];
count[nums[i]] — ;
}
// 5. Copy the sorted array to nums
for (let i = 0; i < nums.length; i++) {
nums[i] = sorted[i];
}
return nums;
};
  • Radix Sort
Radix Sort (Source: GeeksforGeeks)
  • Bucket sort
Bucket Sort (Source: GeeksforGeeks)

Following is the algorithm for shell sort.

Step 1 − Initialize the value of h
Step 2 − Divide the list into smaller sub-list of equal interval h
Step 3 − Sort these sub-lists using insertion sort
Step 3 − Repeat until complete list is sorted
Shell Sort (Source: GeeksforGeeks)
  • Tree Sort
Tree Sort (Source: GeeksforGeeks)

Time and Space Complexity of Sorting Algorithms

The table is a good summary of the time and space complexity of array sorting algorithms.

The comparison of the time and space complexity of Array sorting algorithms

--

--

Youra Cho
Youra Cho

Written by Youra Cho

Software Engineer enjoying a creamy latte, sumo citrus, and fresh air from redwoods.