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.

'''
PYTHON
'''
def selection_sort(arr):
    for i in range(len(arr)):
        '''Initialize a variable min_idx to location 0.
        This points to our minimum value.
        '''
        min_idx = 0

        '''Traverse the array to find the
        minimum element in the array.
        '''
        for j in range(min_idx + 1, len(arr)):
            if arr[j] < arr[min_idx]:
                # swap
                arr[j], arr[min_idx] = arr[min_idx], arr[j]
                '''Increment `min_idx` to point to
                the next element.'''
                min_idx += 1

def main():
    arr = [6, 5, 4, 9, 8, 7, 3, 2, 1, 0]

    print('before: ',arr)
    selection_sort(arr)

    print('after: ', arr)

# call main
main()