SORTING ALGORITHMS

INTRO

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 monotonic order. 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.

CLASSIFICATION

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.

COMPARISON OF ALGORITHMS

1. SELECTION SORT

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

• Initialize a variable min_idx to location 0. This points to our minimum value.
• Traverse the array to find the minimum element in the array.
• If any element smaller than the value pointed to by min_idx is found, swap both values.
• Increment min_idx to point to the next element.
• Repeat until the array is sorted.

COMPLEXITY ANALYSIS

---

2. BUBLE SORT

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.

ALGORITHM

• Define a function called bubble_sort that takes an integer array arr and an integer n as its parameters.
• Initialize a variable called flag with the value of n-1.
• Start an infinite loop.
• Within the infinite loop, create a for loop that starts at index 0 and ends at n-1.
• Within the for loop, define two variables called current and nex which are assigned the values of arr[i] and arr[i+1] respectively.
• Compare current and nex: if current is greater than nex, swap them by assigning arr[i] the value of nex and arr[i+1] the value of current. Also, increment the value of flag by 1. If current is not greater than nex, decrement the value of flag by 1.
• At the end of the for loop, check if the value of flag is equal to 0. If it is, break out of the infinite loop.
• If the value of flag is not equal to 0, re-initialize the value of flag to n-1.
• The function doesn't return anything

C IMPLEMENTATION

#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);  
}

PYTHON IMPLEMENTATION

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)

COMPLEXITY ANALYSIS

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.

---

3. INSERTION SORT

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.

ALGORITHM

• Define a function called insertion_sort that takes an array arr as 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 j is 0.
• Within the while loop, compare the current element at index j with the element at index j-1.
• If the current element is less than the element at index j-1, swap them and decrement the value of j by 1.
• If the current element is not less than the element at index j-1, break out of the while loop.

PYTHON IMPLEMENTATION

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)

C IMPLEMENTATION

#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;
}

COMPLEXITY ANALYSIS

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.

INSERTION SORT FOR DOUBLY LINKED LIST

PYTHON IMPLEMENTATION

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()