Sorting Algorithms
Definition:
A sorting algorithm is an algorithm made up of a series of instructions that takes an array as input, performs specified operations on the array, sometimes called a list, and outputs a sorted array. Sorting algorithms are often taught early in computer science classes as they provide a straightforward way to introduce other key computer science topics like Big-O notation, divide-and-conquer methods, and data structures such as binary trees, and heaps.
Applications:
Sorted data is faster to search.
Easier to find maximum, minimum, duplicates and specific items
Useful to compare or find overlap between arrays.
Common sorting algorithms:
Bubble Sort:
Bubble Sort is a simple algorithm which is used to sort a given set of n elements provided in form of an array with n number of elements. Bubble Sort compares all the element one by one and sorts them based on their values. If the given array has to be sorted in ascending order, then bubble sort will start by comparing the first element of the array with the second element, if the first element is greater than the second element, it will swap both the elements, and then move on to compare the second and the third element, and so on. It is called bubble sort because with every complete iteration, the larget element in the giver arraw, 'bubbles up' to the next highest (or lowest) index.
Specifics:
Best time complexity: O(n)
Worst time complexity: O(n^2)
Space complexity: O(1)
Python Implementation:
def bubble_sort(array):
for u in range(len(array)):
for i in range(len(array)-1):
if array[i] > array[i+1]:
array[i+1], array[i] = array[i], array[i+1]
return array
Insertion sort:
An insertion sort is less complex and efficient than a merge sort, but more efficient than a bubble sort.
An insertion sort compares values in turn, starting with the second value in the list. If this value is greater than the value to the left of it, no changes are made.
Otherwise this value is repeatedly moved left until it meets a value that is less than it. The sort process then starts again with the next value. This continues until the end of the list is reached.
Specifics:
Best time complexity: O(n) when the given array is already sorted
Worst time complexity: O(n^2) when the given array is reversely sorted
Space complexity: O(1)
Python Implementation:
def insertion_sort(array):
for i in range(1, len(array)):
key_item = array[i]
j = i - 1
while j >= 0 and array[j] > key_item:
array[j + 1] = array[j]
j -= 1
array[j + 1] = key_item
return array
Merge sort:
Another example of a computer sorting algorithm is merge sort. This is a more complex algorithm than bubble sort, but can be more efficient.
The merge sort algorithm repeatedly divides a list into two until all the elements are separated individually. Pairs of elements are then compared, placed into order and combined. The process is then repeated until the list is recompiled as a whole.
Specifics:
Best time complexity: O(N logN)
Worst time complexity: O(N logN))
Space complexity: O(N)
def merge_sort(arr):
if len(arr) > 1:
a = len(arr)//2
l = arr[:a]
r = arr[a:]
mergeSort(l)
mergeSort(r)
b = c = d = 0
while b < len(l) and c < len(r):
if l[b] < r[c]:
arr[d] = l[b]
b += 1
else:
arr[d] = r[c]
c += 1
d += 1
while b < len(l):
arr[d] = l[b]
b += 1
d += 1
while c < len(r):
arr[d] = r[c]
c += 1
d += 1
arr = [3, 2, 7, 8]
merge_sort(arr)
print(arr)
Quick sort:
Quick sort is a highly efficient sorting algorithm and is based on partitioning of array of data into smaller arrays. A large array is partitioned into two arrays one of which holds values smaller than the specified value, say pivot, based on which the partition is made and another array holds values greater than the pivot value.
Quicksort partitions an array and then calls itself recursively twice to sort the two resulting subarrays. This algorithm is quite efficient for large-sized data sets as its average and worst-case complexity are O(n2), respectively.
Specifics:
Best time complexity: O(n*log (n))
Worst time complexity: O(n^2)
Space complexity: O(N)
Python Implementation:
def partition(arr,low,high):
i = (low-1)
pivot = arr[high]
for j in range(low , high):
if arr[j] <= pivot:
i = i+1
arr[i],arr[j] = arr[j],arr[i]
arr[i+1],arr[high] = arr[high],arr[i+1]
return (i+1)
def quick_sort(arr,low,high):
if low < high:
pi = partition(arr,low,high)
quick_sort(arr, low, pi-1)
quick_sort(arr, pi+1, high)
arr = [2,5,3,8,6,5,4,7]
n = len(arr)
quick_sort(arr,0,n-1)
print("Sorted array is:")
for i in range(n):
print(arr[i],end=" ")