Data Structures: ?Please answer #1-3 ASAP! ShellSort utilizes what sort method t
ID: 3680327 • Letter: D
Question
Data Structures: ?Please answer #1-3 ASAP!
ShellSort utilizes what sort method to do most of the work? It has its own algorithm that is unique Merge Sort Selection Sort Insertion Sort What is the recursion_limit variable in our quickSortX algorithm used for? It is the number of integers left to sort in the array, below which we resort to insertion sort for efficiency. It is the number of elements left to sort in the array, below which the algorithm will fall into an infinite recursive loop. It is the number of recursions that occur in the algorithm after which sorting is completed. It is the number of recursions after which the algorithm will fall into an infinite recursive loop. What is the optimum value to choose as a pivot for a quicksort algorithm? The highest value in the set The median value of the set Any value will work the same The lowest value of the setExplanation / Answer
1)
1. Shellsort, also known as Shell sort or Shell's method, is an in-placecomparison sort. It can be seen as either a generalization of sorting by exchange (bubble sort) or sorting by insertion (insertion sort).
2. The method starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared.
3. Starting with far apart elements can move some out-of-place elements into position faster than a simple nearest neighbor exchange. Donald Shell published the first version of this sort in 1959.
4. The running time of Shellsort is heavily dependent on the gap sequence it uses. For many practical variants, determining their time complexity remains an open problem.
5. Shellsort is a generalization of insertion sort that allows the exchange of items that are far apart. The idea is to arrange the list of elements so that, starting anywhere, considering every hth element gives a sorted list. Such a list is said to be h-sorted.
6. Equivalently, it can be thought of as h interleaved lists, each individually sorted.Beginning with large values of h, this rearrangement allows elements to move long distances in the original list, reducing large amounts of disorder quickly, and leaving less work for smallerh-sort steps to do.
7. If the file is then k-sorted for some smaller integer k, then the file remains h-sorted. Following this idea for a decreasing sequence of hvalues ending in 1 is guaranteed to leave a sorted list in the end.
8. Therefore shellsort utilises Insertion sort method to do most of the work.
2)
1. Quicksort is a comparison sort, meaning that it can sort items of any type for which a "less-than" relation (formally, a total order) is defined.
2. In efficient implementations it is not a stable sort, meaning that the relative order of equal sort items is not preserved. Quicksort can operate in-place on an array, requiring small additional amounts of memory to perform the sorting.
3. Therefore answer is " It is the number of elements left to sort in the array, below which the algorithm fall into infinite recursive loop.
3) The optimum value to choose as pivot element in quick sort is median of the elements.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.