# Java Tutorial: Sorting and Searching

Posted 2020/06/02

## Time Complexity Time complexity is how many steps are required to complete an algorithm. When measuring time complexity, we make an average, best, and worst time complexities. The average time complexity is roughly how many steps are performed on average. The best and worst time complexities are how many steps it takes in the algorithm’s best and worst-case scenarios. Time complexity is expressed using Big-O notation, where n represents the input size or array length. For example a time complexity of O(n) means that the algorithm will take the same amount of steps as the array size.

## Sorting

Sorting is the process of putting items of a list in a certain order. Most times, sorting is done to order a list in numerical or lexicographical order. There are many different algorithms for sorting with varying levels of simplicity and efficiency.

### Bubble Sort Bubble sort is one of the simplest sorting algorithms. This algorithm looks at adjacent values in the list and compares them and swaps if that pair is in the wrong order. It repeats this until the list is sorted.

#### Time Complexity

Worst-case: O(n2)
Average: O(n2)
Best-case: O(n)

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15``` ``````public static void bubbleSort(int[] arr) { boolean sorted = false; int temp; //temporary variable for swaps while (!sorted) { sorted = true; for (int i = 0; i < arr.length - 1; i++) { //iterate through list if (arr[i] > arr[i+1]) { //compare adjacent items temp = arr[i]; //if not in order swap arr[i] = arr[i+1]; arr[i+1] = temp; sorted = false; //if swap made then array is not sorted, run another rotation } } } } `````` ### Insertion Sort

Insertion sort builds the sorted list one item at a time. It creates two sublists and takes the next item of the unsorted sublist and inserts it in its proper position in the sorted sublist. It repeats until all items have been placed in their proper position in the sorted sublist.

#### Time Complexity

Worst-case: O(n2)
Average: O(n2)
Best-case: O(n)

 ``` 1 2 3 4 5 6 7 8 9 10 11 12``` ``````public static void insertionSort(int arr[]) { for (int i = 1; i < arr.length; ++i) { //iterate through loop int key = arr[i]; //value to move int j = i - 1; //sorted sublist while (j >= 0 && arr[j] > key) { //shift elements arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = key; //insert } } ``````

### Selection Sort

Selection sort also builds the sorted list one item at a time. It creates two sublists and scans the unsorted sublist for the next item to place at the end of the sorted sublist. It repeats until all items have been moved from the unsorted sublist to the sorted sublist.

#### Time Complexity

Worst-case: O(n2)
Average: O(n2)
Best-case: O(n2)

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17``` ``````public static void selectionSort(int[] arr){ int n = arr.length; int min = 0; for(int i=0; i < n-1; i++){ //size of sorted subarray min = i; for(int j=i; j < n; j++){ //scan unsorted subarray if(arr[min] > arr[j]){ //if smaller set as min min = j; } if(min != i){ //swap min to end of sorted int temp=arr[min]; //write min to temporary var arr[min]=arr[i]; //write index i to min index arr[i]=temp; //write temp var to index i } } } } `````` ### Merge Sort

Merge sort is a divide and conquer sorting algorithm. The algorithm splits the list into sublists of just one element each and merges the sorted sublists together to make the final sorted list. This algorithm is a recursive algorithm.

#### Time Complexity

Worst-case: O(n log n)
Average: O(n log n)
Best-case: O(n log n)

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38``` ``````public static void mergeSort(int[] arr, int n) { if (n < 2) { // subarray has one element it is sorted return; } int mid = n / 2; //half of array int[] l = new int[mid]; //first half subarray int[] r = new int[n - mid]; //second half subarray for (int i = 0; i < mid; i++) { //copy first half l[i] = arr[i]; } for (int i = mid; i < n; i++) { //copy second half r[i - mid] = a[i]; } mergeSort(l, mid); //sort first half mergeSort(r, n - mid); //sort second half merge(arr, l, r, mid, n - mid); //put halves together } public static void merge(int[] a, int[] l, int[] r, int left, int right) { int i = 0, j = 0, k = 0; //pointers on left, right, and merge arrays while (i < left && j < right) { //while both arrays being compared if (l[i] <= r[j]) { //if left pointer value smaller than right a[k++] = l[i++]; //add left to merged array } else { a[k++] = r[j++]; } } while (i < left) { a[k++] = l[i++]; } while (j < right) { a[k++] = r[j++]; } } ``````

## Searching

Searching is the process of fetching data stored in data structures like arrays or lists. Most search algorithms are used to find the location of an item in a data structure.

### Linear/Sequential Search

Linear or sequential search is a brute-force algorithm that scans the list or array looking for a match to the search term. This search algorithm is not time efficient and is very slow when used on large lists.

#### Time Complexity

Worst-case: O(n)
Average: O(n)
Best-case: O(1)

 ```1 2 3 4 5 6``` ``````public static int linearSearch(int[] arr, int search){ for(int i=0; i < arr.length; i++){ //loop through items if(arr[i] == search) return i; //return index if matches } return -1; } ``````

### Binary/Logarithmic Search

Binary or logarithmic search is a divide and conquer algorithm that requires the data structure to be already sorted. The algorithm splits the data set in half and compares the search term with the item in the middle. Using this comparison it knows which half to search for the item. It then repeats this process on the half until the item has been found.

#### Time Complexity

Worst-case: O( log n)
Average: O( log n)
Best-case: O(1)

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17``` ``````public static int binarySearch(int arr[], int search) { int firstIndex = 0; int lastIndex = arr.length - 1; while(firstIndex <= lastIndex) { //termination condition (can't be found) int middleIndex = (firstIndex + lastIndex) / 2; if (arr[middleIndex] == search) { //if middle is element then return index return middleIndex; } else if (arr[middleIndex] < search) firstIndex = middleIndex + 1; //if middle is smaller go to second half else if (arr[middleIndex] > search) lastIndex = middleIndex - 1; //if middle is larger go to first half } return -1; } ``````