Trace selection sort as it sorts the following array into ascending order: 15, 2

Question

Trace selection sort as it sorts the following array into ascending order:

                15, 20, 3, 9, 25, 30, 2, 5

Trace insertion sort as it sorts the following array into ascending order:

                15, 20, 3, 9, 25, 30, 2, 5

Trace bubble sort as it sorts the following array into ascending order:

                15, 20, 3, 9, 25, 30, 2, 5

Trace mergesort as it sorts the following array into ascending order:

15, 20, 3, 9, 25, 30, 2, 5

Trace heapsort as it sorts the following array into ascending order:

                15, 20, 3, 9, 25, 30, 2, 5

Trace quicksort as it sorts the following array into ascending order:

                15, 20, 3, 9, 25, 30, 2, 5

Here is an array which has just been partitioned by the first iteration of quicksort:

      3, 0, 2, 4, 5, 8, 7, 6, 9

Which of these elements were possibly the pivot element? (There may be more than one possibility!)

Explanation / Answer

Trace selection sort as it sorts the following array into ascending order:

original array: 15, 20, 3, 9, 25, 30, 2, 5

1 st : 2 15 20 3 9 25 30 5
2nd: 2 3 15 20 9 25 30 5
3rd: 2 3 5 15 20 9 25 30
4th: 2 3 5 9 15 20 25 30
5th: 2 3 5 9 15 20 25 30
6th: 2 3 5 9 15 20 25 30
7th : 2 3 5 9 15 20 25 30

here we have 8 elements and we get 7 passes. 7th swap is still necessary, since the computer does not know the first two are sorted yet.

Bubble sort:
15, 20, 3, 9, 25, 30, 2, 5

1st: 15 20 3 9 25 30 2 5
         15 20 3 9 2 5 25 30
2nd: 3 9 15 20 2 5 25 30
3rd: 2 5 3 9 15 20 25 30
4th: 2 3 5 9 15 20 25 30

insertion:
15, 20, 3, 9, 25, 30, 2, 5

1st: 15 20 3 9 25 30 2 5
2nd: 15 3 20 9 25 30 2 5
3rd: 3 15 20 9 25 30 2 5
4th: 3 15 9 20 25 30 2 5
5th: 3 9 15 20 25 30 2 5
6th: 3 9 15 20 25 30 2 5
7th: 2 3 9 15 20 25 30 5
8th: 2 3 5 9 15 20 25 30

Merge sort:
First divide the list into the smallest unit (1 element), then compare each element with the adjacent list to sort and merge the two adjacent lists. Finally all the elements are sorted and merged.
15 20 3 9 25 30 2 5
15 20 3 9 25 30 2 5
3 9 15 20 2 5 25 30
2 3 5 9 15 20 25 30

Heap sort:

A run of the heapsort algorithm sorting an array of randomly permuted values. In the first stage of the algorithm the array elements are reordered to satisfy the heap property

15 20 3 9 25 30 2 5
2 15 20 3 9 30 25 5
2 5 3 9 15 20 25 30

Everything to the left of x must be < x, and everything to the right of x must be > x
4, 5, 9

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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