Search, sort on memory main call it  search and sort internal

1 Search Algorithm

1.1 LinearSearch: compare every element of array with x

* Cost

Best Case: O(1)
Middel Case: O(n+1/2) // use technique guards
Worst Case: O(n)

* Explain version basic:

Step 1: i = 0 start index head of array
Step 2: compare value of index i in array with x
    array[i] == x return i // index appearance x in array
    array[i] != x continue Step 3
Step 3: i = i++
    if i > N return -1 // x not appearance in array
    i < N repeat Step 2

* Code with technical guards

1.2 Search Binary: 

Intended for array is order (asc,desc), the ideas check with element middle of array
if x < value middle it search the element before middle
if x > value middel it search the element after middle
else x == value of middle return middle

* Cost

Best Case: O(1)
Middel Case: O[log2n/2]
Worst Case: O(log2n)

* Explain :

Step 1: left = 0 , right = length array - 1
Step 2:
    middle = (left + right) / 2
    if x == middle return middle
    if x > middle left = middle + 1 // search the elment from left ... right
    if x < middle right = middle - 1 // search the elment from left ... right
Step 3: if left <= right repeat bước 2
    else return -1

* Code

1.3 Sumary search :

Algorithm Binary searh quickly than LinearSeach
Cost:      log2N < N  
Example: N size of array is 100:  log2(100) = 6 < 100
Require: Order    <-> Not thing

GitHub:

2 Sort Algorithm

2.1 Concept sort

Ascending tăng (bring value max the tail):

Descending giảm (bring value max the head) :

 https://github.com/nguyenthinhit996/sharefullcode/blob/java/Learn%20Java/Java%20Basic/sort/Sorts.java

2.2 Selection Sort (chọn trực tiếp):

Find min of current swap with a[i] current.

* Cost

Best Case: n(n-1) / 2
Worst Case: n(n-1) / 2

* Explain :

Step 1: i = 0 , min = i
Step 2: Find value min of array from j = i + 1 to end Array
Step 3: Swap value of min and value of i
Step 3: i++ if i < n , repeat Step 2
        else Stop sort

* Code 

2.3 Insertaion Sort (chèn trực tiếp):

Suppose array has a[0] orderd, then we add the elements from a[1] --> a[n-1] into current array, it call insertion sort

* Cost

Best Case: n-1 // minus 1 because it start with 1
Worst Case: n(n-1)/2 - 1

* Explain :

Step 1: i = 1
Step 2: foreach from index i-1 to i= 0 of head array if value of index > x, we move to it right(vòng lặp từ vị trí của i-1 đến đầu i=0 nếu giá trị lớn hơn x thì sẽ dời 1 đơn vị sáng phải)
Step 3: if value of  index < x thì sẽ insert vào vị trí đó + 1


* Code

2.4 InterchangeSort (đổi chỗ trực tiếp):

* Cost

Best Case = Worst Case = n(n-1)/2

* Explain :

Step 1: i = 0
Step 2: j = i + 1 , tìm phần tử i < j mà a[i] > a[j] swap 2 giá trị
Step 3: j = j + 1 , và j < n lặp lại bước Step 2
Step 4: i = i + 1 , và i < n-1 lặp lại bước Step 2 + 3


* Code 

2.5 BubbleSort (nổi bọt):

* Cost

Best Case = Worst Case = n(n-1)/2

* Explain :

Step 1: i = 0
Step 2: j = n-1 from index tail to head,
    trong khi (i < j)
    if a[j] < a[j-1] swap value, bring value smaller to head
    j = j - 1
Step 3: i = i + 1
    i < n repeat Step 2, ngược lại stop

* Code

 Shaker Sort

This is advance of bubble sort
sort by 2 browse Go and return 

Go: bring value smaler to head array 

Return : bring value bigger to tail array

2.6 Quickly Sort

* Cost :
Best Case: n*log2(n)
Middle Case: n*log2(b)
Worst Case: n^2

Explain:
Step 1: x=a[k], i = left, j = right
Step 2: find the couple incorect
    While (a[i] < x) i++
    While (a[j] > x) j--
    if i <= j , a[i] > a[j]
    swap value, next i++, j--
Step 3: i < j , repeat Step 2
    i >= J Stop

Code :

 Git search and sort: https://github.com/nguyenthinhit996/sharefullcode/tree/master/structureWithAlgorithm