Please enable JavaScript.
Coggle requires JavaScript to display documents.
Searching and Sorting (P3) - Coggle Diagram
Searching and Sorting (P3)
Searching
Binary-Search (A,n,x)
For ordered lists
Running time:
θ(log n)
How it works
: divide array in half; compare x to half element; otherwise if element is larger than x go back on array and do the same thing; otherwise if element is smaller than x go forward in array and do same thing
Correctness proof: Loop invariant at the start of the loop, if x is anywhere in A, then it is somewhere in the sub array A[p...r]
Sorting
Selection Sort (A,n)
Input
: an array A and the number n of elements in A to sort
Output
: the elements of A sorted into non-decreasing order
How it works
: Set first element as the smallest; if element you're on is smaller than the smallest element then change variable 'smallest' to that and and swap their place; carry till end of array
In place
Running time: θ(n^2)
Insertion Sort (A)
How it works:
increment elements in array for each element do a backward comparison until that element is smaller than the array element before it
An incremental algorithm
: which processes the input elements one-by-one and maintains the solution for the elements processes so far
Running Time:
θ(n^2)
In place
Merge-Sort (A)
How it works
: Divide the array into 2 until split into individual elements; Merge and sort all pieces until all elements have been ordered
Running time: θ(n log n)
Not in-place
