Sorting and Efficiency

In any programming language, you will see numerous lists that contain an array of random or unsorted numbers. Sorting algorithms are methods or functions used  to sort these lists into either ascending or descending order.There are many kinds of sorting algorithms, each with their own pros and cons when it comes to efficiency which refers to how many steps it takes to sort a list. The different types of sorts include selection sort, insertion sort and bubble sort.

Selection sort is a not so efficient algorithm that has a complexity of O(n^2) as its best, or in other words, the total number of moves it takes to sort the list is equal to the number of items in the list squared. The algorithm works by keeping track of the left most index, then going through the whole list to find any value that is less than that index. The pointer for the index to be compared then moves one space over and the process repeats.

Insertion sort is much more efficient than Selection sort since the best case complexity of this algorithm is only O(n) meaning the total number of moves it takes to sort the array of numbers is equal to the length of the list, however, the average and worst case complexity of insertion sort is also O(n^2). Insertion sort algorithm functions by removing an element and generating an output list that increases in size by one for each iteration. The sorted output list will "bump" each element by one until the removed element will be put in the proper location. This sort is good for keeping the list relatively stable since it does not change the order of indices with equal keys.

Bubble sort is similar to insertion sort in terms of complexity since it has a best case complexity of O(n) and its average and worst case complexities are O(n^2). The algorithm works by keeping track of an index and the index right next to it, then swapping the indices if the latter is smaller than the former.This process repeats through the rest of the list and repeatedly passes through the entire list until no more swaps are needed. This sort is particularly efficient in detecting already sorted lists.

The previous three sorting algorithms should only be used for small lists as they are not very efficient when it comes to larger lists. There are other types of sorts that have a good run time such as quick sort and merge sort.

The complexity of quick sort is O(nlogn) as its best case and average case but its worst case is O(n^2). The algorithm works by going through a partition step which selects a random value as the pivot. It then divides the list into two, everything less than the pivot on the left side and everything greater than the pivot on the right. It does this by having a selector on both side of the list and swaps the position of both selectors depending on whether they are greater than, less than, or equal to the pivot.The process then repeats for each division in the list.

The merge sort is very efficient since its best, average, and worst case complexity is O(nlogn). Theoretically, the algorithm works in two steps. The steps are as follows:
1. Split the list into n sub lists, where n is the number of elements in the list. Each sub list is considered sorted since a list of length one is considered sorted.
2. Repeatedly merge sub lists into new sorted sub lists until there is only one sorted sub list remaining and that will be the sorted list.