a linear search or sequential search is a method for finding an element within a list. It sequentially checks each element of the list until a match is found or the whole list has been searched.
A linear search runs in at worst linear time and makes at most n comparisons, where n is the length of the list. If each element is equally likely to be searched, then linear search has an average case of n/2 comparisons, but the average case can be affected if the search probabilities for each element vary - wikipedia
public static int LinearSearch2(String[] words, String wordToSearch) {
for (int index = 0; index < words.length; index++) {
if (words[index].equals(wordToSearch)) {
return index;
}
}
return -1;
}
binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array.
Binary search compares the target value to the middle element of the array.
If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found.
If the search ends with the remaining half being empty, the target is not in the array. - wikipedia
public int binarySearch(int arr[], int x) {
int l = 0, r = arr.length - 1;
while (l <= r) {
int m = l + (r - l) / 2;
if (arr[m] == x) { // Check if x is present at mid
return m;
}
if (arr[m] < x) { // If x greater than mid, ignore left half
l = m + 1;
}else { // If x is smaller than mid, ignore right half
r = m - 1;
}
}
return -1; // if we reach here, then element was not present
}
public int binarySearch(int arr[], int l, int r, int x) {
if (r >= l) {
int mid = l + (r - l) / 2;
// If the element is present at the middle itself
if (arr[mid] == x) {
return mid;
}
// If element is smaller than mid, then
// it can only be present in left subarray
if (arr[mid] > x) {
return binarySearch(arr, l, mid - 1, x);
}
// Else the element can only be present in right subarray
return binarySearch(arr, mid + 1, r, x);
}
// We reach here when element is not present in array
return -1;
}
"a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted. The algorithm, which is a comparison sort, is named for the way smaller or larger elements "bubble" to the top of the list." - wikipedia
public static void BubbleSortAscending(double[] items) {
for (int i = 0; i < (items.length - 1); i++) {
for (int k = 0; k < (items.length - 1 - i); k++) {
if (items[k] > items[k + 1]) {
double temp = items[k];
items[k] = items[k + 1];
items[k + 1] = temp;
}
}
}
}
public static void BubbleSortDescending(int[] nums) {
int j;
boolean flag = true;
int temp;
while (flag) {
flag = false;
for (j = 0; j < nums.length - 1; j++) {
if (nums[j] > nums[j + 1]) {
temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
flag = true;
}
}
}
}
selection sort is an in-place comparison sorting algorithm.
The algorithm divides the input list into two parts: a sorted sublist of items which is built up from left to right at the front (left) of the list and a sublist of the remaining unsorted items that occupy the rest of the list.
Initially, the sorted sublist is empty and the unsorted sublist is the entire input list.
The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right. - wikipedia
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 for this
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;
}
Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time.
Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.
Sorting is typically done in-place, by iterating up the array, growing the sorted list behind it. At each array-position, it checks the value there against the largest value in the sorted list (which happens to be next to it, in the previous array-position checked). If larger, it leaves the element in place and moves to the next. If smaller, it finds the correct position within the sorted list, shifts all the larger values up to make a space, and inserts into that correct position. - wikipedia
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;
}
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;
}
an efficient, general-purpose, comparison-based sorting algorithm.
a divide and conquer algorithm
Divide the unsorted list into n sublists, each containing one element (a list of one element is considered sorted).
Repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining. This will be the sorted list. - wikipedia
// 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 sub-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);
}
}