Question

In: Computer Science

Part 2: Insertion Sort Q3. Arrange the following arrays in ascending order using Insertion sort. Show...

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

Solutions

Expert Solution

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


Related Solutions

Sorting – Insertion Sort Sort the list 0, 3, -10,-2,10,-2 using insertion sort, ascending. Show the...
Sorting – Insertion Sort Sort the list 0, 3, -10,-2,10,-2 using insertion sort, ascending. Show the list after each outer loop. Do his manually, i.e. step through the algorithm yourself without a computer. This question is related to data structure and algorithm in javascript (.js). Please give your answer keeping this in your mind.
Sort the following set of numbers using bubble sort, insertion sort, and selection sort. Show the...
Sort the following set of numbers using bubble sort, insertion sort, and selection sort. Show the process step-by-step, and find the time complexity in Big-O notation for each method. For sorting, use ascending order. 49, 7, 60, 44, 18, 105
1a .Write a program that perform insertion sort (ascending order) on an input array and print...
1a .Write a program that perform insertion sort (ascending order) on an input array and print the total number of comparisons that have been made. You can implement by using any programming languages such as C/C++. For example, in the case of array B = [ 30 , 10 , 20 , 40 ], there are 4 needed comparisons to perform insertion sort (30 vs 10, 20 vs 30, 20 vs 10, and 40 vs 30). 1b. Write a program...
// This program uses a bubble sort to arrange an array of integers in // ascending...
// This program uses a bubble sort to arrange an array of integers in // ascending order (smallest to largest). It then display the array // before the sorting and after the sorting. Modify the program so it orders // integers in descending order (largest to smallest). Then add some code // to display the array at each step of the algorithm. You don't have to // modify anything in the main() function. All modification are inside // the bubbleSortArray()...
1) Use insertion sort to sort: 25, 17, 31, 13, 2. Show your work step-by-step. 2)...
1) Use insertion sort to sort: 25, 17, 31, 13, 2. Show your work step-by-step. 2) Use Euclidean algorithm to find gcd(248, 198) 3) (ABCDEF)16 to binary, octal and decimal
Write a program in Java to sort the given array using merge sort, quick sort, insertion...
Write a program in Java to sort the given array using merge sort, quick sort, insertion sort, selection sort and bubble sort based on the input from the user which sorting technique they wanted to use. Get the array size, array elements from the user, and also display the sorted array along with the name of the sorting technique used.
2 real-time examples on the Insertion sort, Bubble sort, Selection sort, Quick sort, Shell sort, Merge...
2 real-time examples on the Insertion sort, Bubble sort, Selection sort, Quick sort, Shell sort, Merge sort, Radix sort, Bucket sort, and Counting sort.
come up with at least 2 real-time examples on the Insertion sort, Bubble sort, Selection sort,...
come up with at least 2 real-time examples on the Insertion sort, Bubble sort, Selection sort, Quick sort, Shell sort, Merge sort, Radix sort, Bucket sort, and Counting sort.
come up with at least 2 real-time examples on the Insertion sort, Bubble sort, Selection sort,...
come up with at least 2 real-time examples on the Insertion sort, Bubble sort, Selection sort, Quick sort, Shell sort, Merge sort, Radix sort, Bucket sort, and Counting sort.
out of the following four: 1.Bubble sort 2. Insertion sort 3. Quicksort 4. Mergesort a. Which...
out of the following four: 1.Bubble sort 2. Insertion sort 3. Quicksort 4. Mergesort a. Which sorting methods perform best and worst for data sizes ≥ 25,000 when the input data is random? b. Which sorting methods perform best and worst for data sizes ≥ 25,000 when the input data is 90% sorted? c. Which sorting methods perform best and worst for data sizes ≥ 25,000 when the input data is reverse sorted? d. Which sorting methods perform best and...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT