Let All [1: n] be an array that contain a sequence of distinct integers. Conside

Question

Let All [1: n] be an array that contain a sequence of distinct integers. Consider the following algorithm, called selection sort, to sort A in increasing order: In the first pass, the smallest element is found and moved to the first position. In the second pass, the smallest of the remaining elements is found and moved to the second position. And so on. Express this algorithm in psuedocode, determine the exact number of comparisons made between elements of A, and then express this using big-O notation. (Ignore any other type of operation done by the algorithm.) Your style of pseudocode should be similar to the one in the text or seen in class; do not give full-blown C/C++/Java etc.

Explanation / Answer

selection sort:Generally selection sort works like Selecting the lowest element requires comparing all n elements (this takes n 1 comparisons) and then swapping it into the first position. Finding the next lowest element requires scanning the remaining n 1 elements and so on, for (n 1) + (n 2) + ... + 2 + 1 = n(n 1) / 2 (n2) comparisons. Each of these scans requires one swap for n 1 elements.

Psuedocode:

First we have to declare the array of elements which we want to sort.

After that we will compare the all the elementa with each other in side the for loop for n-1 times for n elements.

After each comparision we swap the laest position of the element compared to other element positon of the array with the least element .

In that way we will continue till n-1 searches completes for n number of elements

Finally entire array will be displayed.

slection sort is completed.

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

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