Arrays are used for storing data sequentially for processing. Sorting algorithms can take the elements of an array and put them in order. The operation of insertion sort is illustrated on the array A = [ 40, 15, 30, 5, 25, 10, 20, 35 ].
Merge sort is another sorting algorithm used to place data in a certain order. Unlike insertion sort, the data structure which may be an array is divided with the pieces reassembled while the data in each piece is put in order. The process that merge sort uses is shown with the array B = [ 40, 15, 30, 5, 25, 10, 20, 35 ].
Big O notation is used to decribe the computational complexity of an algorithm. Since the behavior of an algorithm can be represented by a mathematical function, the behavior of the function can be described by how fast it increases. The order of the function is without constants and coefficients and depends on its highest degree if it is a polynomial. The order can be exponential or logarithmic also. Whatever the order of a function, it is written in parenthesis with a capital O. For example, 3x3+4x2+5x+2 would be O(n3).
The following determines an O(f(n)) bound for the following pseudocode assuming n is a known, fixed value.
| r = 1 | |
| t =n * n * n | |
| First statement cost is 1 operation | |
| Second statement cost is 3 operations | |
| Total statement cost is 4 operations | |
| n is a known, fixed value means n is like a constant | |
| f(n) = 4 | |
| 0 ≤ f(n) ≤ cg(n) | |
| 0 ≤ 4 ≤ 5 | |
| Therefore, O(1) |
Another sorting algorithm frequently used is quicksort. Quicksort can sort an array in nlog n time where n is the number of items to be sorted. In big O notation, this would be stated as O(nlog n). Quicksort uses the divide and conquer process to sort quickly.