pes 5. Sorting 0) During lecture, we focused an four difent sorting algorithms:
ID: 3726805 • Letter: P
Question
pes 5. Sorting 0) During lecture, we focused an four difent sorting algorithms: insetion sot, mere sont, quiek con,and counting sort. For each of these four algorithms, state bert n looin woxst n ·The best, average, and worst-case runtimes Whether the sorting algorithm is stable Whether the sorting algorithm is in-place used. Whether the sorting algorithm is a general-purpose one, or if there are any restrictions on how it can be (b) Suppose we want to sort an array containing 50 strings. Which of the above four algorithms is the best choice? (e) Suppose we have an array containing a few hundred elements that is almost entirely sorted, apart from a one or two elements that were swapped with the previous item in the list. Which of the algorithms is the best way of sorting this data? (d) Suppose we are writing a website named "sort-my-numbers.com" which accepts and sorts numbers uploaded by the user. Keeping in mind that users can be malicious, which of the above algorithms is the best choice? (e) Suppose we want to sort an array of ints, where we know all the ints are between O and 1000. Which of the (D Suppose we want to sort an array of ints, but also want to minimize the amount of extra memory we want to (e) Supos we want to sort an arry of chssming the chars are all owercase alphabetical letes, which Ch) On the homework, you were asked to find a way of building an array that would cause a version of quick sort Now, find a way of making a version of quick sort implemented using the random pivot selecetion strategy run y both versions of quicksort so that they no longer display O (n2) behavior given the same above algorithms is the best choice? use as much as possible. Which of the above algorithms is the best choice? of the above algorithms is the best choice? implemented using the median-of-three pivoting strategy to run in O (n2) time. in O (n2) time (i) How can you modif inputs?Explanation / Answer
Answer (d):
------------------------------------------------
Answer (e):
Counting Sort is best choice, because we know we have numbers from 0 to 1000 only so we just need to count how many times a number have been appeared in array using hashing method. After that we need to traverse that hash array where index will represent original numbers in array and value stored will be frequency of number in array. So simply print that number as many times it appeared in original array. This will be an O(n) approach.
-------------------------------------------------------------------------------------------------------------------------------------------------
Answer (f):
Quick sort will be best choice, because it runs in O(nlogn) time complexity and it also does not use extra space.
--------------------------------------------------------------------------------------------------------------------------------------------------
Answer (g):
Counting sort will be best choice, because we know there are all lower case alphabets i.e; only 26 characters are possible. So we need to create an auxillary hash array of size 26 and need to count frequency of each character in the array ( hash[ch - 'a']++ ) and after that print each character as many times it appeared in original array.
------------------------------------------------------------------------------------------------------------------
Answer (h):
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.