Sort algorithms and their implementations
Sorting algorithms are one of the most popular algorithms in programming, and together with searching algorithms, they make data more manageable.
Sorting algorithms allow us to sort or organize data in different formats, alphabetically, numerically, ascending or descending order, highest or lowest, or vice versa. They perform operations on data structures by re-arranging the data, inserting or removing it in specific formats.
There are different sorting algorithms, and we divide them into two formats - stable and unstable sorting.
Stable sorting algorithms treat identical elements of a data structure as the same and preserve their order of appearance. An array containing elements [7, 4, 2, 4, 1, 8] will sort as [1, 2, 4, 4, 7, 8], in this case, 4 is an equal element. The first 4 appears first at index 1 appears first, followed by the 4 at index 3.
In unstable sorting, the ordering of identical elements is not there. The algorithm decides to choose which element goes first. 4 at index 3 can be written before the 4 at index 1.
Does stability in sorting matter?
Stability creates reliability in the ordering of data, and we need it during stacking.
Some of the different types of sorting algorithms include
- Heap sort
- Quick sort
- Insertion sort
- Bubble sort
- Merge sort
- Counting sort
- Radix sort
- Shell sort
- Selection sort and
- Bucket sort.
We will be looking at some of them in detail.
Quick sort
Quick sort uses a divide-and-conquer method to sorting. It takes an unsorted sequence and sorts it out in either ascending or descending order. Quick sorts pick a pivot number to base its comparison of all the other numbers. A pivot number is an element chosen from the list and used as a comparison to partition the data structure.
There are different methods to pick out a pivot number:
- To pick the last element as pivot
- To pick the first element
- Pick the middle or median number
- Pick a random element
After we choose a pivot number, we iterate through the data structure with it. If an element is higher than the pivot number, the algorithm moves that to one list. Alternatively, if it is less than the pivot number, it is moved to another list.
[0, 9, 3, 8, 2, 7, 5]
If we decide to use the last element as our pivot, our first arrangement will be
Related Articles
[0, 3, 2, 5, 9, 8, 7] - with 5 being the number to compare the others to.
Although positions have changed, the elements do not adequately sort out - 3 is still before. We will repeat the same process, choosing a pivot number from both lists (the last piece) until a proper order. We will select 2 and 7.
The next arrangement becomes this:
[0, 2, 3, 5, 7, 9, 8]
We choose 8 as pivot number from the second list:
[0, 2, 3, 5, 7, 8,9]
The time complexity of this algorithm is 0(log n)
Algorithm
STEP 1:
Start
STEP 2:
Choose a pivot number
STEP 3:
Use pivot number to compare other numbers to
STEP 4:
Create a partitioned list with this pivot number.
IF pivot number is greater than an element, send it to list one
IF pivot number is less than an element, send it to list two
STEP 5:
Repeat the process until the sequence has a correct order.
STEP 6:
Exit
Code implementation with Python
def quick_sort(arr):
n = len(arr)
if n <= 1:
return arr
else:
pivot_no = arr.pop()
# get the partitioned lists
list1 = []
list2 = []
for item in arr:
if item > pivot_no:
list1.append(item)
else:
list2.append(item)
return quick_sort(list2) + [pivot_no] + quick_sort(list1)
#to print the values
print(quick_sort([0, 9, 3, 8, 2, 7, 5]))Code implementation with Javascript
var arr = [0, 9, 3, 8, 2, 7, 5];
function swap(arr, list1, list2)
{
var temp = arr[list1];
arr[list1] = arr[list2];
arr[list2] = temp;
}
function partition(arr, l, r)
{
var pivot_no = arr[Math.floor((r + l) / 2)], //getting //a pivot number using the middle element
a = l, //left pointer
b = r; //right pointer
while (a <= b)
{
while (arr[a] < pivot_no)
{
a++;
}
while (arr[b] > pivot_no)
{
b--;
}
if (a <= b)
{
swap(arr, a, b);
a++;
b--;
}
}
return a;
}
function quick_sort(arr, l, r)
{
var index;
if (arr.length > 1)
{
index = partition(arr, l, r); //index returned from //partition
if (l < index - 1)
{
quick_sort(arr, l, index - 1);
}
if (index < r)
{
quick_sort(arr, index, r);
}
}
return arr;
}
// first call to quicksort
var sortedArray = quick_sort(arr, 0, arr.length - 1);
console.log(sortedArray);Bubble sort
A bubble sort takes an unsorted list and re-arranges them in ascending or descending order (from lowest to highest). It does this by comparing adjacent values at any given time. The element with the lower value moves to the left, while one with a higher value - to the right. This process repeats until we get to the end of the list.
When we can no longer perform swaps, we break out of the loop.
The bubble sort algorithm is considered inefficient, especially for large data structures. To swap one item, we need to make iterations through the data structure for n^2 times.
[6, 14, 20, 3, 2, 10]
For the first iteration, we'll look at 6 and 14. 6 is already on the left, and it is smaller than 14, so we leave it.
Second iteration,
Then 14 and 20. Leave it
Third iteration
20 and 3. We move 3 to the left. It becomes [6, 14, 3, 20, 2, 10]
Fourth iteration
14 and 3. We move 3 to the left of 14 it becomes [6, 3, 14, 20, 2, 10].
We continue this process, iterating and moving every adjacent value until we sort out the sequence.
Algorithm
STEP 1:
Start
STEP 2:
Compare the first two adjacent numbers
STEP 3:
Move the smaller value to the left and the higher one to the right
STEP 4:
IF smaller value is already on the left, make no swap and leave it as it is
STEP 5:
Repeat this process until the end of the data structure
STEP 6:
If you can no longer make swaps and all items are sorted out, break out of the loop
STEP 7:
Exit
Code implementation with Python
def bubble_sort(list_a):
length = len(list_a) - 1
sorted = False
while not sorted: #Repeat until sorted = True
sorted = True # to break the loop when the sequence is sorted
for i in range(0, length): # For every value in the list
if list_a[i] > list_a[i+1]: #if value in list is greater than value directly to the right of it,
sorted = False # These values are unsorted
list_a[i], list_a[i+1] = list_a[i+1], list_a[i]
return list_a # to return a list that is not sorted
print(bubble_sort([6, 14, 20, 3, 2, 10]))Code implementation with Javascript
function bubble_sort(arr)
{
let swapped = true;
do {
swapped = false;
for (let j = 0; j < arr.length; j++)
{
if (arr[j] > arr[j + 1])
{
let t = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = t;
swapped = true;
}
}
} while (swapped);
return arr;
}
var num = [6, 14, 20, 3, 2, 10];
var sortedList = bubble_sort(num);
console.log(sortedList);Selection sort
A selection sort repeatedly goes through a list to find the smallest or minimum value and sends it to a location. It usually picks the first element to compare its value to the rest. When a new feature with a lower value than the first is found, this becomes the new minimum value.
The program then moves to the left of the list and creates two sub-lists: the unsorted and sorted elements. All minimum values move to the sorted list while higher values remain in the unsorted lists.
The subsequent iterations will go through the unsorted higher value list, looking for the minimum number to send to the sorted list. It continues this process until all higher values move to the sorted list.
The selection sort algorithm has a complexity of O(n^2) with iterations calculated as (n - 1) + (n - 2) + ... + 1. It is known to perform better than the bubble sort.
Algorithm
STEP 1:
Start
STEP 2:
Pick the first element as the minimum value
STEP 3:
Iterate through the data structure to compare the first element with other elements
STEP 4:
IF there is an element with a lower minimum is discovered, make that the new minimum value
STEP 5:
Create two sub-lists and move all identified minimum values to the one list as sorted list and the move the higher values to another list as an unsorted list
STEP 6:
Move through the unsorted higher value list, and pick the minimum values
STEP 7:
Move minimum values from unsorted list to sorted list
STEP 8:
Repeat process for each iteration until the sequence is sorted
STEP 9:
Exit
Code implementation with Python
def selection_sort(num):
length = range(0, len(num)-1)
for i in length:
min_value = i #picks the first element as the minimum point
#iterate through the list to compare the first elements to other elements
for j in range(i+1, len(num)):
if num[j] < num[min_value]:
min_value = j
if min_value != i:
num[min_value], num[i] = num[i], num[min_value]
return num
print(selection_sort([6,7,8,2,6,5,3,5,8,7,6,7,8,4,7,9,0]))Code implementation with Javascript
function selection_sort(arr)
{
let n = arr.length;
for (let i = 0; i < n; i++)
{
// to get the smallest value
let min = i;
for (let j = i + 1; j < n; j++)
{
if (arr[j] < arr[min])
{
min = j;
}
}
if (min != i)
{
// iterating and creating sublists
let tmp = arr[i];
arr[i] = arr[min];
arr[min] = tmp;
}
}
return arr;
}
let arr = [12, 2, 41, 6, 14, 3];
selection_sort(arr);
document.write(arr);Insertion sort
Insertion sort is a stable sort algorithm that takes a data sequence and divides them into sorted and unsorted lists. It picks the first element by default and makes it the sorted list (with length = 1) while the rest are considered unsorted. It takes a similar approach to selection sort by dividing one list into two.
With insertion sort, the main iteration starts with the second element since the program considers the first element a sorted element. For each iteration, we compare the value of the first unsorted element to the one already sorted. If the value is higher, it moves to the right of the sorted items. If not - it goes to the left. This simple process repeats until the sequence is sorted.
The thing about insertion sort is that the algorithm doesn't need to iterate through the entire list before sorting. It just compares each element at the current iteration point with the sorted items to determine if they should be moved or not. The Insertion sort algorithm has a complexity of O(n^2) because it compares two nested lists.
[6, 3, 7, 2, 4, 9]
First iteration:
6 automatically moves to the sorted array list as the first element
Sorted array = 6
Unsorted array = [3,7,2,4,9]
Second iteration:
The algorithm compares 3 to 6. 3 is less than 6, so 3 moves to the left of 6.
Sorted array = [3, 6]
Unsorted array = [7,2,4,9]
Third iteration:
7 compared to 3 and 6. 7 is greater than 3 and 6, moving to the right.
Sorted array = [3, 6, 7]
Unsorted array = [2, 4, 9]
Fourth iteration:
2 is smaller than 3 and 6, moving to the left of elements on the sorted list.
Sorted array = [2, 3, 6, 7]
Unsorted array = [4, 9]
Fifth iteration:
4 is greater than 3 but less than 6 and 7. So 4 moves between 3 (to the right of 3) and 6 (to the left of 6).
Sorted array = [2, 3, 4, 6, 7]
Unsorted array = [9]
Sixth iteration:
We move 9 to the right of the elements.
Sorted array = [2,3,4,6,7,9]
Algorithm
STEP 1:
Start
STEP 2:
Divide the list into two and automatically move the first element of the array into the sorted list.
STEP 3:
Compare the first value of the sorted elements with the element in the sorted array.
STEP 4:
IF sorted element is greater, move the new element to the left of it.
IF sorted element is lower, move the new element to the right of it
STEP 5:
Repeat process for all elements
STEP 6:
Exit
Code implementation with Python
def insertion_sort(num):
length = range(1, len(num))
for i in length: #iterating through the values
value_to_sort = num[i]
while num[i-1] > value_to_sort and i>0:
num[i], num[i-1] = num[i-1], num[i]
i = i -1
return num
print(insertion_sort([9,8,9,8,4,6,5,2,4,7,8,9,6,8,7,6,5,4,7,8]))Code implementation with Javascript
function insertion_sort(nums)
{
let n = nums.length;
// moving the first element automatically to sorted list
for (let i = 1; i < n; i++)
{
let current = nums[i];
// The last element of our sorted subarray
let j = i - 1;
while ((j > -1) && (current < nums[j]))
{
nums[j + 1] = nums[j];
j--;
}
nums[j + 1] = current;
}
return nums;
}
let nums = [6, 3, 7, 2, 4, 9];
insertion_sort(nums);
document.write(nums);Merge sort
Merge sort is a divide and conquer algorithm usually done recursively. Recursion divides a problem into sub-problems and the sub-problem into further sub-problem, and this is how merge sort works.
Say we have the following values:
[24, 4, 12, 8, 18, 10, 2, 44]
We will divide the list into two and divide each group until it gets to each element.
We will examine the individual items, compare their values and merge them into temporary arrays while sorting them. The following process is to pair up separate arrays with their adjacent element in a sorted format.
The paired smaller arrays merge into bigger ones which are remerged into bigger ones and further remerged into bigger ones until every element fits back into one enormous sorted array.
There are two ways of implementing merge sort algorithms. We can achieve this using a bottom-up approach or a top-down approach. In the first approach, rather than solve recursively throughout, we can solve iteratively once the elements are broken down into sub-arrays. Both methods have in common that the complete list is broken into individual pieces and sorted.
Merge sort has a time complexity of 0(log n) and is considered one of the fastest sort algorithm.
Algorithm
STEP 1:
Start
STEP 2:
Divide the array into equal parts
STEP 3:
Divide each sub-array recursively until each becomes an individual element
STEP 4:
Combine pairs of the individual elements while sorting them out
STEP 5:
Merge each pair with another pair of paired-elements
STEP 6:
Keep pairing until the entire list becomes one complete sorted array.
STEP 7:
Exit.
Like all recursion, the code for a merge sort should have a base recursion function that determines how the rest of the recursion should perform.
Code implementation with Python
def merge_sort(arr, l_index, r_index):
#the base function
if l_index >= r_index:
return
mid = (l_index + r_index)//2
merge_sort(arr, l_index, mid)
merge_sort(arr, mid + 1, r_index)
merge(arr, l_index, r_index, mid)
#recursive function
def merge(arr, l_index, r_index, mid):
# this makes copies of the arrays to be merged
# The second parameter is non-inclusive, so we have to increase by 1
l_copy = arr[l_index:mid + 1]
r_copy = arr[mid+1:r_index+1]
# the initial values for variables needed to keep track of our current #position in each array
l_copy_index = 0
r_copy_index = 0
sorted_index = l_index
# Go through both copies until we run out of elements in one
while l_copy_index < len(l_copy) and r_copy_index < len(r_copy):
# If our left_copy has the smaller element, put it in the sorted
# part and then move forward in left_copy (by increasing the pointer)
if l_copy[l_copy_index] <= r_copy[r_copy_index]:
arr[sorted_index] = l_copy[l_copy_index]
l_copy_index = l_copy_index + 1
# else, move to the right
else:
arr[sorted_index] = r_copy[r_copy_index]
r_copy_index = r_copy_index + 1
# Regardless of where we got our element from
# move forward in the sorted part
sorted_index = sorted_index + 1
# when we run out of copies in either the right or left copies
# will go through the remaining elements and add them
while l_copy_index < len(l_copy):
arr[sorted_index] = l_copy[l_copy_index]
l_copy_index = l_copy_index + 1
sorted_index = sorted_index + 1
while r_copy_index < len(r_copy):
arr[sorted_index] = r_copy[r_copy_index]
r_copy_index = r_copy_index + 1
sorted_index = sorted_index + 1
arr = [33, 42, 9, 37, 8, 47, 5, 29, 49, 31, 4, 48, 16, 22, 26]
merge_sort(arr, 0, len(arr) -1)
print(arr)Code implementation with Javascript
function merge(left_copy, right_copy)
{
let arr = []
// if any of the array is empty, we break out of loop
while (left_copy.length && right_copy.length)
{
//while loop to pick the smaller elements of the left and right sub arrays
if (left_copy[0] < right_copy[0])
{
arr.push(left_copy.shift())
}
else
{
arr.push(right_copy.shift())
}
}
// Concatenating the leftover elements
// (in case we didn't go through the entire left or right array)
return [...arr, ...left_copy, ...right_copy]
}
function merge_sort(num)
{
const half = num.length / 2
// Base function case or terminating case
if (num.length < 2)
{
return num
}
const left = num.splice(0, half)
return merge(merge_sort(left), merge_sort(num))
}
num = [24, 4, 12, 8, 18, 10, 2, 44];
document.write(merge_sort(num));