algorithm

sorting

 linear search

https://en.wikipedia.org/wiki/Linear_search

 

binary search

needs sorted value, 

time complexity = O(log(n))

The binary search tree and B-tree data structures are based on binary search. 

Algorithm:

Given an array of elements with values or records sorted such that , and target value , the following subroutine uses binary search to find the index of in .^[7]

1. Set to and to .
2. If , the search terminates as unsuccessful.
3. Set (the position of the middle element) to the floor of , which is the greatest integer less than or equal to .
4. If , set to and go to step 2.
5. If , set to and go to step 2.
6. Now , the search is done; return .

Pseudocode:

function binary_search(A, n, T) is
    L := 0
    R := n − 1
    while L ≤ R do
        m := floor((L + R) / 2)
        if A[m] < T then
            L := m + 1
        else if A[m] > T then
            R := m − 1
        else:
            return m
    return unsuccessful 

 Pseudocode ceil version:

function binary_search_alternative(A, n, T) is
    L := 0
    R := n − 1
    while L != R do
        m := ceil((L + R) / 2)
        if A[m] > T then
            R := m − 1
        else:
            L := m
    if A[L] = T then
        return L
    return unsuccessful

https://en.wikipedia.org/wiki/Binary_search_algorithm

selection sort

https://en.wikipedia.org/wiki/Selection_sort

for first step n-1 step 

2nd n-2 

n   2 

total step = n-1 + n-2 + ...1 = (n-1)/2 (n-1+1)/2=n(n-1)/2 

bubble sort 

https://en.wikipedia.org/wiki/Bubble_sort 

push biggest element to right by comparing two adjacent 

on n-1 comparision we get first biggest select sorted  

 https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html

merge sort 

sort right half and left half 

merge two half by comparing smallest  

https://en.wikipedia.org/wiki/Merge_sort