Suppose you are given a list of n distinct elements. You are asked to sort this...

   

Transcribed Image Text:

Suppose you are given a list of n distinct elements. You are asked to sort this list in descending order (from greatest to smallest) using Insertion Sort algorithm: The informal description of InsertionSort (n): Let pointer be the pointer which splits the list into two parts: everything on the left including the pointer will be sorted and everything on the right is unsorted. We start with pointer 1. Then we repeat the following steps until the pointer becomes n take the first element to the right of the pointer, find an appropriate position in the ordered part of the list where it can be inserted so that the ordered part remains ordered. The move the element to this position; increase pointer by 1. = (a) Based on the informal description of Insertion Sort (n) (see above) design a step-by- step algorithm which can easily be turned into a code. (You do not have to follow the official version of Insertion Sort.) (b) Find the running time of your algorithm. An elementary operation here is either a data move or a comparison. Suppose you are given a list of n distinct elements. You are asked to sort this list in descending order (from greatest to smallest) using Insertion Sort algorithm: The informal description of InsertionSort (n): Let pointer be the pointer which splits the list into two parts: everything on the left including the pointer will be sorted and everything on the right is unsorted. We start with pointer 1. Then we repeat the following steps until the pointer becomes n take the first element to the right of the pointer, find an appropriate position in the ordered part of the list where it can be inserted so that the ordered part remains ordered. The move the element to this position; increase pointer by 1. = (a) Based on the informal description of Insertion Sort (n) (see above) design a step-by- step algorithm which can easily be turned into a code. (You do not have to follow the official version of Insertion Sort.) (b) Find the running time of your algorithm. An elementary operation here is either a data move or a comparison.

Answer rating: 100% (QA)

a Algorithm for Insertion Sort 1 Start with pointer 1 2 Repeat the following steps until the pointer ... View the full answer