Sorting and Searching

Sorting and Searching

Sorting

1. Bubble Sort
2. Selection Sort
3. Insertion Sort
4. QuickSort
5. Merge Sort

Bubble Sort

Compare two array and swap is necessary. For example if array[1] is greater than array[2] than swap. Using a variable temp to store array[1] then assign array[2] to array[1] and lastly assign temp to array[2].

Selection Sort

Finding the minimum value of an array then put it at the beginning and repeat it until all data are sorted.

Insertion Sort

Pick an element and check the array before if the element is smaller than the array before then insert before the array.

Quick Sort

In quick sort, we pick an element as pivot (usually the first element). then we compare the last data and the second element and the pivot. 

Merge Sort

Divides the array into two parts, then divide each part into smaller part. Then start sorting. Combine the small parts then sort again. And lastly combine all parts then sort all the elements again.


Searching

1. Linear Search

2. Binary Search

3. Interpolation Search

Linear Search

If you want to search X, then compare from array[0] until the last array. if array[a] match with X, return the index.

Binary Search

Binary search a sorted array by repeatedly dividing the search interval in half. If you want to search X, compare X with the middle element. If match return the middle index. Else if X greater than the middle element, recur for the right half. Else if X is smaller than the middle element, recur for the left half.

Interpolation Search

If you want to search X, compare X with pos. If match return the index. Else if X greater than post, recur for the right half. Else if X is smaller than pos, recur for the left half.

  

Princess Jesslyn Lorenza
2201750036

binus.ac.id

skyconnectiva.com