Definition: Linear search (also as known as sequential search) is the process of finding a value by searching through every element till we find the value that we want.
Linear Search Implementation in Java
public int linearSearch(int a[], int target){
//returns the index of the target
for(int x=0; x<a.length; x++){
if(a[x] == target)
return x;
}
//returns -1 if the element is not found
return -1;
}Time Complexity: The time complexity of this prorgram is O(n) because it will take a very short time to find the first element but then finding the next element will take longer and so on. The time it takes to find each element will increase linearly which is why the time complexity is O(n).
Best Case, Average Case, and Worst Case
Best Case: You found the first element
Big O Notation: O(1)
Average Case: You found the middle element
Big O Notation: O(n), even though it is O(n/2) but remember we will drop the constant which is 1/2
Worst Case: You found the last element or element is not found
Big O Notation: O(log n)
Definition: Binary search (also as known as half-interval search) is used to find a specific value within an array by cutting half of an array.
Binary Search Implementation in Java
public static int binarySearch (int[] arr, int from, int to, int target) {
if (from > to) {
return -1; //val not found
}
int mid = (from + to)/2;
if (arr[mid] == target){
return mid;
}else if (target > arr[mid]){
return binSearch(arr,mid+1,to,target);
}else{
return binSearch(arr,from,mid-1,target);
}
}Time Complexity: The time complexity of this prorgram is O(log n) since we are dividing the length of the line and getting rid of the half that surely does not contain the value. We keep on doing this until our line is just empty. A line with a length of 8 will cut the line at most 3 times since log 8 is 3. Remember our base of the log is 2 so 2^3 is 8. For more information about the log n runtime click here.
Best Case and Worst Case
Best Case: We found the element by first comparison
Big O Notation: O(1)
Worst Case: We found the element by last comparison or element was not found at all
Big O Notation: O(n)
Defintion: Insertion sort is a sorting algorithm that builds an element one item at a time.
Insertion Sort Implementation in Java
public static void insertion2(int[] a){
int n = a.length;
for (int i = 1; i < n; i++){
for (int j = i; j > 0; j--){
if(a[j-1] > a[j]){
int temp = a[j-1];
a[j-1] = a[j];
a[j] = temp;
}else {
break;
}
}
}
}Time Complexity: The time complexity of this prorgram is O(n^2) since it is a nested for loop where the input, n, is our array.
Best Case and Worst Case
Best Case: Best case applies to an array that is already sorted from the least to the greatest. In this case, we will traverse through the array which is why the runtime is O(n).
Big O Notation: O(n)
Worst Case: Worst case applies to an array that goes from the greatest value to the least value.
Big O Notation: O(n^2)
Definition: Selection sort is a sorting algorithm that sorts an array by repeatedly finding the minimum value and placing it to the beginning of the array until the array is sorted.
This is an example of selection sort where we repatedly bring the minimum element to the front until the array is sorted.
Selection Sort Implementation in Java
public static void sort(int[] a) {
int n = a.length;
for (int i = 0; i < n; i++) {
int min = i;
for (int j = i+1; j < n; j++) {
if (a[j] < a[min])
min = j;
}
int tmp = a[i];
a[i] = a[min];
a[min]= tmp;
}
}Time Complexity: The time complexity of this prorgram is O(n^2) since it is a nested for loop where the input, n, is our array.
Best Case and Worst Case
Best Case: Best case applies to an array that is already sorted from the least to the greatest. We still go through each element for every array run which is why the runtime is still O(n^2).
Big O Notation: O(n^2)
Worst Case: Worst case applies to an array that goes from the greatest value to the least value.
Big O Notation: O(n^2)
Definition: Merge sort is a storting algorithm which consists of dividing the elements and bringing back the elments to a sorted group of elements.
This is an example of merge sort. As you can see, we first divide the elements till they are alone. After that they will be combined till all of the elements have been sorted.
Selection Sort Implementation in Java
public static void sort (int[] a, int lo, int hi){
int n = hi - lo;
if ( n <= 1 )
return;
int middle = lo + n/2;
sort(a, lo, middle);
sort(a, middle, hi);
merge(a, lo, middle, hi);
}
public static void merge (int[] a, int lo, int mid, int hi){
int i = lo, j = mid, n = hi - lo;
int[] aux = new aux[n];
for (int k = 0; k < n; k++) {
if (i == mid)
aux[k] = a[j++];
else if (j == hi)
aux[k] = a[i++];
else if (a[j] < a[i])
aux[k] = a[j++];
else
aux[k] = a[i++];
}
Time Complexity: The time complexity of this prorgram is O(nlog n) since n items are iterated log n times.
Best Case and Worst Case
Best Case: Even if the array is sorted, it will still divide and conqueror.
Big O Notation: O(nlog n)
Worst Case: It will apply to an arrary that goes from the greatest to the least which consists of divide and conqueror.
Big O Notation: O(nlog n)