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
for (int i = 0; i < data.Length; i++)
for (int j = 0; j < data.Length - 1; j++)
if (data[j] > data[j+1])
{
tmp = data[j]
data[j] = data[j+1]
data[j + 1] = tmp
}
insertion sort
for (int i = 0; i < data.Length; i++) {
int j = i;
while (j > 0 && data[i] < data[j-1])
j--;
int tmp = data[i];
for (int k = i; k > j; k--)
{
data[k] = data[k -1];
}
data[j] = tmp;
}
- 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.
library sort
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
Heap h = new Heap();
for (int i = 0; i < data.Length; i++)
h.Add(data[i]);
int[] result = new int[data.length];
for (int i = 0; i < data.Length; i++)
data[i] = h.RemoveLowest();
- 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.
Array quickSort(Array data)
{
if (data.Length <= 1)
return;
middle = Array[data.Length / 2];
Array left = new Array();
Array right = new Array();
for (int i=0; i < data.Length; i++)
{
if(i != data.Length / 2)
{
if (data[i] <= middle)
left.Add(data[i]);
else
right.Add(data[i]);
}
}
return combine(quickSort(left), middle, quickSort(right));
}