Im really confused with this and i need help. Part 1. Insertion Sort The task: T
ID: 669735 • Letter: I
Question
Im really confused with this and i need help.
Part 1. Insertion Sort
The task:
Take the "insert" logic you developed for HW02, and use it to sort an entire array.
That is:
- start with an array with unordered data
- run your insertionSort function
- print out the array which now should be ordered.
Hint:
If you're feeling lost -- how to get started? -- this might help.
- declare and allocate two arrays, say "a" and "b".
- fill up "b" with unordered data
- start with nothing in "a". nElemsA is zero -- no elements there yet.
- now insert the values from "b" into "a" using the ordered insert.
insert(b[0]); // into a
insert(b[1]); // into a
and so on. (maybe we want a loop here??)
(question: does it matter if I do it this way or backwards?)
insert(b[b.size-1]);
insert(b{b.size-2]);
Remember to print out a lot of stuff while you're figuring out the program.
So, to continue with the hint:
Look at the situation when you've inserted, say, 3 values into the new array.
What is the value of nElems? (ans: 3, i.e., pointing to the 4th cell)
When you do the next insertion, a[3] might get moved to a[4] ... but no one will touch a[5] or any greater values.
In the original array, say it's called b, b[0] through b[3] have already been placed and will not be looked at again.
Explanation / Answer
/**Java program that demonstrates the insertion sort algorithm to sort unsorted elements into
* sorted in ascending order*/
//InsertionSortProgram.java
public class InsertionSortProgram
{
public static void main(String[] args)
{
//array of un-sorted elements
int[] unsorted=new int[9];
//insert elements into array
unsorted[0]=9;
unsorted[1]=5;
unsorted[2]=4;
unsorted[3]=2;
unsorted[4]=3;
unsorted[5]=10;
unsorted[6]=15;
unsorted[7]=7;
unsorted[8]=1;
System.out.println("BEFORE SORTING");
System.out.println("ARRAY ELEMENTS : ");
print(unsorted);
System.out.println("SELECTION SORT");
//calling the method insertionSort method
int[] sorted=insertionSort(unsorted);
System.out.println("AFTER SORTING");
System.out.println("ARRAY ELEMENTS : ");
//print sorted elements
print(sorted);
}
/**The method insertionSort that takes the elements
* and sorts the elements in ascending order*/
public static int[] insertionSort(int elements[])
{
//loop through the array elements and sort the elements
for (int index = 1; index < elements.length; index++)
{
//get element at index position
int current = elements[index];
//set index position to pos
int pos = index;
/*compare the starting element,pos-1 with the next element at current
If starting element is greater than current then
move the startig element to right side by pos value until pos is greater than
zero.*/
while ( (pos > 0) && ( elements [pos-1] > current ) )
{
elements [pos] = elements [pos-1];
pos=pos-1;
}
//Now set the current element into its sorted position in the list.
elements[pos] = current;
}
//returns the sorted list
return elements;
}
//Print the elements in the array
private static void print(int[] array)
{
for (int element : array)
System.out.println(element+" ");
System.out.println();
}
}
--------------------------------------------------------------------------------------------------------------------
Sample Output:
BEFORE SORTING
ARRAY ELEMENTS :
9
5
4
2
3
10
15
7
1
SELECTION SORT
AFTER SORTING
ARRAY ELEMENTS :
1
2
3
4
5
7
9
10
15
Hope this helps you