Question

using java

Which sorting algorithm is this, justify in detail your answer?

image of code in this link

https://lh3.googleusercontent.com/ie0xsSduZTDJ0PYd3skj43dNApdae1rKAXt1OIdkUE9WAyIrrzLndH2pbsVs_laCJ91H61wxBRopgHPcF8PayLjWHiW-Pn72ti02xxb0aNpx87tFUbT7j8lW0bL4=w655

Answer 1

The algorithm that is used in the attached picture is Insertion Sort and It is implemented as it will sort the data in decreasing order.

Insertion sort is a simple technique to sort the array, this algorithm splits the array (unsorted) into two parts sorted part and unsorted part and after each pass, the length of the sorted part array gets increased by 1 and the unsorted part gets decreased by 1 at the same time so after the n-1 pass, we get all the array sorted.

More specifically, for an i^th pass ( for sorting in descending order as in the pic) the algorithm checks for an element that has the index lesser than (i-1) and value less than the value at i^th index element (key). If such an element is found then it stores that element at the next index of that element (space is created ) and continues checking until the condition gets false., when all such elements get checked then this key(i.e, the element at the i^th position) gets placed at that empty space created, in this way all the smaller elements than key element gets the index greater than key element. So basically in each pass it picks a key element and inserts it at such index so that all the elements have index lesser than it has the value greater. That's why it is called Insertion sort, it inserts the key element in each pass.

For example:

Let's assume an array is to be sorted in descending order with this algorithm is

Arr

2

7

1

9

5

6

Let's see how this gets sorted by the same algorithm, there are 6 numbers so there will be 5(starting with 2nd element as the first element has no index lesser than it) passes, we will see the result of each pass one by one.

In pass 1: key = 7 (1^st index element)

so after pass 1:

Arr

7

2

1

9

5

6

Element 2 and 7 got swapped as element 2 has the lesser index than key and its value is also less than key.

In pass 2: key = 1 (2^nd index element)

so after pass 2:

Arr

7

2

1

9

5

6

No change as there is no such element that has a lower index with a lower value.

In pass 3: key = 9 ( 3^rd index element)

so after pass 3:

Arr

9

7

2

1

5

6

The key element is the largest among all its lower index's element so it gets the first position, and all shifted by 1.

In pass 4: key = 5 (4^th index element)

so after pass 4:

Arr

9

7

5

2

1

6

There are two elements 1 and 2 which has a lower index and value than the key element, so both get shifted by 1, and the key element takes the empty space created.

In pass 5: key = 6 (5^th index element)

so after pass 5:

Arr

9

7

6

5

2

1

There are three elements 1 and 2 and 5 which have a lower index and value than the key element, so all get shifted by 1, and the key element takes the empty space created.

Now we can see that the array is now sorted in descending order.

NOTE: In case of any query, you can mention in the comment section. HAPPY LEARNING!!