## Introduction to Sorting

In this section, we'll cover sorting. Before we get started, let's cover the base class and some sorting basics.

### Stable vs. Unstable

A sort that is stable means that order of elements with the same key are preserved.

For example, if I had a list of `{f, F, D, d, W, n, K, i}`

and I wanted to sort alphabetically (ignoring the cases) I would have `{D, d, f, F, i, n, K}`

. Since D and d, along with f and F have the same value in terms of precedence, the letter that appears before the other in the original list appears first in the sorted array.

### Sort class

All the lessons in the section will use code that inherits from the `Sort`

class. We could use generics to sort different types of objects (with respective `.equals()`

) methods, but we'll keep it simple and focus on the algorithmic parts.

```
/**
* Contains the functionalities of any class that is able to Sort an array of ints.
* @author Code Snipcademy
* @version 1.0.0 May 16, 2015.
*/
public class Sort {
/**
* Swap two elements in our int array.
* @param index1 First index
* @param index2 Second index
*/
public static void swap(int[] inputArray, int index1, int index2) {
int temp;
temp = inputArray[index1];
inputArray[index1] = inputArray[index2];
inputArray[index2] = temp;
}
}
```

## Selection Sort

### Algorithm Pseudocode

- Start at beginning of the array, where index
`i = 0`. - Move through
`i`to`N`where`N`is the length of the array. - Select the min
- Swap the min with
`i`. - Increment
`i`and loop.

### Visualization

This visualization makes it seem like selection sorting is fast, but in reality, this algorithm iterates through all elements (gray bars) to select the smallest value.

### Characteristics

Selection sort is not stable.

Having a runtime of always quadratic, selection sort may present itself as not the best sorting algorithm. However, this algorithm could be useful if the cost of swapping items is high.

### Complexity

`O(n ^{2})` comparisons,

`O(n)`swaps

### Implementation in Java

Here's a sample implementation written in Java. Note that it extends the Sort.java class.

```
import java.util.Arrays;
public class SelectionSort extends Sort {
public static void main(String[] args) {
int[] testInt = {1,6,2,3,6,7,4,2,5};
selectionSort(testInt);
System.out.println(Arrays.toString(testInt));
}
public static void selectionSort(int[] input) {
for (int i = 0; i < input.length; i++) {
int minIndex = i;
int min = input[i];
// Iterate through array to find minimal value
for (int j = i; j < input.length; j++) {
if (input[j] < min) {
// Replace with new min if new min found
minIndex = j;
min = input[j];
}
}
// Swap with index at start of search
swap(input, minIndex, i);
}
}
}
```

## Bubble Sort

### Algorithm Pseudocode

- Start at the outer loop,
`i = 0`. - Within the inner loop, compare each two consecutive values.
- If the value of the right cell has a key index lower than that of the left cell, swap.
- Repeat inner/outer loops until smaller values bubble to the top.
- *If no swaps occur in one entire inner loop, list is already sorted and you're done.

### Visualization

Here's a good visualization as to what's exactly happening.

### Complexity

Time: `O(n ^{2})` but

`O(n)`when nearly sorted.

Space: `O(1)`

### Characteristics

Bubble sort is a stable sorting algorithm.

Bubble sort has a high overhead. In the case where the given input is reversed, the algorithm will take `O(n ^{2})` time.

### Implementation in Java

Here's a sample implementation written in Java. Note that it extends the Sort.java class.

```
import java.util.Arrays;
public class BubbleSort extends Sort {
public static void main(String[] args) {
int[] testInt = {1,6,2,3,6,7,4,2,5};
bubbleSort(testInt);
System.out.println(Arrays.toString(testInt));
}
public static void bubbleSort(int[] testInt) {
/**
* If flag keeps false, then no swaps occurred, meaning
* our list is already sorted
*/
boolean flag;
do {
flag = false;
for (int j = 0; j < testInt.length-1; j++) {
if (testInt[j+1] < testInt[j]) {
swap(testInt, j, j+1);
flag = true;
}
}
} while (flag);
}
```

## Insertion Sort

### Algorithm Pseudocode

- Partition the array into two subarrays - the first value will be the "sorted" array, and the others will be in an "unsorted" array.
- Take the first value
`x`in the unsorted array and store into a`temp`

. - Moving down the list in the sorted array, shift over every element greater than
`x`. - Insert
`x`and repeat.

### Visualization

Here's a nifty animation for your better learning.

### Characteristics

Insertion sort is the best choice when data is nearly sorted or the problem size is small. Thus, it's a good choice for higher divide-and-conquer sorting algorithms such as merge sort and quick sort.

Furthermore, it is considered to have low overhead since it avoids executing unneccesary lines of code.

Insert sort is stable sorting algorithm.

### Complexity

If our array is already sorted, only `n-1` comparisons are used. In the worst case, `n(n-1)/2` comparisons are used.
Time: `O(n ^{2})` Space:

`O(1)`

### Implementation in Java

Here's a sample implementation written in Java. Note that it extends the Sort.java class.

```
import java.util.Arrays;
public class InsertionSort extends Sort {
public static void main(String[] args) {
int[] testInt = {1,6,2,3,6,7,4,2,5};
insertionSort(testInt);
System.out.println(Arrays.toString(testInt));
}
public static void insertionSort(int[] test) {
/**
* The array will be partitioned to two subarrays - the sorted
* and unsorted. The first element will be in our sorted subarray.
*/
for (int i = 1; i < test.length; i++) {
// Store the element to insert
int temp = test[i];
/**
* For every element in our sorted subarray that is greater
* than the temp, shift elements over one.
*/
for (int j = i-1; j >= 0; j--) {
if (temp < test[j]) {
test[j+1] = test[j];
} else {
test[j+1] = temp;
break;
}
}
}
}
}
```

## Quick Sort

Quick sort is a divide-and-conquer algorithm developed by Tony Hoare in 1959. Let's look at how Quick Sort works.

### Algorithm Pseudocode

- Assign the last element as a pivot.
- Place a line to partition the array into two, starting from the far left end of the array.
- For each element in our array that is less than or equal to the pivot, swap it with the element to the right of the wall and move wall up one.
- Place pivot as the first element on the right of the partitioning wall.
- Split and repeat, then merge together for sorted array.

Here's a step-by-step illustration of what is going on. Try writing down the array [8, 4, 7, 2, 9, 5] and running through Quick Sort yourself.

### Visualization

Here's a nifty animation for your better learning experience.

### Characteristics

Quick sort is said to be similar to insertion and bubble, but more efficient in most cases. Depending on the implementation, it may or may not be a stable sort.

#### Complexity

`O(n ^{2})` at worst case, and

`O(n log n)`on average.

`O(n)`space for recursion stack.

### Implementation in Java

Here's a sample implementation written in Java. Note that it extends the Sort.java class.

```
import java.util.Arrays;
public class QuickSort extends Sort {
public static void main(String[] args) {
int[] testInt = {1,6,2,3,6,7,4,2,5};
quickSort(testInt, 0, testInt.length-1);
System.out.println(Arrays.toString(testInt));
}
public static void quickSort(int[] input, int low, int high) {
// Base case
if (low >= high) {
return;
}
// Use last element as pivot
int pivot = input[high];
// Set our wall at the first element
int wall = low;
/**
* Iterate through array - if current element is less that or equal
* to pivot, swap with element above wall
*/
for (int i = low; i < high; i++) {
if (input[i] <= pivot) {
swap(input, i, wall++);
}
}
// Place pivot to right to just right of wall
swap(input, wall, high);
// Recursively call for each part of array
quickSort(input, low, wall-1);
quickSort(input, wall, high);
}
}
```