5. Suppose we are sorting an array using one of the specified sorting algorithms

Question

5. Suppose we are sorting an array using one of the specified sorting algorithms. After 4 iterations, the array elements are ordered as: 2 4 5 7 8 1 3 6. Briefly explain your reason for choosing it?   

a) Insertion sort b) Selection sort c) Bubble Sort d) none of a, b and c

7. Consider the following list of integers: [1,2,3,4,5,6]. Show how this list is sorted by the following algorithms:
Explain how steps each sorting algorithm would take?
bubble sort
selection sort
insertion sort
merge sort
quick sort (you decide on the pivot value)

Explanation / Answer

5) The sorting algorithm specified for sorting of given set of arrays is Insertion Sort.

Explanation:

Insertion sort, works on the concept that, a key is to be selected and then inserted at the right place it should be in according to the particular iteration, that is

Consider the array as, 8 7 5 4 2 1 3 6

Now, according to insertion sort first element will be the key, that is

key = 8,

now compare key with all other elements and move all elements greater then the key, one position ahead in the array and insert the first smaller element then key in the place of key, that is after first iteration

7 8 5 4 2 1 3 6

now,

key = 7

after 2nd iteration

5 7 8 4 2 1 3 6

now, key = 4

after third iteration

4 5 7 8 2 1 3 6

now key = 2

after fourth iteration

2 4 5 7 8 1 3 6

for selection sort and bubble sort, after first iteration '1', will find it's place in the array as smallest element of the array.

7)Bubble sort:

Bubble sort works with the idea of comparing the adjacent elements at a time and then deciding upon to swap the same or not, that is

for given array:

[1, 2, 3, 4, 5, 6]

compare element[0] and element[1], that is 1 and 2, since 1 is already smaller then 2, no swapping will be done, and then count the number of swaps. here count_of_swap=0

then, compare element[1] and element[2], that is 2 and 3, again no swapping, count_of_swap=0

similarly compare all the elements of the array as, 3 and 4, 4 and 5, 5 and 6, that ends first iteration for the bubble sort, now check count_of_swaps that is still equals to zero, this indicates that the array is already sorted, hence display the respective information and exit the algorithm.

Selection sort:

Selection sort works with the idea of selecting an element of the list and then comparing it to the rest of the elements to find it's place in the list,

for the given list [1,2,3,4,5,6]

firstly the element[0]=1, will get compared to the rest of the elements, with no swaps, thus finishing the first iteration

similarly, the loops will going to continue to compare the elements untill end of the list and then shows the necessary information regarding the array is already being sorted.

Insertion Sort:

As mentioned earlier also the insertion sort works with the principle of selecting key, then pushing the list by one step according to the required conditioning and then inserting the element to it's right place.

In the case given list [1,2,3,4,5,6]

since, the value of key will not be going to change, checking on the key with the elements used to assign for the key of the array can give away the idea that array is already sorted.

Merge sort:

Merge sort is a very good example of divide and conquer technique, proposed in greedy algorithms, that is

dividing the list in to the smaller parts such that no part will have no of elements not greater then 2, that is achieved by,, dividing the lis into two parts [1,2,3] and [4,5,,6] that will further be decomposed into

[1,2], [3], [4,5], [6]

Now compare the elements in the list, and swap if needed, ths gives

[1,2], [3], [4,5], [6]

Now, merge the parts as it is to again form the entire list

[1,2,3,4,5,6]

this shows that the list of integer provided is already sorted.

Quick Sort

Quick sort is again like merge sort uses the concept of divide and coquer tehnique, now for the given list

[1,2,3,4,5,6]

here, we can choose, a pivot of the choice,

say, pivot = 4,

Now according to quicksort, all the elements smaller then pivot must be in the left of the pivot, and all elements greater then pivot must be in right of the pivot, that is true in this case, now the partitions be like

4

1, 2, 3 5, 6

Now again for left say pivot be 2, and for right say pivot be 5, this decomposes the list further as,

4

1 2 3 5 6

Now, from above we can get the sorted array as, [1,2,3,4,5,6] ,

that shows, the list of array provided is already sorted.

Related Questions

Navigate

• Browse (All)
• Browse 5
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.