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.