Can I get some help with these Sorting questions? I\'m really confused with what

Question

Can I get some help with these Sorting questions? I'm really confused with what to do. Please explain what you did, I need to learn not simply get the answers, so please show all your work.

Problems on Sorting. (a) If all the elements in an array are sorted in the decreasing order and we want them in increasing order, which sorting algorithm will be asymptotically the fastest; insertion sort, quick sort, merge sort (b) If all the elements in an array are sorted in the increasing order and we want them in increasing order, which sorting algorithm will be asymptotically the fastest; insertion sort, quick sort, merge sort (c) Prove that the optimal complexity for a comparison based sort is O (nlogn) (d) Suppose instead of sorting we require an array to be k sorted, that is for all i i- k Ali] Ali 1,2, 3 n k the following condition holds i What does it mean for an array to be 1-sorted? Give a permutation of the numbers 1,2 10 that is 2-sorted but not sorted.

Explanation / Answer

a) if all the elements in a array are sorted in decreasing order and we want them in increasing order then quick sort will be asymptotically the fastest because quicksort is a fast sorting algorithm that takes a divide-and-conquer approach to sorting lists. Divide and conquer is a technique used for breaking algorithms down into subproblems, solving the subproblems, and then combining the results back together to solve the original problem. It can be helpful to think of this method as divide, conquer, and combine.

b) In general terms, there are the O(n/) sorting algorithms, such as insertion sort, bubble sort, and selection sort, which you should typically use only in special circumstances. Quicksort, which is worst-case O(n/) but quite often O(nlogn) with good constants and properties and which can be used as a general-purpose sorting procedure, the O(nlogn) algorithms, like merge-sort and heap-sort, which are also good general-purpose sorting algorithms and the O(n), or linear, sorting algorithms for lists of integers, such as radix, bucket and counting sorts, which may be suitable depending on the nature of the integers in your lists.

If the elements in our list are such that all we know about them is the total order relationship between them, then optimal sorting algorithms will have complexity (nlogn). This is a fairly cool result and one for which you should be able to easily find details online. The linear sorting algorithms exploit further information about the structure of elements to be sorted, rather than just the total order relationship among elements. So, for this also quick sort can be a good one.

Comparison-Based Sorting

Here the three sorting algorithms:

     Each of these algorithms takes an input array a and sorts the elements of a into non-decreasing order O(nlogn) (expected) time. These algorithms are all comparison-based.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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