A sorting algorithm is an algorithm that puts elements of a list in a certain order. The most frequently used orders are numerical order and lexicographical order. Efficient sorting is important for optimizing the efficiency of other algorithms(such as search and merge algorithms). More formally, the output of any sorting algorithm must satisfy two conditions:
The output is in nondecreasing order(each element is no smaller than the previous element according to the desired total order);
The output is a permutation(a reordering, yet retaining all of the original elements) of the input.
Sorting algorithms are often classified by:
Computational complexity(worst, average and best behavior) in terms of the size of the list(n). For typical serial sorting algorithms good behavior is O(n log n), with parallel sort in O(log2n), and bad behavior is O(n2).(SeeBig O notation.) Ideal behavior for a serial sort is O(n), but this is not possible in the average case. Optimal parallel sorting is O(log n). Comparison-based sorting algorithms need at least Ω(n log n) comparisons for most inputs.
Memory usage(and use of other computer resources). In particular, some sorting algorithms are"in-place". Strictly, an in-place sort needs only O(1) memory beyond the items being sorted; sometimes O(log(n)) additional memory is considered"in-place".
Recursion. Some algorithms are either recursive or non-recursive, while others may be both(e.g., merge sort).
Stability: stable sorting algorithms maintain the relative order of records with equal keys(i.e., values).
Whether or not they are a comparison sort. A comparison sort examines the data only by comparing two elements with a comparison operator.
General method: insertion, exchange, selection, merging, etc. Exchange sorts include bubble sort and quicksort. Selection sorts include shaker sort and heapsort.
Whether the algorithm is serial or parallel. The remainder of this discussion almost exclusively concentrates upon serial algorithms and assumes serial operation.
Adaptability: Whether or not the presortedness of the input affects the running time. Algorithms that take this into account are known to be adaptive.
Split list into elements and repeatedly merge them into one sorted list. 4x1→2x2→1x4→2x2 sorted→4x1 sorted
MERGE SÖRT
Heapsort
Sorting heapsort anim.gif
Builds max heap(binary sorting tree) from an ARRAY and than rebuilds heap popping one element(root node) at a time.
Path-search
Shortest route between two points.
Dijkstra
Dijkstra Animation.gif
Initial node(first current node) has 0 distance, all other nodes have infinite distances → calculate distance through current to neighbours, replacing old value if found is smaller → current node removed from scope, if it was destination - we are done, if all neighbours infinite - we are done → select nearest neighbour and move on.
An example of A* algorithm in action(nodes are cities connected with roads, h(x) is the straight-line distance to target point) Green: Start, Blue: Target, Orange: Visited
f(n) = h(n) + g(n), where n is the next node on the path, g(n) is the cost of the path from the start node to n, and h(n) is a heuristic function that estimates the cost of the cheapest path from n to the goal. A* terminates when the path it chooses to extend is a path from start to goal or if there are no paths eligible to be extended.
Algorithms
Sort
Path-search
Merge
Graph Traversal