## What is Sorting?

Sorting is the process of placing objects in a logical order. For instance, we could place numbers in an increasing or decreasing order. This topic by itself is huge. There are entire textbooks written on the subject of sorting numbers! There are also many different sorting methods. Just check out the Wikipedia page!

Sorting algorithms were a big deal back in the 50s and 60s when computers started becoming the processing machines they are today. When data was stored on very slow tape drives, you wanted to be sure to have an efficient way of putting data in order. This would make searching for data much faster. It was also popular due to its simplistic problem definition but involved a great deal of complexity creating a good sorting algorithm. As far as most people are concerned, the problem of sorting has already been solved. That is, we already have algorithms that are the best and we can do no better.However, we are still finding new algorithms that can speed up sorting in specific applications. Below you will see 4 different sorting algorithms: Selection Sort, Bubble Sort, Insertion Sort, and Merge Sort. You will be responsible for knowing the first 3. I have included a description, the java code , and a video that demonstrates each sorting algorithm :)

Sorting algorithms were a big deal back in the 50s and 60s when computers started becoming the processing machines they are today. When data was stored on very slow tape drives, you wanted to be sure to have an efficient way of putting data in order. This would make searching for data much faster. It was also popular due to its simplistic problem definition but involved a great deal of complexity creating a good sorting algorithm. As far as most people are concerned, the problem of sorting has already been solved. That is, we already have algorithms that are the best and we can do no better.However, we are still finding new algorithms that can speed up sorting in specific applications. Below you will see 4 different sorting algorithms: Selection Sort, Bubble Sort, Insertion Sort, and Merge Sort. You will be responsible for knowing the first 3. I have included a description, the java code , and a video that demonstrates each sorting algorithm :)

## Why Study Sorting?

Sorting may seem like a boring thing to look at but it is critical for many applications. It is so important, in fact, that it is considered a fundamental process in computer science. Without being able to sort something, many other problems would be very difficult to accomplish. Also, many sorting algorithm employ a technique that can be applied to solve other problems. For instance, merge sort using a divide and conquer algorithm which can be used to solve other problems.

## Sort 1: Selection Sort

Selection sort is probably the most intuitive sorting algorithm that anyone can think of. Essentially, we look for the smallest (or largest depending on which way you want to sort), and place it in the correct position. Then we repeat this process until we have reached the end of our numbers to sort. This is not a very efficient algorithm, but it is very easy to code.

```
public void selectionSort(int[] n){
// start at the first element and go up to the second from the end element
for(int i = 0; i < n.length - 1; i++){
// keep track of the smallest element's position
int minPos = i;
// start at the next position in the array and go through the remaining items
for(int j = i + 1; j < n.length; j++){
// if the current element is smaller than the minimum I have found, keep track of it instead
if(n[j] < n[minPos]){
minPos = j;
}
}
// swap the smallest element into its proper position
int temp = n[i];
n[i] = n[minPos];
n[minPos] = temp;
}
}
```

## Sort 2: Bubble Sort

This is basically the algorithm that your wrote in grade 11 when you learned about arrays. It is actually a worse algorithm than selection sort but it is very easy to understand and code. The idea is that we compare 2 adjacent items and move the bigger one down the list. We continue to do this until we reach the end. Once we reach the end, we start over again. We stop sorting once we have made a swap.

```
public void bubbleSort(int[] n){
boolean swapped = false;
do{
swapped = false;
for(int i = 0; i < end; i++){
if(n[i] > n[i+1]){
int temp = n[i];
n[i] = n[i+1];
n[i+1] = temp;
swapped = true;
}
}
}while(swapped);
}
```

While this isn't the exact implementation that is normally shown (I am always going through the complete array), it is still working in the spirit of bubble sort. There are some improvements that can be made but it doesn't make up a lot of issues with this sorting.

## Sort 3: Insertion Sort

This is the final simple sorting algorithm that you will need to know for this course in detail. Insertion sort sorts the array one number at a time. It essentially picks up the number and shuffles it down the array until it finds the appropriate spot in the array. It may not seem like this would be an improvement over the other sorting methods but it is actually pretty efficient with smaller groups of numbers. In fact, some of the built in sorting algorithms in some of the programming languages use a form of insertion sort for smaller groups of numbers. There is also a 3 line version of this algorithm written in C with a 5 line optimized version.

```
public void insertionSort(int[] n){
for(int i = 1; i < n.length; i++)
{
int j = i;
while(j>0 && n[j-1] > n[j])
{
int temp = n[j];
n[j] = n[j-1];
n[j-1] = temp;
j--;
}
}
}
```

## Bonus Sort: Merge Sort

By utilizing the recursion that we did in the previous unit, we can develop a new type of sorting algorithm, known as divide and conquer algorithms. The idea behind merge sort is that we can take an array and divide it in half to sort each section separately. By doing this, we have made the problem easier to solve and it can also be given to multiple computers to solve at the same time. We continue to do this dividing until we reach a simple case. Once this happens, we begin merging the results together (hence the name merge sort)

```
public static void mergeSort(int[] a) {
if(a.length <= 1)
{
return;
}
// find the middle
int middle = (a.length) / 2;
// break the array into 2 parts
int[] left = new int[middle];
for(int i = 0; i < left.length; i++){
left[i] = a[i];
}
int[] right = new int[a.length - middle];
for(int i = 0; i < right.length; i++){
right[i] = a[i+middle];
}
//call mergeSort on first half
mergeSort(left);
//call mergeSort on second half
mergeSort(right);
//merge the results
int leftPos = 0;
int rightPos = 0;
for(int i = 0; i < a.length; i++){
// if only leftmost items left
if(rightPos >= right.length && leftPos < left.length)
{
a[i] = left[leftPos];
leftPos++;
// only rightmost items left
}else if(leftPos >= left.length && rightPos < right.length)
{
a[i] = right[rightPos];
rightPos++;
// left item is next in line
}else if(left[leftPos] < right[rightPos]){
a[i] = left[leftPos];
leftPos++;
// right item is next in line
}else{
a[i] = right[rightPos];
rightPos++;
}
}
}
```