Algorithm Notes
Here's a collection of my notes while attempting to implement some of these solutions myself. I've noted where I was tripped up along the way, and hopefully using these tips, I'll be better prepared to recognize the patters that work.
MergeSort Implementation
First off, understand how it works. A temp array will hold your data as you scan two other arrays to build them up. See this video for more on that. Recursivly splitting an array is a pattern that pops up from time to time and can be useful for many problems. Notice mid + 1 below. The left side is larger on arrays with uneven numbers.
public void sort(int[] arr) {
mergeSort(arr, 0, arr.length-1);
}
private void mergeSort(int[] arr, int start, int end) {
if ( start == end) {
return;
}
int mid = ( end - start ) / 2;
mid = start + mid;
mergeSort(arr, start, mid);
mergeSort(arr, mid + 1, end);
sortThem(arr, start, end);
}
From here I was struggling to do a true mergesort and figured I'd just finish it out with a bubble sort. This is was inefficient, but a good building block to solve with.
private void sortThem(int[] arr, int start, int end) {
int runner = start;
int[] temp = new int[(end - start) + 1];
for ( int i = start; i <= end; i++ ) {
int smallest = arr[i];
int position = i;
for ( int x = i; x <=end; x++ ) {
if ( arr[x] < smallest ) {
smallest = arr[x];
position = x;
}
}
int temper = arr[position];
arr[position] = arr[i];
arr[i] = temper;
}
}
Output
[33, 23, 54, 13, 84, 23, 87, 42, 39, 84] [13, 23, 23, 33, 39, 42, 54, 84, 84, 87]
Attempt two
Building off the attempt before at this point was much easier. Basically implement the temp array as needed and copy in. I think the loop at the bottom to add the remaining onto the temp is easier to read.
private int[] mergeSort(int[] arr, int start, int end) {
if ( start == end) {
return new int[];
}
int mid = ( end - start ) / 2;
mid = start + mid;
int[] left = mergeSort(arr, start, mid);
int[] right = mergeSort(arr, mid + 1, end);
return sortThem(left, right);
}
private int[] sortThem(int[] left, int[] right) {
int[] temp = new int[left.length + right.length];
int ls = 0;
int rs = 0;
int runner = 0;
while ( ls < left.length && rs < right.length ) {
if ( left[ls] < right[rs] ) {
temp[runner] = left[ls];
ls++;
}
else {
temp[runner] = right[rs];
rs++;
}
runner++;
}
//throw what's remaining of left or right array onto temp
while (runner < temp.length) {
if ( ls < left.length ) {
temp[runner] = left[ls];
ls++;
}
else {
temp[runner] = right[rs];
rs++;
}
runner++;
}
return temp;
}