sorting algorithms
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()
{
//Your Code Here
if(bTest)
printArr(arr);
}
public void selSort()
{
// Your Code Here
if(bTest)
printArr(arr);
}
public void merge(
int[] a, int[] l, int[] r, int left, int right) {
//Your Code Here
if(bTest)
printArr(a);
}
public void mergeSort(int[] a, int n)
{
//Your Code Here
}
public String getResult()
{
return result;
}
public void printArr(int[] a)
{
for(int i = 0; i < a.length; i++)
result = result + (a[i] + ” “);
}
}