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?

Recommended Answers

All 2 Replies

  1. Stable sort. I used https://en.wikipedia.org/wiki/Category:Stable_sorts and https://en.wikipedia.org/wiki/Merge_sort
    Answer. Possible? Yes. But always? No. See second link.

Why not show your efforts on your questions? This is noted at https://www.daniweb.com/programming/threads/435023/read-this-before-posting-a-question and you have many questions. Question one took about 2 minutes to find the answer.

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.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.