Silly-Sort(A,i,j)
if A[i] > A[j]
then exchange A[i] and A[j];
if i+1 >= j
then return;
k = floor(j-i+1)/3);
Silly-Sort(A,i,j-k);
Silly-Sort(A,i+k,j);
Silly-Sort(A,i,j-k);
(a) Argue (by induction) that if n is the length of A, then
Silly-
Sort(A,1,n) correctly sorts the input array A[1...n]
(b) Give a recurrence relation for the worst-case run time of
Silly-Sort
and a tight bound on the worst-case run time
(c) Compare this worst-case runtime with that of insertion sort,
merge
sort, heapsort and quicksort.
A.
By induction:
For the base case let n = 2. The first two lines of the algorithm
will check if
the two elements are sorted; if not, it exchanges them (and now
they are sorted).
The algorithm returns after the following if statement. Thus
Silly-Sort sorts
correctly for n = 2.
Assume Silly-Sort correctly sorts an input array of size 2n/3 (you
may also
assume that Silly-Sort correctly sorts an array of size k, for any
1 ≤ k < n).
Let A[1..n] be an input array of size n. By the induction
hypothesis the first call to
Silly-Sort(A, i, j−k) correctly sorts the first 2n/3 elements, so
that the elements
1 . . .n/3 are less than elements (n+1)/3 . . . 2n/3. The call to
Silly-Sort(A, i, j−
k) correctly sorts the last 2n/3 elements, so that the elements (n
+ 1)/3 . . . 2n/3
are less than elements 2(n + 1)/3 . . .n. Also, after this call
to Silly-Sort the
elements 2(n + 1)/3 . . .n (the last n/3 elements) are the largest
n/3 elements in A.
The last call to Silly-Sort(A, i, j − k) sorts correctly (by
induction hypothesis)
the elements 1 . . . 2n/3. These sorted elements are less than
elements 2(n+1)/3 . . .n.
Thus the array A of size n is sorted.
b. Give a recurrence for the worst-case running time of
Silly-Sort and a tight
asymptotic (Θ-notation) bound on the worst-case running time.
Solution:
T(n) = 3T(2n3) + Θ(1)
= . . .
= Θ(n^log3/2 3)
= Θ(n^2.7...).
c.
Insertion-Sort: Θ(n^2)
Merge-Sort: Θ(n lg n)
Heapsort: Θ(n lg n)
Quicksort: Θ(n^2)
Silly-Sort: Θ(n^2.7...)
Silly-Sort(A,i,j) if A[i] > A[j] then exchange A[i] and A[j]; if i+1 >= j then return;...
And the related
algorithms:
(20 points) Consider the following strategy for choosing a pivot element for the Partition subroutine of QuickSort, applied to an array A. .Let n be the number of elements of the array A. If n 24, perform an Insertion Sort of A and return. Otherwise: Choose 2n/2)| elements at random from n; let S be the new list with the chosen elements. Sort the list S using Insertion Sort and use the median m of S...
Subject: Algorithm
need this urgent please.
2.1 Searching and Sorting- 5 points each 1. Run Heapsort on the following array: A 17, 3, 9, 4, 2,5, 6, 1,8) 2. Run merge sort on the same array 3. What is the worst case for quick sort? What is the worst case time com- plexity for quick sort and why? Explain what modifications we can make to quick sort to make it run faster, and why this helps.
2.1 Searching and Sorting-...
Insertion sort on small arrays in merge sort Although merge-sort runs in Θ(n log n) worst-case time and insertion sort runs in Θ(n 2 ) worst-case time, the constant factors in insertion sort can make it faster in practice for small problem sizes on many machines. Thus, it makes sense to coarsen the leaves of the recursion by using insertion sort within merge sort when subproblems become sufficiently small. Consider a modification to merge sort in which n/k sublists of...
2.1 Searching and Sorting- 5 points each 1. Run Heapsort on the following array: A (7,3, 9, 4, 2,5, 6, 1,8) 2. Run merge sort on the same array. 3. What is the worst case for quick sort? What is the worst case time com- plexity for quick sort and why? Explain what modifications we can make to quick sort to make it run faster, and why this helps. 4. Gi pseudocode for an algorithm that will solve the following...
PROBLEM 1 (24 points): For each of the recursive functions below and on the next page, give a correct recurrence relation expressing its runtime and then a tight runtime bound for the recurrence relation. Functions that take parameters lo and hi: n=hi-lo+1 RECURRENCE RELATION: int foo(int a[], int lo, int hi) { int x, i, j, m; X = 0; if(lo==hi) return a[10]; for(i=lo; i<=hi; i++) { for(j=i+1; j<=hi; j++) { if(a[i] % 2) x += a[i]; else x -=...
Inal Examination 17. Which of the sorting algorithms listed below has the time fastest best case run (a) Heap sort (b) Merge sort (c) Quick sort (d) Insertion sort 18. Which statement below is false: (a) Quick uick sort and merge sort are divide and conquer algorithte (b) Counting sort is a linear time sorting algorithm. (e) Insertion sort and quicksort have similar best case (d) Generic minimum spanning tree algorithm is 19. Counting sort and radix sort are linked...
When asked to describe an algorithm you are expected to give a
clear pseudo-code description of the algorithm
1. (10 pts) Here is a new sorting algorithm NewSort Suppose the original call made is NewSort(A,0,n-1) where A is an array integers. == void NewSort(int A[], int i, int j){ \\ sorts the subarray Aſi..j] if (j i+1) \\when there are only 2 elements if (A[i] > A[j]) swap(A,i,j) \\swaps A[i] and A[j] else { int k = (j-i+1)/3; NewSort(A,i,j-k); \\...
1. Which is the best sorting algorithm for larger arrays if all the items can not fit in main memory? selection sort insertion sort quicksort Merge sort 2. Which sorting algorithm sorts items without comparing them? quick sort radix sort merge sort Insertion sort 3 What is the average running time for quicksort? O(n2) O(logn) O(nlogn) O(n) O(n2logn) 4. Examine the steps of the following algorithm and write the name of the algorithm described in the blank provided: Recursively divide...
Read the following pseudocode, note that A is a sorted array: BINARY-SEARCH(A, v) low := 1 high := n while low <= high mid = floor((low+ high)/2) if v == A[mid] return mid else if v > A[mid] low = mid + 1 else high = mid - 1 return NIL a) Find the Recurrence Relation. b) Is there a tight bound? If the answer is yes, find it. c) Find the best case and worst case running time.
Read the following pseudocode, note that A is a sorted array: BINARY-SEARCH(A, v) low := 1 high := n while low <= high mid = floor((low+ high)/2) if v == A[mid] return mid else if v > A[mid] low = mid + 1 else high = mid - 1 return NIL a) Find the Recurrence Relation. b) Is there a tight bound? If the answer is yes, find it. c) Find the best case and worst case running time.