# Sorting Lab Your task is to complete the sorting algorithms in the Sort class. The insSort should implement the insertion sort algorithm. This will sort from least to gratest “in-place”. The algorithm

Sorting Lab

Your task is to complete the sorting algorithms in the Sort class.

The insSort should implement the insertion sort algorithm. This will sort from least to gratest

“in-place”. The algorithm is as follows. Consider the array as two separate arrays where the left

hand side (index 0 to index i) is sorted and the right hand side (index i+1 to index arr.length-1) is

unsorted. Starting with position n=1, keep searching while the element is less than the element

to the left in the array and swap positions until the element to the left is less than the element

being inserted. Example:

12 4 13 5 8 2 6 would start with element “4” and swap with 12, to give

4 12 13 5 8 2 6, then element 13 would be considered, but since 13 > 12, no swap is made, then

element 5 is considered. 5 < 13, so 5 and 13 are swapped. 5 < 12 so 5 and 12 are swapped. 5 > 4,

so we are done. This continues util we look at the last element. The bTest should be placed after

the inner loop, but before the outer loop completes.

Passes:

4 12 13 5 8 2 6

4 12 13 5 8 2 6

4 5 12 13 8 2 6

4 5 8 12 13 2 6

2 4 5 8 12 13 6

2 4 5 6 8 12 13

For sel sort, you should start at element 0, find the smallest element in the array and swap with

element 0, then go to element 1, find the smallest value in the rest of the array, and swap and so

on. The bTest should be placed after the inner loop, but before the outer loop completes.

Passes:

2 4 13 5 8 12 6

2 4 13 5 8 12 6

2 4 5 13 8 12 6

2 4 5 6 8 12 13

2 4 5 6 8 12 13

2 4 5 6 8 12 13

2 4 5 6 8 12 13

For merge sort, you need to recursively create separate left and right arrays from an array. The

base case is if n < 2. Otherwise find the middle of the array (n/2) the left array is 0 to n/2 -1 in

the passed in array and the right array is from n/2 to n-1. Recursive call the merge on the left

array (length n/2) and the right array (length n – n/2). The merge the left and right arrays into the

passed in array. The bTest should be placed at the end of the merge.

4 13

4 12 13

5 8

2 6

2 5 6 8

2 4 5 6 8 12 13

public class Sort

{

private int[] arr;

private boolean bTest;

private String result;

public Sort(int num)

{

result = “”;

bTest = false;

arr = new int[num];

for(int i = 0; i < num; i++)

arr[i] = (int)(Math.random() * 1000000);

}

public Sort(int[] a)

{

result=””;

bTest = true;

arr=a;

}

public int[] getArray()

{

return arr;

}

public void insSort()

{

if(bTest)

printArr(arr);

}

public void selSort()

{

if(bTest)

printArr(arr);

}

public void merge(

int[] a, int[] l, int[] r, int left, int right) {

if(bTest)

printArr(a);

}

public void mergeSort(int[] a, int n)

{

}

public String getResult()

{

return result;

}

public void printArr(int[] a)

{

for(int i = 0; i < a.length; i++)

result = result + (a[i] + ” “);

}

} 