Sorts Algorithms

Introduction to Sorting Algorithms

A sorting algorithm is any series of steps that takes an unsorted data input and returns data organized in a specific pattern. For computer-related operations, this involves taking an input of a list or array and returning an organized list or array. Sorting primarily helps optimize data usability, as some data operations are more efficient when operating on a sorted list. This is apparent in searching, selecting, handling duplication, and analyzing data distribution. Given the usefulness of sorted data, sorting algorithms are a well-studied part of computer science. Let’s review different attributes sorting algorithms can have and present and analyze select algorithms. All algorithms will be presented in Python.

https://www.crazygames.com/game/sort-it-uei

Attributes of Sorting Algorithms

As the number of entries N plugged into a sorting algorithm grows, so do the resources it utilizes. The primary resource usages for analyzing sorting algorithms are time and space complexity. As per the name, time complexity describes how long a sorting algorithm will take based on the magnitude of the number of operations performed. Similarly, space complexity describes how much space an algorithm needs in terms of N (the number of entries).

Introduction to Time Complexity of Sorting Algorithms

Evaluating sorting algorithms for time does not involve evaluating a specific runtime, as the number of entries and the resources available are unknown variables. Instead, it consists of quantifying the time the algorithms will take in terms of the number of entries. Algorithms are quantified in three different aspects: lower bound, or big Omega notation (denoted by an Omega); tightest bound, or big Theta notation (represented by a Theta); and upper bound, or big O notation (defined by O, meaning “order of”). These equate to a minimum, average, and maximum runtime. For most use cases, O, or maximum runtime, is the metric of time complexity considered. Thus, this paper will primarily consider the maximum runtime of sorting algorithms.

Elaboration on Time Complexity of Sorting Algorithms

The time complexity of an algorithm is quantified by how the time grows as the number of entries grows. There are several categories of time complexity in which algorithms can fit: constant time O(1), logarithmic time O(\log{n}), linear time O(n), quadratic time O(n²), and exponential time O(2^n). As these describe how an algorithm’s time increases as the number of entries increases, constant time means that the algorithm’s time is not dependent on the number of entries. This makes it the optimal runtime of a sorting algorithm, although it generally only appears as the Omega(n) runtime for pre-sorted data. However, as a general rule, the shorter the time, the better, although sometimes shorter time comes at the cost of higher space complexity.

Space Complexity of Sorting Algorithms

Similar to time complexity, the space complexity of a sorting algorithm is quantified by how much memory (that is, RAM or Random Access Memory) an algorithm takes to run in terms of the number of entries input. This, too, is highly dependent on the algorithm. Although it’s an important aspect to consider, generally, time complexity is weighed more heavily when considering algorithms.

Stable Sorting

A sorting algorithm is considered “stable” if, upon encountering equivalent values, it maintains the original order of these values when sorting. A sorting algorithm is thus considered “unstable” if it does not preserve the original order of equivalent values.

Evaluating Specific Sorting Algorithms

Given the attributes above of sorting algorithms, the following will evaluate common sorting algorithms for their time and space complexity.

Insertion Sort

# function - sorts list values from least to greatest
def sort_values_ascending(inputList):
i = 0
while i < len(inputList):
ii = i
smallValue = inputList[ii] + 1
smallValueIndex = 0
while ii < len(inputList):
if inputList[ii] < smallValue:
smallValue = inputList[ii]
smallValueIndex = ii
else:
ii += 1
inputList[smallValueIndex] = inputList[i]
inputList[i] = smallValue
i += 1
return inputList

This function sorts the input list from least to greatest and returns it. If inputList = [3, 2, 1, 4, 2], the function will return [1, 2, 2, 3, 4]. It accomplishes this by iterating through the sequence starting at the relative front until it finds the smallest number, then swapping the values of the smallest value and the value at the relative front of the list for each value, incrementing the location of the relative front by one for each full list read. This may be a very intuitive sort, but when analyzed for time complexity, it comes up somewhat short at O(n²) time complexity. The space complexity of insertion sort is only the array itself, as shown in the example above, and as mentioned by Coding Ninjas, as it updates the original array itself while iterating. However, its inability to scale well with the number of entries input makes it an unrealistic pick when dealing with an arbitrarily large number.

Bubble Sort

def bubble_sort(alist):
for i in range(len(alist) - 1, 0, -1):
no_swap = True
for j in range(0, i):
if alist[j + 1] < alist[j]:
alist[j], alist[j + 1] = alist[j + 1], alist[j]
no_swap = False
if no_swap:
return
alist = input('Enter the list of numbers: ').split()
alist = [int(x) for x in alist]
bubble_sort(alist)
print('Sorted list: ', end='')
print(alist)

As written above by Manish Bhojasia, bubble sort has a time complexity of O(n^n), which is worse than insertion sort. However, its best time complexity is linear, and the time complexity scales directly with how unsorted a list is, making it a highly situational sorting algorithm. The bubble sort sorting algorithm only has a space complexity of O(1), or a constant space complexity, as it swaps the values of the original dataset.

Merge Sort

# Python program for implementation of MergeSort
# Merges two subarrays of arr[].
# First subarray is arr[l..m]
# Second subarray is arr[m+1..r]
def merge(arr, l, m, r):
n1 = m - l + 1
n2 = r - m
# create temp arrays
L = [0] * (n1)
R = [0] * (n2)
# Copy data to temp arrays L[] and R[]
for i in range(0, n1):
L[i] = arr[l + i]
for j in range(0, n2):
R[j] = arr[m + 1 + j]
# Merge the temp arrays back into arr[l..r]
i = 0 # Initial index of first subarray
j = 0 # Initial index of second subarray
k = l # Initial index of merged subarray
while i < n1 and j < n2:
if L[i] <= R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
# Copy the remaining elements of L[], if there
# are any
while i < n1:
arr[k] = L[i]
i += 1
k += 1
# Copy the remaining elements of R[], if there
# are any
while j < n2:
arr[k] = R[j]
j += 1
k += 1
# l is for left index and r is right index of the
# sub-array of arr to be sorted
def mergeSort(arr, l, r):
if l < r:
# Same as (l+r)//2, but avoids overflow for
# large l and h
m = l+(r-l)//2
# Sort first and second halves
mergeSort(arr, l, m)
mergeSort(arr, m+1, r)
merge(arr, l, m, r)
# Driver code to test above
arr = [12, 11, 13, 5, 6, 7]
n = len(arr)
print("Given array is")
for i in range(n):
print("%d" % arr[i],end=" ")
mergeSort(arr, 0, n-1)
print("\n\nSorted array is")
for i in range(n):
print("%d" % arr[i],end=" ")
# This code is contributed by Mohit Kumra

As written here by Mohit Kumra, Merge sort is one of the more versatile sorting algorithms. It takes a divide-and-conquer approach to sort, dividing the dataset into halves until it can no longer do so. It has a time complexity of O(n log n), which, as mentioned by Coding Ninjas, is equivalent to the best, worst, and average case scenario. It has a space complexity of O(n), which is minimal when considering the relatively.

Quick Sort

# Python program for implementation of Quicksort Sort
# This implementation utilizes pivot as the last element in the nums list
# It has a pointer to keep track of the elements smaller than the pivot
# At the very end of partition() function, the pointer is swapped with the pivot
# to come up with a "sorted" nums relative to the pivot
# Function to find the partition position
def partition(array, low, high):
# choose the rightmost element as pivot
pivot = array[high]
# pointer for greater element
i = low - 1
# traverse through all elements
# compare each element with pivot
for j in range(low, high):
if array[j] <= pivot:
# If element smaller than pivot is found
# swap it with the greater element pointed by i
i = i + 1
# Swapping element at i with element at j
(array[i], array[j]) = (array[j], array[i])
# Swap the pivot element with the greater element specified by i
(array[i + 1], array[high]) = (array[high], array[i + 1])
# Return the position from where partition is done
return i + 1
# function to perform quicksort
def quickSort(array, low, high):
if low < high:
# Find pivot element such that
# element smaller than pivot are on the left
# element greater than pivot are on the right
pi = partition(array, low, high)
# Recursive call on the left of pivot
quickSort(array, low, pi - 1)
# Recursive call on the right of pivot
quickSort(array, pi + 1, high)
data = [1, 7, 4, 1, 10, 9, -2]
print("Unsorted Array")
print(data)
size = len(data)
quickSort(data, 0, size - 1)
print('Sorted Array in Ascending Order:')
print(data)

As presented here by Geeks for Geeks, quick sort is another search algorithm with the divide and conquer method. It has a time complexity of O(log n) and a space complexity of O(n), making it similar to the Merge sort, with different use cases.

Which Algorithm?

A sorting algorithm only becomes essential when dealing with large amounts of data. As such, the built-in function should suffice for trivial purposes. However, when dealing with large amounts of data, one should consider how significant the time and space complexity is to them, based on their use case and resources available, and pick an algorithm appropriate to their use case.

Common Errors

A common error when making a sorting algorithm could be not checking whether or not it’s already been made, as sorting algorithms are a relatively well-studied topic. When programming a sorting algorithm, a possible error is not correctly incrementing one’s loop, thus creating an infinite loop. When using a sorting algorithm, an easy mistake would be picking one that is not well suited to one’s use case, i.e., just using the default sorting algorithm when another one is more appropriate. However, unless dealing with large amounts of data, the difference can be small enough that it doesn’t matter much — it entirely depends on the use case.

Takeaway

Sorting algorithms can be beneficial for making data more usable. Sorted data improves search efficiency, data selection, duplication handling, and data distribution analysis. This is especially relevant today, given the massive amounts of data produced. Many searching algorithms are available, and picking one that fits the job is essential when dealing with large amounts of data.