AlgoDS/Algorithm
-
QuicksortAlgoDS/Algorithm 2020. 1. 16. 22:58
1. Overview Like Merge Sort, QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways. Always pick the first element as a pivot. Always pick the last element as the pivot (implemented below) Pick a random element as pivot. Pick the median as a ..
-
Binary SearchAlgoDS/Algorithm 2020. 1. 16. 22:57
1. Overview Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the value is found or the interval is empty. 2. Description 2.1 Procedure Comp..
-
RecursionAlgoDS/Algorithm 2020. 1. 16. 22:56
1. Overview Recursion makes the code easy to write compared to iterative whenever a given problem can be broken down into a similar sub-problem. It has some properties like below: The same operation is performed multiple times with different inputs In every step, we try to make the problem smaller We mandatorily need to have a base condition, which tells the system when to stop the recursion. 2...
-
Searching and Sorting with ArrayAlgoDS/Algorithm 2019. 9. 4. 21:12
1. Overview Two array processing technique that are particularly common are searching and sorting. Searching here refers to finding an item in the array that meets some specified criterion. Sorting refers to rearranging all the items in the array into increasing or decreasing order. 2. Description Sorting Process Big O Selection Sort Find the smallest value in A and put it in A[0] Find the secon..
-
Merge SortAlgoDS/Algorithm 2019. 8. 31. 14:45
1. Overview Like QuickSort, Merge Sort is a Divide and Conquer algorithm. It divides input array into two halves, calls itself for the two halves and then merges the two sorted halves. The merge() function is used for merging two halves. The merge(arr, l, m, r) is a key process that assumes that arr[l..m] and arr[m+1..r] are sorted and merges the two sorted sub-arrays into one. See the following..