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.
#include <stdio.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void Sort(int arr[], int n) {
int min_val, min_index;
for (int i = 0; i < n - 1; i++) {
min_val = arr[i + 1];
min_index = i + 1;
for (int j = i + 1; j < n; j++) {
if (arr[j] < min_val) {
min_val = arr[j];
min_index = j;
}
}
if (min_val < arr[i]) {
swap(&arr[i], &arr[min_index]);
}
}
}
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;
}
def SelectionSort(arr):
n = len(arr)
for i in range(n - 1):
min_val = arr[i + 1]
min_index = i + 1
for j in range(i + 1, n):
if arr[j] < min_val:
min_val = arr[j]
min_index = j
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)
- 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).
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.
-
Create a new, empty sorted list.
-
Traverse the given doubly linked list, for each node in the list:
- Create a new node with the same data as the current node.
- Initialize pointers for the current node in the sorted list and the previous node.
- Iterate through the sorted list, comparing the data of the new node to the data of each node in the sorted list.
- If the data of the new node is less than or equal to the data of the current node in the sorted list, insert the new node before the current node.
- If the current node is the first node in the sorted list, set the new node as the head of the sorted list.
- Otherwise, set the previous node's next pointer to the new node, set the new node's prev pointer to the previous node, and set the current node's prev pointer to the new node.
-
If the end of the sorted list is reached, insert the new node at the end.
-
Return the head of the sorted list.
#include <stdio.h>
#include <stdlib.h>
// Define node of a linked list
typedef struct Node
{
struct Node *prev;
struct Node *next;
int data;
}Node;
// add a node at the end of a linked list
void add_node_end(Node **head, int data)
{
Node *ptr = *head;
// create a new node
Node *new_node = malloc(sizeof(Node));
if (!new_node)
{
printf("No memory to allocate");
}
new_node -> prev = NULL;
new_node -> next = NULL;
new_node -> data = data;
// empty list
if (!ptr)
{
*head = new_node;
return;
}
// traverse list
while (ptr -> next)
{
ptr = ptr -> next;
}
// Insert
ptr -> next = new_node;
new_node -> prev = ptr;
}
void print_list(Node *head)
{
Node *ptr = head;
while (ptr)
{
printf("%d ", ptr -> data);
ptr = ptr -> next;
}
}
Node *insertion_sort(Node *head)
{
// create a new sorted list
Node *head2 = NULL;
// Traverse the given linked list
while (head)
{
Node *ptr = head2;
// for each node of the list create a new node
Node *new_node = malloc(sizeof(Node));
if (!new_node)
{
printf("No memory to allocate");
return (NULL);
}
new_node -> prev = NULL;
new_node -> next = NULL;
new_node -> data = head -> data;
// if sorted list is empty
if (!head2)
{
head2 = new_node;
head = head -> next;
continue;
}
//loop through sorted list
Node *prev_node = NULL;
while (ptr)
{
if (new_node -> data <= ptr -> data)
{
// special case for first node
if (ptr -> prev == NULL)
{
new_node -> next = ptr;
new_node -> prev = NULL;
ptr -> prev = new_node;
head2 = new_node;
break;
}
else
{
Node *before = ptr -> prev;
before -> next = new_node;
new_node -> next = ptr;
new_node -> prev = before;
ptr -> prev = new_node;
break;
}
}
prev_node = ptr;
ptr = ptr -> next;
}
if (!ptr)
{
// insert node at the end
prev_node -> next = new_node;
new_node -> prev = prev_node;
new_node -> next = NULL;
}
head = head -> next;
}
return (head2);
}
// driver code
int main(void)
{
// stert with empty list
Node *head = NULL;
add_node_end(&head, 5);
add_node_end(&head, 20);
add_node_end(&head, 4);
add_node_end(&head, 3);
add_node_end(&head, 30);
// print the unsorted list
print_list(head);
// sort list
Node *head2 = insertion_sort(head);
printf("\n");
// print sorted list
print_list(head2);
return (0);
}
class Node:
def __init__(self, data):
self.prev = None
self.data = data
self.next = None
class linked_list:
def __init__(self):
self.head = None
def add_node_end(self, data):
'''add node at the end of
the linked list'''
# create node
new_node = Node(data)
if not self.head:
self.head = new_node
else:
# traverse the list
temp = self.head
while temp.next:
temp = temp.next
# Attach
temp.next = new_node
new_node.prev = temp
new_node.next = None
def print_list(self):
temp = self.head
while temp:
print(temp.data, end = ' ')
temp = temp.next
print()
def insertion_sort(self):
#create new sorted list
head2 = None
#Traverse the given linked list
head = self.head
while head != None:
ptr = head2
#For each node of the list, create a new node
new_node = Node(head.data)
# if new list is empty
if head2 == None:
head2 = new_node
head = head.next
continue
prev_node = None
while ptr:
# if value of unsorted list is smaller
if new_node.data <= ptr.data:
# special case for first node
if ptr.prev == None:
new_node.next = ptr
new_node.prev = None
ptr.prev = new_node
head2 = new_node
break
else:
before = ptr.prev
before.next = new_node
new_node.next = ptr
new_node.prev = before
ptr.prev = new_node
break
prev_node = ptr
ptr = ptr.next
else:
# Insert at the end
prev_node.next = new_node
new_node.prev = prev_node
new_node.next = None
head = head.next
self.head = head2
# Create a linked list
list1 = linked_list()
# Add elements
list1.add_node_end(12)
list1.add_node_end(11)
list1.add_node_end(13)
list1.add_node_end(5)
list1.add_node_end(6)
# print unsorted list
list1.print_list()
#sort the list
list1.insertion_sort()
#print the sorted list
list1.print_list()