Algorithm

```
Bubble sort: swap the element with the next element if the are not in the right
order. Swap i with i+1 if they are not in the right order, until i is the end
of the array. We have to repeat the process n times. This is probably the worst
sorting algorithm. If the array is already sorted, the complexity is O(n), but
if the array is not already sorted, the complexity is O(n2).
Selection sort: for each pass, find the smallest number in the remaining array,
and swap it with i.
Insertion sort: sort the first two elements. Take the next remaining unsorted
element, and determine where to insert it into the sorted sub-array, and repeat.
Complexity is O(n2).
O(n2): Selection sort, insertion sort, bubble sort
O(n log n): Merged sort, Heap sort
Heap sort: build the heap using the given elements. If we want to sort the
elements in ascending order we create a Min Heap. If we want to sort the
elements in descending order we create a max heap. Once the heap is created,
we delete the root node from the heap and put the last node in the root position
and repeat the steps until we have covered all the elements. Heap sort is
O(n lg n)
Merge sort: Uses divide-conquer approach. Divide the array into half until
it cannot be divided further. Sort the sub arrays, and then merge them
together. This algorithm can use either the recursive or iterative approach.
Quick sort: This algorithm use the divide-conquer technique, but it does not do
merging. Pick a number, and put it in a position where all the number to the
left of it is smaller than this number, and all the number on the right of it
is larger than this number. Say we pick the first number of the array, we
would then point i to the second element of the array, and j to the last element
of the arry. We would compare the element at i with the value of the selected
element. If the value of the element at the ith position is larger than the
value of the selected element, we do not swap the elements, we just increment
i. If the value of the element at ith is smaller than the value of the selected
element, we swap the elements at i and j, and we increment i and decrement j.
When we put the selected element into the right place, we use the same function
to sort the array that is on the left, and the array that is on the right. On
average, the complexity of this algorithm is O(n log n). In the worst case
scenario, this can be O(n2).
```

page revision: 0, last edited: 07 Nov 2016 03:44