Question

Problem 3 . A sorting algorithm is stable if the relative order of any two equal entries in the given array stays the same: when two records a[i] and a[j] are equal in content, and i < j, then the algorithm sorts the array in a way that the record originally stored in a[i], still appears to the left of the record originally stored in a[j], when the array is sorted. Which of the algorithms Insertion Sort, Shellsort, Heapsort, and Mergesort (as presented in class) are stable, which are not?

Answer #1

1) Insertion sort : It is a stable sorting algorithm. It ensures that an element a[j] comes to the left of a[i] only when a[j] < a[i].

2) Shellsort : It is not a stable sorting algorithm as it doesn't maintain the relative order of any two equal entries in an array.

3) Heapsort : It is not a stable sorting algorithm because the heapify operations can change the relative order of two equal entries in an array.

4) Mergesort : It is a stable sorting algorithm. Just like selection sort, it ensures that an element a[j] comes to the left of a[i] only when a[j] < a[i].

Hope this resolves your doubt.

Please give an upvote if you liked my solution. Thank you :)

Problem 3 . A sorting algorithm is stable if the
relative order of any two equal entries in the given array stays
the same: when two records a[i] and a[j] are equal in content, and
i < j, then the algorithm sorts the array in a way that the
record originally stored in a[i], still appears to the left of the
record originally stored in a[j], when the array is sorted. Which
of the algorithms Insertion Sort, Shellsort, Heapsort, and...

. A sorting algorithm is stable if the relative order of any two
equal entries in the given array stays the same: when two records
a[i] and a[j] are equal in content, and i < j, then the
algorithm sorts the array in a way that the record originally
stored in a[i], still appears to the left of the record originally
stored in a[j], when the array is sorted. Which of the algorithms
Insertion Sort, Shellsort, Heapsort, and Mergesort (as...

Problem 2 (2+3 marks). Assume your sorting algorithms have to
deal with lists that can potentially contain duplicates. Assume the
same sorting algorithms as discussed in class / in the textbook.
(a) What is the running time of Insertion Sort when all elements in
a given list of length N are equal? Explain your answer. (b) Give a
Θ-bound on the running time of Mergesort for the case that all
elements in a given list of length N are equal...

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 7 minutes ago

asked 19 minutes ago

asked 30 minutes ago

asked 34 minutes ago

asked 42 minutes ago

asked 45 minutes ago

asked 1 hour ago

asked 2 hours ago

asked 2 hours ago

asked 2 hours ago

asked 3 hours ago

asked 3 hours ago