In: Computer Science
Part 2: Insertion Sort
Q3. Arrange the following arrays in ascending order using Insertion sort. Show all steps.
7 11 2 9 5 14
Q4. State the number of comparisons for each pass.
Pass |
# comparisons |
1st |
|
2nd |
|
3rd |
|
4th |
|
5th |
Q3:
Given array: 7 11 2 9 5 14
Algorithm to sort an array in ascending order using
Insertion sort.
To sort an array of size k in ascending order:
1: Iterate from arr[1] to arr[k] over the array.
2: Compare the current element (key) to its previous element.
3: If the key element is smaller than its previous element, compare
it to the elements before. Move the greater elements one position
up to make space for the swapped element.
Array before sorting: 7 11 2 9 5 14
Step 1: let us loop from index=1(Second element) to index=4(Last element)
Step 2: Now compare the element at index=1(11) with the element at index=0(7).
Since 7 is smaller than 11 so the elements are not swapped
So the elements remain the same: 7 11 2 9 5 14
comparison=1
Step 3: Now compare the element at index=2(2) with the element at index=1(11) and index=0(7).
Since 2 is smaller than 11 and 7 so the element 2 is moved to index=0
Now the elements are: 2 7 11 9 5 14
comparison=2
Step 4: Now compare the element at index=3(9) with the element at index=2(11),
index=1(7) and index=0(2).
Since 9 is smaller than 11. so 9 and 11 are swapped
Now the elements are: 2 7 9 11 5 14
comparison=3
Step 4: Now compare the element at index=4(5) with the element at index=3(11),
index=2(9), index=1(7) and index=0(2).
Since 5 is smaller than 11,9 and 5 so the element 2 is moved to index=1
Now the elements are:2 5 7 9 11 14
comparison=4
Step 5: Now compare the element at index=5(14) with the element at index=4(11),
index=3(9),index=2(7), index=1(5) and index=0(2).
Since 14 is greater than 11,9,7,5 and 2
No elements are changed.
Now the elements are:2 5 7 9 11 14
The ArrayList is now sorted in ascending order using Insertion sort.
comparison=5
Code in java:
public class MyClass{
public static void main(String args[]) {
int lst[]=new int[]{7,11,2,9,5,14};
System.out.println("The Arraylist before sorting: ");
for (int i=0;i<lst.length;i++){
System.out.print(lst[i] + " ");
}
for (int i=1;i<lst.length;++i){
int keyValue = lst[i];
int j = i - 1;
while (j>=0 && lst[j]>keyValue) {
lst[j + 1]=lst[j];
j=j-1;
}
lst[j+1]=keyValue;
}
System.out.println("\nThe Arraylist after sorting: ");
for (int i=0;i<lst.length;i++){
System.out.print(lst[i] + " ");
}
}
}
Q4:
Pass #Comparisons
1st 1
2nd 2
3rd 3
4th 4
5th 5