0

I need help with some questions.They were 20 of them but this 5 have been so hard for me. Any help I get will be highly appreciated. Cheers!!!

1.When mergesort is implemented on a linked list it is possible to implement it as a stable sort. True or False?

These questions are based on shuffling linked lists:
2.Suppose the implementation of shuffling uses mergesort as the sorting algorithm, and it takes O(n^2) to generate n random numbers. Then shuffling can be implemented in ?

3.Suppose the implementation of shuffling uses bubblesort as the sorting algorithm, and it takes O(n) to generate n random numbers. Then shuffling can be implemented in?

4.Suppose the implementation of shuffling uses mergesort as the sorting algorithm, and it takes O(n) to generate n random numbers. Then shuffling can be implemented in?

5.The implementation of a shuffle on a linked list uses O(n) scratch space to store random numbers used for the shuffle.

Consult the resource on the Fisher-Yates shuffling algorithm to determine whether the following statement is true or false:
The Fisher-Yates algorithm can be implemented on a linked list so that it uses only O(1) scratch space with O(n) time complexity.
True or False?

2
Contributors
2
Replies
26
Views
6 Months
Discussion Span
Last Post by Mirty
1

rproffitt I managed to do them. Thanks for your help. They were 20 question in total and the ones I posted were the ones giving me trouble. I have managed to them.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.