Introduction
Understanding the common sorting and searching algorithms is incredibly valuable, as many sortings and searching problems are tweaks of the well-known algorithms. Two factors influence greatly, ie space and time complexity.
Common Sorting Algorithms
Selection Sort
This is one of the easy algorithms, find the smallest element using a linear scan and move it to the front. Then, find the second smallest and move it, again doing a linear scan. Continue doing this until all the elements are in place.
private static void selectionSort() {
int[] array = new int[100];
for (int i = 0; i < 100 ; i++) {
array[i] = new Random().nextInt();
}
for (int i= 0; i < array.length; i++) {
for (int j = i + 1; j < array.length; j++) {
if (array[i] > array[j]) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}
Arrays.stream(array).forEach(System.out::println);
}
Bubble Sort
In bubble sort, we start at the beginning of the array and swap the first two elements if the first is greater than the second. Then we go to the next pair, and so on, continuously making sweeps of the array until it is sorted. In doing so, the smaller items slowly bubble up to the beginning of the list.
private static void bubbleSort() {
int[] array = new int[100];
for (int i = 0; i < 100 ; i++) {
array[i] = new Random().nextInt();
}
for (int i= 0; i < array.length - 1; i++) {
for (int j = 0; j < array.length - 1; j++) {
if (array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
Arrays.stream(array).forEach(System.out::println);
}
Merge Sort – O(n log(n)) average and worst case.
Merge sort divides the array in half, sorts each of those halves, and then merges them back together. Each of those halves has the same sorting algorithm applied to it. Eventually, you are merging just two single-element arrays. it is the ‘merge’ part that does all the heavy lifting.
package com.jonesjalapat.java.searchsort;
import java.util.Arrays;
public class MergeSort {
public static void main(String[] args) {
int[] array = { 2, -5, 3, -4, 1, 2, 5, -9};
mergeSort(array);
Arrays.stream(array).forEach(System.out::println);
}
private static void mergeSort(int[] array) {
int arrayLength = array.length;
if (arrayLength < 2) {
return;
}
int mid = array.length/ 2;
int[] firstHalf = new int[mid];
int[] secondHalf = new int[array.length - mid];
for (int i =0; i < mid; i++) {
firstHalf[i] = array[i];
}
for (int i = mid; i < array.length; i++) {
secondHalf[i - mid] = array[i];
}
mergeSort(firstHalf);
mergeSort(secondHalf);
merge(array, firstHalf, secondHalf);
}
private static void merge(int[] array, int[] firstHalf, int[] secondHalf) {
int i = 0, j = 0, k =0;
while (i < firstHalf.length & j < secondHalf.length) {
if (firstHalf[i] > secondHalf[j]) {
array[k] = firstHalf[i];
i ++;
} else {
array[k] = secondHalf[j];
j++;
}
k++;
}
while ( i < firstHalf.length) {
array[k] = firstHalf[i];
i++;
k++;
}
while ( j < secondHalf.length) {
array[k] = secondHalf[j];
j++;
k++;
}
}
}
Quick Sort – O( n log(n)) average, O(n2) worst case
In quick sort, we pick a random element and partition the array, such that all numbers that are less than the partitioning element come before all elements that are greater than it. The partitioning can be performed efficiently through a series of swaps. If we repeatedly partition the array around an element, the array will eventually become sorted.
Quicksort is an efficient, general-purpose sorting algorithm. Overall, it is slightly faster than merge sort and heapsort for randomized data, particularly on larger distributions. Quicksort is a comparison sort, meaning that it can sort items of any type for which a “less-than” relation (formally, a total order) is defined. Most implementations of quicksort are not stable, meaning that the relative order of equal sort items is not preserved.
Radix Sort – O(kn)
In computer science, radix sort is a non-comparative sorting algorithm. It avoids comparison by creating and distributing elements into buckets according to their radix. For elements with more than one significant digit, this bucketing process is repeated for each digit, while preserving the ordering of the prior step, until all digits have been considered. For this reason, radix sort has also been called bucket sort and digital sort. Finally, In radix sort, we iterate through each digit of the number, grouping numbers by each digit. For example, if we have an array of integers, we might first sort by the first digit, so that the 0s are grouped together. Then, we sort each of these groupings by the next digit. We repeat this process sorting by each digit, until finally the whole array is sorted.
Searching Algorithm
When we think of searching algorithms, we generally think of binary search. In binary search, we look for an element x in a sorted array by first comparing x to the midpoint of the array. If x is less than te midpoint, then we search the left half of the array. If x is greater than the midpoint, then we search the right half of the array. We then repeat this process, treating the left and right halves as subarrays. Again, we compare x to the midpoint of this subarray and then search either its left or right side. We repeat this process until we either find x or the subarray has size 0.
package com.jonesjalapat.java.searchsort;
public class BinarySearch {
public static void main(String[] args) {
int[] array = { 2, -5, 3, -4, 1, 2, 5, -9};
selectionSort(array);
System.out.println( binarySeatch(0, array.length -1, array, 6));
}
private static int binarySeatch(int low, int high, int[] array, int x) {
if (low > high) {
return -1;
}
int mid = (low + high)/ 2;
if (array[mid] > x) {
binarySeatch(low, mid -1, array, x);
} else if (array[mid] < x) {
binarySeatch(mid + 1, high, array, x);
} else {
return mid;
}
return -1;
}
private static void selectionSort(int[] array) {
for (int i= 0; i < array.length; i++) {
for (int j = i + 1; j < array.length; j++) {
if (array[i] > array[j]) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}
}
}
