# Basic algorithms in Java

## Searching 🔎

### Linear Search

This is the simplest search algorithm, we iterate through the whole array, if the integer we are searching for is there we return it's index in the array. If we don't see the integer, we return -1 to signal that it is not in the array.

_10public static int linear(int[] array, int x) {_10 for (int i = 0; i < array.length; i++) {_10 if (array[i] == x) {_10 return i;_10 }_10 }_10 return -1;_10}

### Binary Search

this algorithm leverages an already sorted array, by splitting the array and determining on which side of the split the element could be.

#### Iterative

_19public static int binarySearchIterative(int[] array, int x) {_19 int upperLimit = array.length -1;_19 int lowerLimit = 0;_19 int mid;_19_19 while (upperLimit >= lowerLimit) {_19 mid = (upperLimit + lowerLimit) / 2;_19 if (array[mid] == x) {_19 return mid;_19 }_19_19 if (array[mid] > x) {_19 upperLimit = mid - 1;_19 } else {_19 lowerLimit = mid + 1;_19 }_19 }_19 return -1;_19}

#### Recursive

_20public static int binarySearchRecursive(int[] array, int lowerLimit, int upperLimit, int x) {_20 if (upperLimit >= lowerLimit) {_20 int mid = (upperLimit + lowerLimit) / 2;_20_20 if (array[mid] == x) {_20 return mid;_20 }_20_20 if (array[mid] > x) {_20 return binarySearchRecursive(array, lowerLimit, mid - 1, x);_20 }_20_20 return binarySearchRecursive(array, mid + 1, upperLimit, x);_20 }_20 return -1;_20}_20_20public static int binarySearch(int[] array, int element) {_20 return binarySearchRecursive(array, 0, array.length - 1, element);_20}

## Sorting 📮

### Selection Sort

The selection sort algorithm sorts an array by repeatedly finding the minimum element from an unsorted part of an array and placing it at the start of the unsorted part.

_15public static void selectionSort(int[] array) {_15 for (int i = 0; i < array.length ; i++) {_15 int minIndex = i;_15 // find smallest element in array._15 for (int j = i + 1; j < array.length; j++) {_15 if (array[j] < array[minIndex]) {_15 minIndex = j;_15 }_15 }_15 // swap i with the found element._15 int temp = array[i];_15 array[i] = array[minIndex];_15 array[minIndex] = i;_15 }_15}

### Insertion Sort

The insertion sort algorithm sorts an array like a human would sort cards, when you are sorting cards let's say you start at the left, then, you look at the cards before the one you want to place if there are cards that are greater than your current card you put the card where its supposed to go and the others get shifted one place to the right. in real life you just insert the card at the correct place but in java you need to shift the cards that are greater than your current card to the right so you can place your card in that spot where you know it's supposed to go.

_12public static void insertionSort(int[] array) {_12 for (int i = 1; i < array.length; i++) {_12 int key = array[i];_12 int j = i - 1;_12_12 while (j >= 0 && array[j] > key) {_12 array[j + 1] = array[j];_12 j--;_12 }_12 array[j + 1] = key;_12 }_12}

### Bubble Sort

This is a slow sorting algorithm that checks successive elements of an array are they in order ? no -> swap, yes -> next pair.

_11public static void bubbleSort(int[] array) {_11 for (int i = 0; i < array.length; i++) {_11 for (int j = i + 1; j < array.length; j++) {_11 if (array[i] > array[j]) {_11 int temp = array[i];_11 array[i] = array[j];_11 array[j] = temp;_11 }_11 }_11 }_11}

### Quick Sort

QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot.

There are many different versions of quickSort:

• Pick first element as pivot.
• Pick pick last element as pivot (implemented below)
• Pick a random element as pivot.
• Pick the median of low and high as pivot.
_41public static void quickSort(int[] array) {_41 quickSortRecursive(array, 0, array.length-1);_41}_41_41public static void quickSortRecursive(int[] array, int low, int high) {_41 if (low < high + 1) {_41 int partition = partition(array, low, high);_41 quickSortRecursive(array, low, partition - 1);_41 quickSortRecursive(array, partition + 1, high);_41 }_41}_41_41public static int partition(int[] arr, int low, int high) {_41 int pivot = getPivotIndex(low, high);_41 int partitionIndex = 0;_41_41 swap(arr, pivot, high);_41_41 for (int i = 0; i < high; i++) {_41 // we put the pivot arr[high]_41 if (arr[i] <= arr[high]) {_41 swap(arr, i, partitionIndex);_41 partitionIndex++;_41 }_41 }_41 swap(arr, partitionIndex, high);_41_41 return partitionIndex;_41}_41_41private static int getPivotIndex(int low, int up)_41{_41 Random rand = new Random();_41 return rand.nextInt((up - low) + 1) + low;_41}_41_41public static void swap(int[] arr, int a, int b) {_41 int temp = arr[a];_41 arr[a] = arr[b];_41 arr[b] = temp;_41}

### Merge Sort

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, low, middle, middle+1, high) takes arr[low..middle] and arr[middle+1..high] which should be sorted and merges the two them into one.

_47public static void mergeSort(int[] arr) {_47 mergeSortRecursive(arr, 0, arr.length - 1);_47}_47_47public static void mergeSortRecursive(int[] arr, int low, int high) {_47 if (low < high) {_47 int middle = (high + low)/2;_47 mergeSortRecursive(arr, low, middle);_47 mergeSortRecursive(arr, middle + 1, high);_47 merge(arr, low, middle, middle + 1, high);_47 }_47}_47_47public static void merge(int[] arr, int low1, int high1, int low2, int high2) {_47 int index1 = 0;_47 int index2 = 0;_47 int indexArr = low1;_47_47 int[] copy1 = new int[high1 - low1+1];_47 int[] copy2 = new int[high2 - low2+1];_47_47 for (int i = 0; i < copy1.length; i++) {_47 copy1[i] = arr[low1 + i];_47 }_47 for (int i = 0; i < copy2.length; i++) {_47 copy2[i] = arr[low2 + i];_47 }_47_47 while (index1 < copy1.length && index2 < copy2.length) {_47 if (copy1[index1] <= copy2[index2]) {_47 arr[indexArr] = copy1[index1];_47 index1++;_47 } else {_47 arr[indexArr] = copy2[index2];_47 index2++;_47 }_47 indexArr++;_47 }_47_47 for (int i = index1; i < copy1.length; i++, indexArr++) {_47 arr[indexArr] = copy1[i];_47 }_47_47 for (int i = index2; i < copy2.length; i++, indexArr++) {_47 arr[indexArr] = copy2[i];_47 }_47}

Radix is a sorting algorithm that does not use comparison.

Instead it iterates over the digits in the elements you want to sort (for example in base 10, ones', tenths', hundredths' ...) Then we iterate over our elements and we count how many times we find a digit, and we put that count in a count array.

Ok, deep breath 👃

With this count array, we can find what is called the prefix sum which gives you the position+1 of the element should be placed at in the next step.

Then we make a new output array (this array will be ordered but only relative to the digits that have been iterated on), to do this you have to iterate over the input array from right to left, getting the digit of the element. and using the count array with the digit as key to find the new place the element should take.

Thank you for coming to my TED talk 😆

There are several ways of doing Radix Sort:

• with buckets (in practice a linked-list, or a queue like data-structure) takes a lot of memory
• in combination with countingSort. takes less memory but costs more time.

_43public static int[] radixSort(int[] arr) {_43 int[] count = new int;_43 int digit;_43_43 // find the length of the largest number._43 int max = arr;_43 for (int i = 1; i < arr.length; i++) {_43 if (arr[i] > max) {_43 max = arr[i];_43 }_43 }_43 int countDigits = Integer.toString(max).length();_43_43 // Iterate for each digit in the largest number in the array._43 // keep track of the digits, tenths, hundredths ... with digitTen_43 for (int times = 1, digitTen = 1; times <= countDigits; times++, digitTen *= 10) {_43 // clear the count array._43 Arrays.fill(count, 0);_43_43 // for each digit in the increase the count in the count array._43 for (int i = 0; i < arr.length; i++) {_43 digit = arr[i] % (digitTen * 10);_43 digit = digit/digitTen;_43 count[digit]++;_43 }_43_43 // get the prefix sum of the count array._43 for (int i = 1; i < count.length; i++) {_43 count[i] = count[i - 1] + count[i];_43 }_43_43 // use the prefix sum to find the correct index for a digit._43 int[] output = new int[arr.length];_43 for (int i = arr.length - 1; i >= 0; i--) {_43 digit = arr[i] % (digitTen * 10);_43 digit = digit/digitTen;_43 output[--count[digit]] = arr[i];_43 }_43_43 arr = output;_43 }_43 return arr;_43}