# The Quick Sort Algorithm

The quick sort algorithm is slower than merge sort algorithm, but requires less space, since it does not copy the array being searched into a temporary array, but performs all operations on the initial array.

The hart of the quick sort is the partitioning process. The algorithm picks a place in the array (usually the last element) and considers it to be a pivot. Then it throws every value that is less than that pivot to the left, and a value greater than the pivot to the right. After that the pivot is placed in the correct position of where it belongs in the array. Then the partitioning process begins in the right part of the array, and in the left part of the array until all elements of the array are sorted.

Code in Java:

```public static void main(String[] args) {
int[] inputArray = {9,8,3,13,87,12,99};
quickSort(inputArray, 0, inputArray.length-1);
System.out.println(Arrays.toString(inputArray));
}

public static void quickSort(int[] inputArray, int start, int end) {
if (start < end) {
int partition = partition(inputArray, start, end); // index position
// of the corrected placed element
quickSort(inputArray, start, partition - 1); // sorts the left half of the range
quickSort(inputArray, partition + 1, end); // sorts the right half of the range
}
}
private static int partition(int[] inputArray, int start, int end) {
int pivot = inputArray[end]; // pivot at the end of the array
int i = start - 1;  // the place before the start point (-1)
for (int j = start; j <= (end - 1); j++) {
if (inputArray[j] <= pivot) {
i++;
// swapping
int temp = inputArray[i];
inputArray[i] = inputArray[j];
inputArray[j] = temp;
}
}
// put the pivot value in the correct slot next
int temp = inputArray[i + 1];
inputArray[end] = temp;
inputArray[i + 1] = pivot;
return i + 1;
}
```

# The Merge Sort Algorithm

The merge sort algorithm is pretty fast algorithm for sorting list elements. Its running time is O(n log n). The merge sort may implement a recursive approach. Splitting sets the data to the stage where it is eligible for being merge.

```public class MergeSort {
public static void sort(int inputArray[]) {
sort(inputArray, 0, inputArray.length-1);
}

public static void sort(int inputArray[], int start, int end) {
if (end <= start) {
return; // done traversing the array
}
int mid = (start + end) / 2;
sort(inputArray, start, mid); // sort left half
sort(inputArray, mid+1, end); // sort right half
merge(inputArray, start, mid, end);
}

public static void merge(int inputArray[], int start, int mid, int end) {
int[] tempArray = new int[end - start + 1];
int leftSlot = start;
int rightSlot = mid + 1;
int k = 0;

while(leftSlot <= mid && rightSlot <= end) {
if (inputArray[leftSlot] < inputArray[rightSlot]) {
tempArray[k] = inputArray[leftSlot];
leftSlot++;
} else {
tempArray[k] = inputArray[rightSlot];
rightSlot++;
}
k++;
}

if (leftSlot <= mid) {
while(leftSlot <= mid) {
tempArray[k] = inputArray[leftSlot];
leftSlot++;
k++;
}
} else if (rightSlot <= end) {
while(rightSlot <= end) {
tempArray[k] = inputArray[rightSlot];
rightSlot++;
k++;
}
}

for (int i = 0; i < tempArray.length; i++) {
inputArray[start+i] = tempArray[i];
}

}
}
```

Starting point:

```int[] inputArray = {9,8,3,13,87,12,99};
MergeSort sorter = new MergeSort();

sorter.sort(inputArray);
for (int i = 0; i < inputArray.length; i++) {
System.out.print(inputArray[i] + " ");
}
```

# The Insertion Sort Algorithm

The insertion sort algorithm is of O(n2) complexity. It divides an array into two sections: a sorted section and unsorted section. In each step of the algorithm the number is moved from unsorted section to sorted one, until the entire array is sorted.
This is a pseudo code:
``` Procedure: insertionSort(a) Inputs: - a: the array to sort Output: - a: sorted array in ascending order Process: 1) For i = 1 to a.length: a) Set element to a[i] and set j to i-1 b) While j >= 0 and a[j] > element: i) Set a[j+1] to a[j] ii) Decrement j by 1 c) Set a[j+1] to element 2) Return the sorted array ```
The Java code:

```public static int[] insertionSort(int[] a) {
for (int i = 1; i < a.length; i++) {
int element = a[i];
int j = i - 1;
while (j >= 0 && a[j] > element) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = element;
}
return a;
}
```

# The Selection Sort Algorithm

The selection sort algorithm has the worst case running time of O(n2) complexity. Given an array it scans from left to right to find the smallest number in the array. Once the algorithm is done scanning the entire array and the smallest number has been found, it is swapped into the first space. Then the scanning process starts over again, but this time from the second space. Once a new minimum has been found, that will be swapped into the second space. And so on.
This is a pseudo code:
``` Procedure: selectionSort(a) Inputs: - a: the array to sort Output: - a: the array in sorted ascending order Process: 1) For i = 0 to a.length: a) Set minimum to i b) For j = i + 1 to a.length. If a[j] < a[minimum], then set minimum to j c) Swap a[i] with a[minimum] 2) Return the sorted array ```
Code in Java

```public static int[] selectionSort(int a[]) {
for (int i = 0; i < a.length; i++) {
int minimum = i;
for (int j = i + 1; j < a.length; j++) {
if (a[j] < a[minimum]) minimum = j;
}
int temp = a[i];
a[i] = a[minimum];
a[minimum] = temp;
}
return a;
}
```

# The Binary Search Algorithm with Recursion

A loop in a binary search algorithm may be substitute with a recursion. This approach allows for more elegant code. The pseudo code looks like this:
``` Procedure: Recursive-Binary-Search(a,p,r,x) Inputs: - a: the array to search - x: the value we are searching for in a - p and r: represents indexes sub-array under consideration Output: - The index of an element matching x in the sub-array from a[i] - Through a[a.length], or -1 if x is not found in the array 1) If p > r then return -1 2) Else: a) Set q to [(p + r) / 2] b) If a[q] == x, than return q. c) else if a[q] > x, then return Recursive-Binary-Search(a,p,q-1,x) d) else return Recursive-Binary-Search(a,q+1,r,x) ```
The code in Java

```System.out.println(recursiveBinarySearch(new int[] {1,2,3,4,7,9,12,18}, 0, 7, 12));

public static int recursiveBinarySearch(int[] a, int p, int r, int x) {
if (p <= r) {
int q = (p + r) / 2;
if (a[q] == x) return q;
else if (a[q] > x) return recursiveBinarySearch(a, p, q-1, x);
else return recursiveBinarySearch(a, q+1, r, x);
}
return -1;
}
```

# The Linear Search Algorithm with Recursion

A loop in a linear search algorithm may be substitute with a recursion. This approach allows for more elegant code. The pseudo code looks like this:
``` Procedure: Recursive-Linear-Search(a,i,x) Inputs: - a: the array to search in - x: the value we are searching for in a - i: the index of an element in a Output: - The index of an element matching x in the sub-array from a[i] - Through a[a.length], or -1 if x is not found in the array 1) If i > the last element index, then return -1 2) Else if a[i] == x, then return i 3) Else return Recursive-Linear-Search(a, i + 1, x) ```
Java code:

```System.out.println(recursiveLinearSearch(a,0,x));

public static int recursiveLinearSearch(int[] a, int i, int x) {
if (i > a.length - 1) return -1;
else if (a[i] == x) return i;
else return recursiveLinearSearch(a, i + 1, x);
}
```

# The Binary Search Algorithm

The Binary Search algorithm is a bit more complex to code, but it is much more powerful and efficient than the linear search algorithm. Note that the binary search can be done only on a SORTED collection of data!
This is a pseudo code:
``` Procedure: Binary-Search(a,x) Inputs: a: a sorted array to search in x: the value we are searching for in a Outputs: The index position where a[i] == x or -1 if not found Let assume that array a has the following structure a[p...q...r] where p is the first index, r is the last index, and q is the index in the midpoint of the array. Process: 1) Set the first index p to value 0 and the last index to a.length - 1 2) While p is less or equal to r do a) set q to (p + r) / 2 and floor it to a whole number b) if a[q] = x, return the index position (q) c) if a[q] > x, set r to q - 1 else set p to q + 1 3) Return -1 if not found ```
Code in Java:

```public static int binarySearch(int[]a, int x) {
int p = 0;
int r = a.length - 1;
while (p <= r) {
int q = (p + r)/2;
if (a[q] == x) {
return q;
}
if (a[q] > x ) {
r = q - 1;
} else {
p = q + 1;
}
}
return -1;
}
```

Or a more elegant way to write it:

```
public static int binarySearchModified(int[]a, int x) {
int p = 0;
int r = a.length - 1;
while (p <= r) {
int q = (p + r)/2;
if (x < a[q]) r = q - 1;
else if (x > a[q]) p = q + 1;
else return q;
}
return -1;
}
```

# The Linear Search Algorithm

The linear search algorithm is one of the most simple algorithms. This is a pseudo code:
``` Procedure: Linear-Search(a,x) Inputs: a: the array to search in x: the value we are searching for in a Outputs: The index position where a[i] == x or -1 if not found Process: 1) Set result to -1 2) For each index i going from 1 to n, in order if a[i] = x, then set result to the value of i 3) Return the value of result as the output. ```
The code in Java:

```public static void main(String[] args) {
int[] a = {1,2,3,4,5};
int x = 5;
System.out.println(linearSearch(a, x));
}

public static int linearSearch(int[] a, int x) {
for (int i = 0; i < a.length; i++) {
if (a[i] == x) return i;
}
return -1;
}
```

# Stack and Reverse a String Algorithm

The Stack data structure allows for LIFO (last in – first out) functionality. We can use is it within complex structures where we need the order of items to be reversed.
One of a simple examples would be a string reverse method:

```public static void main(String[] args) {
String str = "system";
String result = App.reverseString(str);
System.out.println(result);
}

// Algorithm to reverse the string that is passed in as a parameter
public static String reverseString(String str) {
Stack stack = new Stack(str.length());
for (int i = 0; i < str.length(); i++) {
stack.push(str.charAt(i));
}
String result = "";
while (!stack.isEmpty()) {
result  += stack.pop();
}
return result;
}
```

The Stack class may look like this:

```public class Stack {

// Store the size of the stack
private int maxSize;

// Store list of items
private char[] stackArray;

// Index position of the last item on the top of the stack
private int top;

public Stack(int size) {
this.maxSize = size;
this.stackArray = new char[maxSize];
this.top = -1;
}

public void push(char j) {
if (isFull()) {
System.out.println(" this stack is already full");
} else {
top++;
stackArray[top] = j;
}
}

public char pop() {
if (isEmpty()) {
System.out.println(" this stack is already empty");
return 0;
} else {
int old_top = top;
top--;
return stackArray[old_top];
}
}

public long peak() {
return stackArray[top];
}

public boolean isEmpty() {
return (top == -1);
}

public boolean isFull() {
return (maxSize - 1 == top);
}
}
```

Of course, there would be a much simpler solution for such a basic operation as a string reverse, but the code above just illustrates the LIFO benefit.

```public static String reverseString(String str) {
String result = "";
for (int i = str.length() - 1; i >= 0; i--) {
result += str.charAt(i);
}
return result;
}
```