SORTING ALGORITHMS
A sorting algorithm is one that puts elements in a list into an order.
The most frequently used orders are:
- Numerical order
- Lexicographical order.
These can either be ascending or descending.
Efficient sorting is important for optimizing the efficiency of other algorithms such as search and merge algorithms that require data to be in sorted lists.
Sorting is also useful for canonicalizing data and for producing human-readable output.
In Computer Science, canonicalization is the process of converting data that has more than one possible representation into a standard/ normal form
Formally , the output of any sorting algorithm must satisfy two conditions.
- The output must be in
monotonicorder. i.e. each element is no smaller/ larger than the previous element, according to the required order. - The output is a permutation of the input. i.e. it is a reordering yet retaining all of the original elements.
For optimum efficiency, the input data should be stored in a data structure that allows random access rather than one that allows only sequential access.
Sorting algorithms can be classified by:
-
Computational complexity. This classifies an algorithm based on its usage of resources. This gives 3 behaviors in terms of the size of the list
- Best
- Worst
- Average case
-
Memory usage
-
Recursion
Merge sort is both recursive and non recursive. -
Stability
stable algorithms maintain the relative order of records with equal keys. -
Whether or not they are a comparison sort.
-
Serial or Parallel
-
Adaptability. This determines whether the presortedness of input affects its runing time.
-
Online
online algorithms can sort a constant stream of input.
This is a simple and efficient sorting algorithm that works by repeatedly selecting the smallest or largest element from the unsorted portion of the list and moving it to the sorted portion of the list.
ALGORITHM
- It uses two nested for loops to iterate through the array. The outer loop starts from the first element of the array and runs until the second last element. The inner loop starts from the element next to the current element of the outer loop and runs until the end of the array.
- In the inner loop, the function compares the current element of the inner loop with the minimum value and index stored in the variables
min_valandmin_index. If the current element is smaller than the stored minimum value, the function updates the minimum value and index with the current element's value and index. - After the inner loop completes, if the stored minimum value is smaller than the current element of the outer loop, the function swaps the current element and the minimum element.
def SelectionSort(arr):
# Array length
n = len(arr)
# Iterate up to the second last element
for i in range(n - 1):
# Compare all values after the current
# Element and store the smallest one
min_val = arr[i + 1]
min_index = i + 1
for j in range(i + 1, n):
if arr[j] < min_val:
# If a min element is encountered
# Update the min_val and Index
min_val = arr[j]
min_index = j
# if we found a smaller element
# than the current one, we swap
if min_val < arr[i]:
arr[i], arr[min_index] = arr[min_index], arr[i]
return arr
if __name__ == "__main__":
arr = [64, 25, 12, 22, 11]
print("Before: ", arr)
arr = SelectionSort(arr)
print("After: ", arr)#include <stdio.h>
/*Define a function to swap two integers by reference.*/
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
/* Define a function to sort an array of integers using selection sort.*/
void Sort(int arr[], int n) {
int min_val, min_index;
/*Iterate over each element in the array.*/
for (int i = 0; i < n - 1; i++) {
/*Assume that the next element is the minimum value.*/
min_val = arr[i + 1];
min_index = i + 1;
/*Find the minimum value and its index in the remaining part
of the array.*/
for (int j = i + 1; j < n; j++) {
if (arr[j] < min_val) {
min_val = arr[j];
min_index = j;
}
}
/*If the minimum value is less than the current element, swap
the two elements.*/
if (min_val < arr[i]) {
swap(&arr[i], &arr[min_index]);
}
}
}
/* Driver Code */
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Before: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
Sort(arr, n);
printf("After: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}- The above selection sort algorithm has a time complexity of O(n^2) where n is the number of elements in the array. This is because for each element in the array, the algorithm needs to iterate through the remaining n-1 elements to find the minimum value. The outer loop runs n times and the inner loop runs n-1 times for each iteration of the outer loop. Thus the overall time complexity is O(n * (n-1)) which can be simplified as O(n^2).
- In terms of space complexity, the algorithm only uses a constant amount of extra space for variables such as
min_valandmin_index, making the space complexity O(1). - The algorithm is stable. This is because it preserves the relative order of elements with equal values. In other words, if two elements have the same value, the algorithm will maintain their original order and not swap them. This is because the algorithm compares and swaps elements based on their values and not their positions in the array.
Bubble sort is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order.
The pass trough the list is repeated until no swaps are needed, which indicates the list is sorted.
It has a time complexity of O(n^2) in the worst and average cases making it inefficient for large data sets.
However, it is simple to understand and implement.
- Define a function called
bubble_sortthat takes an integer arrayarrand an integernas its parameters. - Initialize a variable called
flagwith the value ofn-1. - Start an infinite loop.
- Within the infinite loop, create a for loop that starts at index
0and ends atn-1. - Within the for loop, define two variables called
currentandnexwhich are assigned the values ofarr[i]andarr[i+1]respectively. - Compare
currentandnex: ifcurrentis greater thannex, swap them by assigningarr[i]the value ofnexandarr[i+1]the value of current. Also, increment the value offlagby 1. Ifcurrentis not greater thannex, decrement the value offlagby 1. - At the end of the for loop, check if the value of
flagis equal to 0. If it is, break out of the infinite loop. - If the value of
flagis not equal to 0, re-initialize the value of flag to n-1. - The function doesn't return anything
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
void bubble_sort(int arr[], int n) {
int flag = n - 1;
while (true) {
for (int i = 0; i < n - 1; i++) {
int current = arr[i];
int nex = arr[i + 1];
if (current > nex) {
arr[i] = nex;
arr[i + 1] = current;
flag += 1;
} else {
flag -= 1;
}
}
if (!flag) {
break;
}
flag = n - 1;
}
}
int main(void)
{
int i;
int array[] = {1,2,3,10,4,5,6};
/*array length*/
int n = sizeof(array) / sizeof(array[0]);
/* print input array */
for(i = 0; i < n; i++)
{
printf("%d ", array[i]);
}
printf("\n");
bubble_sort(array, n);
/* print output array */
for(i = 0; i < n; i++)
{
printf("%d ", array[i]);
}
return (0);
}def bubble_sort(arr):
# Array length
n = len(arr)
# checks if array is sorted
flag = n - 1
# Outer loop
while True:
# Inner loop
for i in range(n - 1):
current = arr[i]
nex = arr[i + 1]
if current > nex:
#swap
arr[i], arr[i + 1] = arr[i + 1], arr[i]
flag += 1
# No swap
else:
flag -= 1
# list is sorted
if not flag:
break
# List not yet sorted
flag = n - 1
# Driver code to test above
if __name__ == "__main__":
arr = [5, 1, 4, 55, 2, 8]
print('Before: ', arr)
bubble_sort(arr)
print('After: ', arr)Worst and Average Case Time Complexity: O(N2). The worst case occurs when an array is reverse sorted.
Best Case Time Complexity: O(N). The best case occurs when an array is already sorted.
Auxiliary Space: O(1)
The bubble sort algorithm is stable.
It is a simple sorting algorithm that builds the final sorted list one item at a time.
It iterates through the list, and for each element, it compares it with the elements on its left and finds the correct position of that element.
It is efficient for small data sets and is also useful when the input array is almost sorted.
it has a time complexity of O(n^2) in the worst and average case.
- Define a function called
insertion_sortthat takes an arrayarras its parameter. - Assign the length of the array to a variable
n. - Create a for loop that starts at index 1 and ends at
n-1. - Within the for loop, assign the value of the loop index variable to a variable
j. - Create a while loop that continues until
jis 0. - Within the while loop, compare the current element at index
jwith the element at indexj-1. - If the current element is less than the element at index
j-1, swap them and decrement the value ofjby 1. - If the current element is not less than the element at index
j-1, break out of the while loop.
def insertion_sort(arr):
n = len(arr)
for k in range(1, n):
j = k
while j:
if arr[j] < arr[j - 1]:
# swap
arr[j], arr[j - 1] = arr[j - 1], arr[j]
j -= 1
else:
break
if __name__ == '__main__':
arr = [12, 11, 13, 5, 6]
print('Before: ', arr)
insertion_sort(arr)
print('After: ', arr)#include <stdio.h>
#include <stdlib.h>
void insertion_sort(int arr[], int n) {
for (int k = 1; k < n; k++) {
int j = k;
while (j) {
if (arr[j] < arr[j - 1]) {
// swap
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
j -= 1;
} else {
break;
}
}
}
}
int main(void) {
int arr[] = { 12, 11, 13, 5, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("Before: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
insertion_sort(arr, n);
printf("After: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}Time Complexity: O(N^2) Auxiliary Space: O(1)
BOUNDARY CASES:
Insertion sort takes maximum time to sort if elements are sorted in reverse order. And it takes minimum time (Order of n) when elements are already sorted.
Insertion sort is a stable sorting algorithm.
The code below is an implementation of an in-place insertion sort algorithm for a doubly linked list. The function takes in a pointer to the head of the linked list and sorts the elements of the list in ascending order. The function starts by checking if the list is empty or has only one element, in which case it exits with an error message. Then, it iterates through the list, comparing the current node's data with the data of the previous node, and swapping them if the current node's data is smaller. If the previous node is the first node in the list, the function updates the head pointer accordingly. The function continues to iterate through the list and sort the elements until all elements are in the correct order.
// Define node of a linked list
typedef struct Node
{
struct Node *prev;
struct Node *next;
int data;
}Node;
/* Insertion sort function in place */
void insertion(Node **head)
{
// empty list
if (*head == NULL){
printf("Empty list");
exit(1);
}
Node *h = *head;
// list has one element
if (h -> next == NULL)
{
printf("Can't sort one element");
exit(1);
}
while (h)
{
Node *current = h;
Node *previous = current -> prev;
Node *next = current -> next;
// first node
if (!previous)
{
h = h -> next;
continue;
}
while (previous && current -> data <= previous -> data)
{
// special case swap for first node
if (!(previous -> prev))
{
current -> next = previous;
current -> prev = NULL;
previous -> prev = current;
previous -> next = next;
next -> prev = previous;
*head = current;
break;
}
else{
previous -> prev -> next = current;
current -> prev = previous -> prev;
previous -> next = next;
previous -> prev = current;
current -> next = previous;
if (next)
next -> prev = previous;
// update
next = previous;
previous = current -> prev;
}
}
h = h -> next;
}
}def insertion_sort(head):
# empty list
if not head:
print("Empty list")
exit(1)
# list has one element
if head.next is None:
print("Can't sort one element")
exit(1)
while head:
current = head
previous = current.prev
next_node = current.next
# first node
if previous is None:
head = head.next
continue
while previous and current.data <= previous.data:
# special case swap for first node
if previous.prev is None:
current.next = previous
current.prev = None
previous.prev = current
previous.next = next_node
next_node.prev = previous
head = current
break
else:
previous.prev.next = current
current.prev = previous.prev
previous.next = next_node
previous.prev = current
current.next = previous
if next_node:
next_node.prev = previous
# update
next_node = previous
previous = current.prev
head = head.next