Sorting Algorithms Types: Mathematics

Concepts of basic sorting algorithms:

There are numerous sorting algorithms, each with its unique approach and characteristics. Here is a list of some common sorting algorithms:

1. Bubble Sort:

A simple comparison-based algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.

• Mathematical representation:

for i = 0 to n-1:
    for j = 0 to n-i-1:
        if arr[j] > arr[j+1]:
            swap(arr[j], arr[j+1])

⤏ Here, 'arr' is the array to be sorted, 'n' is the number of elements in the array, and swap(a, b) is a function that swaps the values of 'a' and 'b'.

2. Selection Sort:

Another simple comparison-based algorithm that divides the input into a sorted and an unsorted region. It repeatedly selects the smallest (or largest) element from the unsorted region and swaps it with the first unsorted element.

• Mathematical representation:

for i = 0 to n-1:
    min_index = i
    for j = i+1 to n:
        if arr[j] < arr[min_index]:
            min_index = j
    swap(arr[i], arr[min_index])

3. Insertion Sort:

Builds the sorted array one item at a time by repeatedly taking elements from the unsorted part and inserting them into their correct position in the sorted part.

• Mathematical representation:

for i = 1 to n-1:
    key = arr[i]
    j = i-1
    while j >= 0 and arr[j] > key:
        arr[j+1] = arr[j]
        j = j-1
    arr[j+1] = key

4. Merge Sort:

A divide-and-conquer algorithm that recursively divides the input into two halves, sorts them, and then merges the sorted halves to produce the final sorted array.

• Mathematical representation:

for i = 1 to n-1:
    key = arr[i]
    j = i-1
    while j >= 0 and arr[j] > key:
        arr[j+1] = arr[j]
        j = j-1
    arr[j+1] = key

⤏ Here, merge(arr, l, mid, r) is a function that merges two sorted subarrays into one sorted array.

5. Quick Sort:

Another divide-and-conquer algorithm that selects a "pivot" element and partitions the other elements into two sub-arrays according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.

• Mathematical representation:

quick_sort(arr, low, high):
    if low < high:
        pivot = partition(arr, low, high)
        quick_sort(arr, low, pivot-1)
        quick_sort(arr, pivot+1, high)

⤏ The partition(arr, low, high) function selects a pivot and partitions the array into elements less than and greater than the pivot.

6. Heap Sort:

Uses a binary heap data structure to build a partially ordered binary tree and then repeatedly extracts the maximum element from the heap, placing it at the end of the sorted array.

• Mathematical representation:

heap_sort(arr):
    build_max_heap(arr)
    for i = n-1 to 1:
        swap(arr[0], arr[i])
        max_heapify(arr, 0, i)

⤏ build_max_heap(arr) builds a max heap from the input array, and max_heapify(arr, i, size) maintains the heap property.

7. Counting Sort:

A non-comparison-based algorithm that works well for integers with a limited range. It counts the occurrences of each element and uses this information to reconstruct a sorted sequence.

• Mathematical representation:

counting_sort(arr, k):
    count = array of size k+1 initialized to 0
    for i = 0 to n-1:
        count[arr[i]]++
    for i = 1 to k:
        count[i] += count[i-1]
    output = array of size n
    for i = n-1 to 0:
        output[count[arr[i]]-1] = arr[i]
        count[arr[i]]--
    ```
- Here, `k` is the maximum value in the array.

8. Radix Sort:

A non-comparison-based algorithm that sorts integers by processing individual digits. It can be implemented using a stable sorting algorithm as a subroutine.

• Mathematical representation:

radix_sort(arr, exp):
    count_sort(arr, exp):
        ... (similar to counting sort, but sorting based on a specific digit)
    max_element = get_max(arr)
    for exp = 1 to max_element:
        count_sort(arr, exp)

⤏ get_max(arr) returns the maximum element in the array.

9. Bucket Sort:

Distributes the elements into a number of buckets and then separately sorts each bucket, often using another sorting algorithm. The sorted buckets are concatenated to obtain the final sorted array.

• Mathematical representation:

bucket_sort(arr, num_buckets):
    buckets = array of num_buckets empty lists
    for i = 0 to n-1:
        index = floor(num_buckets * arr[i] / (max_element + 1))
        append arr[i] to buckets[index]
    for i = 0 to num_buckets-1:
        sort(buckets[i])
    concatenate buckets[0] to buckets[num_buckets-1]

10. Shell Sort:

An extension of Insertion Sort that breaks the input into smaller sub-arrays and sorts them independently using the Insertion Sort algorithm. The sub-array size decreases over multiple passes.

• Mathematical representation:

shell_sort(arr):
    n = length of arr
    gap = n/2
    while gap > 0:
        for i = gap to n-1:
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap = gap / 2

11. Comb Sort:

An improvement over Bubble Sort that compares and swaps elements with a gap, gradually reducing the gap size until it becomes 1.

• Mathematical representation:

comb_sort(arr):
    n = length of arr
    gap = n
    shrink_factor = 1.3
    swapped = True
    while gap > 1 or swapped:
        gap = max(1, int(gap / shrink_factor))
        swapped = False
        for i = 0 to n-gap-1:
            if arr[i] > arr[i + gap]:
                swap(arr[i], arr[i + gap])
                swapped = True

Remember: These are just a few examples, and there are many more sorting algorithms, each with its strengths and weaknesses. The choice of the sorting algorithm depends on factors such as the size of the data, the distribution of values, and the specific requirements of the problem.