5. Sorting (a) During lecture, we focused on four different sorting algorithms:

Question

5. Sorting (a) During lecture, we focused on four different sorting algorithms: i counting sort. a For each of these four algorithms, state: wast, best,t bert n loo(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 above algorithms is the best choice? (0 Suppose we want to sort an array of ints, but also want to minimize the amount of extra memory we want to (8) Suppose we want to somt an arry of charAssuming 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 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. Now, find a way of making a version of quick sort implemented using the random pivot selection strategy run in O (n2) time. i) How can you modify both versions of quicksort so that they no longer display(m) behavior given the same inputs?

Explanation / Answer

(a) (i) Insertion Sort:

Best case: O(n), Average case:O(n2), Worst case: O(n2).

Merge Sort:

Best case: O(n log n), Average case: O(n log n), Worst case: O(n log n).

Quick Sort:

Best case: O(n log n), Average case: O(n log n), Worst case: O(n2).

Counting Sort:

Best case: O(n+k), Average case: O(n+k), Worst case: O(n+k).

(ii) Stable Algorithms: Insertion Sor, Merge Sort and Counting Sort.

Quick Sort is not stable.

(iii) in-place Algorithms: Insertion Sort, Merge Sort and Quick Sort.

Counting sort is not in-place.

(iv) Insertion Sort is efficient for small set of data. It is efficient for the data set which is already sorted.

Merge Sort requires additional memory to sort the elements. The worst case complexity is in quadratic. Due to its recursive calls, it is not suitable for small set of numbers.

Quick sort is suitable for any size input data.

Counting Sort is a non comparison based technique, which is very fast when the range of keys is small.

(b) Quick sort will be the best choice for string sorting.

(c) Insertion sort will be the best choice for this senario as discussed above.

Related Questions

Navigate

• Browse (All)
• Browse 5
• Subjects

---

---

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