Question

Problem 3 (4 marks). A sorting algorithm is stable if the relative order of any two...

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?

Homework Answers

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 :)

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Problem 3 (4 marks). A sorting algorithm is stable if the relative order of any two...
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...
. 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...
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
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT