linear search or sequential search is a method for finding a target value within a list. It sequentially checks each element of the list for the target value until a match is found or until all the elements have been searched.
public static void linearSearch(int[] numsArray, int numToFind) {
int i = 0;
int count = 0;
while (numsArray[i] != numToFind && i < numsArray.length - 1) {
i++;
if (numToFind == numsArray[i]) {
System.out.println("Found a match for " +
numToFind + " at index: " + i);
}
count++;
System.out.println("round..." + count);
}
}
public static void main(String[] args) {
int[] nums = {10, 12, 13, 16, 19, 23, 32, 41, 60, 67, 89, 90, 100, 112};
linearSearch(nums, 90);
}
Convert this Linear search algorithm using a "For" loop structure.
The Binary Search is quicker than the linear search because all the values are sorted. Because everything is sorted once you get to a number larger than what you are looking for you can stop the search. Also you'll be able to start searching from the middle which speeds the search. It also works best when there are no duplicates.
public static void binarySearch(int[] someArray, int value) {
int lowIndex = 0;
int highIndex = someArray.length - 1;
int count = 1;
while (lowIndex <= highIndex) {
System.out.println("round..." + count);
int middleIndex = (highIndex + lowIndex) / 2;
if (someArray[middleIndex] < value) {
lowIndex = middleIndex + 1;
} else if (someArray[middleIndex] > value) {
highIndex = middleIndex - 1;
} else {
lowIndex = highIndex + 1;
System.out.println("Done here at " + middleIndex);
return;
}
count++;
}
}
public static void main(String[] args) {
int[] nums = {10, 12, 13, 16, 19, 23, 32};
binarySearch(nums, 32);
}
Research on Binary search recursive algorithm and understand how the algorithm works
Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.
Example:
First Pass:
( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1.
( 1 5 4 2 8 ) –> ( 1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 ) –> ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.
Second Pass:
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 )
( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Swap since 4 > 2
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.
Third Pass:
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
// Java program for implementation of Bubble Sort
class BubbleSort{
void bubbleSort(int arr[]){
int n = arr.length;
for (int i = 0; i < n-1; i++)
for (int j = 0; j < n-i-1; j++)
if (arr[j] > arr[j+1]){
// swap temp and arr[i]
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
/* Prints the array */
void printArray(int arr[]){
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
// main method to test above
public static void main(String args[]){
BubbleSort ob = new BubbleSort();
int arr[] = {64, 34, 25, 12, 22, 11, 90};
ob.bubbleSort(arr);
System.out.println("Sorted array");
ob.printArray(arr);
}
}
/* This code is written by Rajat Mishra */
Research on a Bubble sort algorithm that sorts a data set in descending order
The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning. The algorithm maintains two subarrays in a given array.
The subarray which is already sorted.
Remaining subarray which is unsorted.
In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray.
Following example explains the above steps:
arr[] = 64 25 12 22 11
// Find the minimum element in arr[0...4]
// and place it at beginning 11 25 12 22 64
// Find the minimum element in arr[1...4]
// and place it at beginning of arr[1...4] 11 12 25 22 64
// Find the minimum element in arr[2...4]
// and place it at beginning of arr[2...4] 11 12 22 25 64
// Find the minimum element in arr[3...4]
// and place it at beginning of arr[3...4] 11 12 22 25 64
public class SelectionSort {
//time complexity = O(n2)
public int[] selectionSortAscending(int[] nums) {
for (int i = 0; i < nums.length - 1; i++) {
int index = i;
int smallest = nums[index];
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] < smallest) {
index = j;
smallest = nums[j];
}
}
//you can call the swap method
if (index != i) {
nums[index] = nums[i];
nums[i] = smallest;
}
}
return nums;
}
public int[] selectionSortDescending(int[] nums) {
int i, j, first, temp;
for (i = nums.length - 1; i > 0; i--) {
first = 0;
for (j = 1; j <= i; j++) {
if (nums[j] < nums[first]) {
first = j;
}
}
temp = nums[first];
nums[first] = nums[i];
nums[i] = temp;
}
return nums;
}
}
class TestSelectionSort {
public static void main(String[] args) {
SelectionSort ss = new SelectionSort();
int[] num = {5, 1, 7, 3, 2, 9, 4, 7};
ss.selectionSortAscending(num);
for (int i = 0; i < num.length; i++) {
System.out.print(num[i] + " ");
}
System.out.println("");
ss.selectionSortDescending(num);
for (int i = 0; i < num.length; i++) {
System.out.print(num[i]+ " ");
}
}
}
Research on a Selection sort algorithm that sorts a data set in descending order
Insertion sort is a simple sorting algorithm that works the way we sort playing cards in our hands.
Example:
Another Example:
12, 11, 13, 5, 6
Let us loop for i = 1 (second element of the array) to 5 (Size of input array)
i = 1. Since 11 is smaller than 12, move 12 and insert 11 before 12
11, 12, 13, 5, 6
i = 2. 13 will remain at its position as all elements in A[0..I-1] are smaller than 13
11, 12, 13, 5, 6
i = 3. 5 will move to the beginning and all other elements from 11 to 13 will move one position ahead of their current position.
5, 11, 12, 13, 6
i = 4. 6 will move to position after 5, and elements from 11 to 13 will move one position ahead of their current position.
5, 6, 11, 12, 13
public class InsertionSort {
public int[] insertionSort(int[] arr) {
int i = 1;
while (i < arr.length) {
int x = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > x) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = x;
i = i + 1;
}
return arr;
}
//recursive variant
public int[] insertionSort(int[] arr, int n){
if(n > 0){
insertionSort(arr, n-1);
int x = arr[n];
int j = n - 1;
while(j >=0 && arr[j] > x){
arr[j+1] = arr[j];
j = j-1;
}
arr[j+1] = x;
}
return arr;
}
}
class TestClass {
public static void main(String[] args) {
InsertionSort is = new InsertionSort();
int[] num1 = {2, 3, 4, 2, 1, 5, 6, 3};
is.insertionSort(num1);
for (int i = 0; i < num1.length; i++) {
System.out.println(num1[i]);
}
int[] num2 = {10, 100, 20, 30, 40, 21, 30, 10};
is.insertionSort(num2, 7);
for (int i = 0; i < num2.length; i++) {
System.out.println(num2[i]);
}
}
}
Research on a Insertion sort algorithm that sorts a data set in descending order
Like QuickSort, Merge Sort is a Divide and Conquer algorithm. It divides input array in 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 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 following C implementation for details.
MergeSort(arr[], l, r)
If r > l
1. Find the middle point to divide the array into two halves:
middle m = (l+r)/2
2. Call mergeSort for first half:
Call mergeSort(arr, l, m)
3. Call mergeSort for second half:
Call mergeSort(arr, m+1, r)
4. Merge the two halves sorted in step 2 and 3:
Call merge(arr, l, m, r)
The following diagram from wikipedia shows the complete merge sort process for an example array {38, 27, 43, 3, 9, 82, 10}.
If we take a closer look at the diagram, we can see that the array is recursively divided in two halves till the size becomes
1. Once the size becomes 1, the merge processes comes into action and starts merging arrays back till the complete array is merged.
public class MergeSort {
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r) {
// Find sizes of two subarrays to be merged
int n1 = m - l + 1;
int n2 = r - m;
/* Create temp arrays */
int L[] = new int[n1];
int R[] = new int[n2];
/*Copy data to temp arrays*/
for (int i = 0; i < n1; ++i) {
L[i] = arr[l + i];
}
for (int j = 0; j < n2; ++j) {
R[j] = arr[m + 1 + j];
}
/* Merge the temp arrays */
// Initial indexes of first and second subarrays
int i = 0, j = 0;
// Initial index of merged subarry array
int k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
/* Copy remaining elements of L[] if any */
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
/* Copy remaining elements of R[] if any */
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// Main function that sorts arr[l..r] using
// merge()
void sort(int arr[], int l, int r) {
if (l < r) {
// Find the middle point
int m = (l + r) / 2;
// Sort first and second halves
sort(arr, l, m);
sort(arr, m + 1, r);
// Merge the sorted halves
merge(arr, l, m, r);
}
}
}
class TestClass2 {
public static void main(String[] args) {
MergeSort ms = new MergeSort();
int[] num = {6, 1, 5, 3, 7, 9, 2, 3, 4};
ms.sort(num, 0, 8);
for (int i = 0; i < num.length; i++) {
System.out.println(num[i]);
}
}
}
Research on a Merge sort algorithm that sorts a data set in descending order
“Sorting Algorithm.” Wikipedia, Wikimedia Foundation, 9 May 2018, en.wikipedia.org/wiki/Sorting_algorithm.
“Sorting Algorithms.” GeeksforGeeks, www.geeksforgeeks.org/sorting-algorithms/.