For each example choose one of the following sorting algorithms and carefully ju

ID: 673473 • Letter: F

Question

For each example choose one of the following sorting algorithms and carefully justify your choice: HeapSort, RadixSort, CountingSort. Give the expected runtime for your choice as precisely as possible. If you choose Radix Sort then give a concrete choice for the basis (i.e. the value of "r" in the book) and justify it. Sort the length 2^16 array A of 128-bit integers on a device with 100MB of RAM. Sort the length 2^24 array A of 256-bit integers on a device with 600MB of RAM. Sort the length 2^16 array A of 16-bit integers on a device with 1GB of RAM.

Explanation / Answer

First of all, let me clear the time and space complexities of Sorting algorithms:

Heap Sort Radix Sort Counting Sort

Time Complexity: O(nlogn) O(nk) O(nk)

Space Complexity: O(1) O(n+k) O(n+k)

Note : Array takes continuous space in memory. So they need space in single chunk. Now, back to the solution

Case 1 :

Array length 2^16 that is 65,536

Size of integer : 128 bit that is 16 bytes

Ram : 100 MB

Space taken by 65536 integers in memory(RAM) = 65536 * 16 = 1,048,576 bytes = 1 MB

Getting 1 MB continuous space is not big task, so space complexity is not determining factor here. In terms of time complexity, Radix Sort is best. So we'll prefer that.

Case 2 :

Array length 2^24 that is 16,777,216

Size of integer : 256 bit that is 32 bytes

Ram : 600 MB

Space taken by 16,777,216 integers in memory(RAM) = 16777216 * 32 = 536,870,912 bytes = 512 MB

Our total RAM is just 600 MB, and we need 512 MB just to store these integers (not to forget array takes continuous space in memory). So in this case, space complexity is our determining factor. And there is obviously one winner, HEAP SORT :)

Case 3:

Array length 2^16 that is 65,536

Size of integer : 16 bit that is 2 bytes

Ram : 1 GB or 1024 MB

Space taken by 65,536 integers in memory(RAM) = 65536 * 2 = 131,072 bytes = 128 KB

I do not need to explain this, do I? ;)

1 GB RAM and we need just 128 KB space, so our choice is definitely RADIX SORT.

Navigate

For each example below, indicate which of the following statistics would be appr

For each example presented below, identify whether positive reinforcement (PR),

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

For each example choose one of the following sorting algorithms and carefully ju

Question

Explanation / Answer

Related Questions

Navigate