How do I do the insertItem(2nd part) using partialSortArr[] and indexToInsertLef
ID: 3755835 • Letter: H
Question
How do I do the insertItem(2nd part) using partialSortArr[] and indexToInsertLeft? For this Insertion Sort?
public class InsertionSort {
/**
* Sort integers in ASCENDING order (-1, 20, 314 ...)
* using INSERTION sort algorithm
*/
public static int[] sort(int[] unsorted) {
// DO THIS PART THIRD
return unsorted;
}
/**
* Insert the value at indexToInsertLeft into the partially-sorted array up to indexToInsertLeft.
*
* For example:
* If the array is: [-1, 2, 12, 20, |7|, 8, -1] and indexToInsertLeft is 4
* Then the resulting array should be:
* [-1, 2, |7|, 12, 20, 8, -1]
*
* Note that all elements after indexToInsertLeft must remain unchanged.
* You may assume that all elements up until indexToInsertLeft are already sorted.
*/
public static void insertItem(int[] partialSortedArr, int indexToInsertLeft) {
// DO THIS PART SECOND need help with this!
}
/**
* Swap the elements at index1 and index2 in the array.
*/
public static void swap(int[] arr, int index1, int index2) {
int tmp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = tmp;
}
}
Explanation / Answer
public class InsertionSort {
/**
* Swap the elements at index1 and index2 in the array.
*/
public static void swap(int[] arr, int index1, int index2) {
int tmp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = tmp;
}
/**
* Sort integers in ASCENDING order (-1, 20, 314 ...)
* using INSERTION sort algorithm
*/
/**
* Insert the value at indexToInsertLeft into the partially-sorted array up to indexToInsertLeft.
*
* For example:
* If the array is: [-1, 2, 12, 20, |7|, 8, -1] and indexToInsertLeft is 4
* Then the resulting array should be:
* [-1, 2, |7|, 12, 20, 8, -1]
*
* Note that all elements after indexToInsertLeft must remain unchanged.
* You may assume that all elements up until indexToInsertLeft are already sorted.
*/
public static void insertItem(int[] partialSortedArr, int indexToInsertLeft) {
// DO THIS PART SECOND need help with this!
int j = indexToInsertLeft;;
while(0<j)
{
if(partialSortedArr[j]<partialSortedArr[j-1])
{
//calling method to swap
swap(partialSortedArr,j,j-1);
}
j--;
}
}
public static int[] sort(int[] unsorted) {
int j = 1;
while(j<unsorted.length)
{
insertItem(unsorted,j);
j++;
}
// DO THIS PART THIRD
return unsorted;
}
//method to print array
void print(int a[])
{
int i=0;
System.out.print("List:");
while(i<a.length)
System.out.print(a[i++]+" ");
}
//method to test
public static void main(String argv[])
{
int [] a = {3,2,8,5,6,3,4,6};
InsertionSort n = new InsertionSort ();
System.out.println("Before sorting:");
n.print(a);
n.sort(a);
System.out.println(" After sorting:");
n.print(a);
System.out.println("");
}
}
output:
run:
Before sorting:
List:3 2 8 5 6 3 4 6
After sorting:
List:2 3 3 4 5 6 6 8
BUILD SUCCESSFUL (total time: 0 seconds)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.