25 June 2013

by mo

# sorting

A sorting algorithm is an algorithm that puts elements of a list in a certain order. - Wikipedia

## bubble sort

• pass through the data from one end to the other, swap adjacent elements whenever the first is greater than the last.
• O(n^2) - very slow for large data sets

## insertion sort

• seeks to sort a list one element at a time.
• one of the principal advantages of the insertion sort is that it works very efficiently for lists that are nearly sorted initially.
• It can also work on data sets that are constantly being added to.
• e.g. if one wanted to maintain a sorted list of the highest scores achieved in a game, an insertion sort would work well, since new elements would be added to the data as the game was played.

## merge sort

• works recursively. First it divides a data set in half, and sorts each half separately.
• next the first elements from each of the two lists are compared.
• the lesser element is then removed from its list and added to the final result list.
• optimization for nearly sorted lists.
• if the highest element in one list is less than the lowest element in the other half, the the merge steps is unnecessary.

## heap sort

• we create a heap data structure.
• head datastructure: stored in a tree such that all the smallest (or largest) elements is always the root node.
• all data is inserted into a heap, then the root element is removed and stored back into the list.

## quick sort

• efficient sorting algorithm.
• divide the data into two groups of “high” values and “low” values.
• then recursively process the two halves. then reassemble the now sorted list.
algorithms 💎