search
Log In

Recent questions tagged sorting

3 votes
3 answers
1
Consider the following array.$\begin{array}{|l|l|l|l|l|l|} \hline 23&32&45&69&72&73&89&97 \\ \hline\end{array}$ Which algorithm out of the following options uses the least number of comparisons (among the array elements) to sort the above array in ascending order? Selection sort Mergesort Insertion sort Quicksort using the last element as pivot
asked Feb 18 in Algorithms Arjun 974 views
2 votes
3 answers
3
Given two sorted list of size '$m$' and '$n$' respectively. The number of comparisons needed in the worst case by the merge sort algorithm will be : $m^{*}n$ minimum of $m, n$ maximum of $m, n$ $m+n-1$
asked Mar 31, 2020 in Algorithms Lakshman Patel RJIT 558 views
4 votes
11 answers
4
Which of the following sorting algorithms does not have a worst case running time of $O(n​^2​)$? Insertion sort. Merge sort. Quick sort. Bubble sort.
asked Mar 31, 2020 in Algorithms Lakshman Patel RJIT 2.9k views
0 votes
3 answers
5
1 vote
2 answers
6
1 vote
3 answers
7
The running time of Quick sort algorithm depends heavily on the selection of: No. of inputs Arrangement of elements in an array Size of elements Pivot Element
asked Mar 31, 2020 in Algorithms Lakshman Patel RJIT 3.1k views
4 votes
4 answers
8
If an array $A$ contains the items $10,4,7,23,67,12$ and $5$ in that order, what will be the resultant array $A$ after third pass of insertion sort? $67,12,10,5,4,7,23$ $4,7,10,23,67,12,5$ $4,5,7,67,10,12,23$ $10,7,4,67,23,12,5$
asked Jan 13, 2020 in Algorithms Satbir 1.9k views
1 vote
3 answers
9
Of the following sort algorithms, which has execution time that is least dependant on initial ordering of the input? Insertion sort Quick sort Merge sort Selection sort
asked Jan 13, 2020 in Algorithms Satbir 772 views
5 votes
2 answers
10
Which of the following is best running time to sort $n$ integers in the range $0$ to $n^2-1$? $O(\text{lg } n)$ $O(n)$ $O(n\text { lg }n)$ $O(n^2)$
asked Jul 2, 2019 in Algorithms Arjun 1.1k views
0 votes
0 answers
11
A probability distribution function $P(x)$ for a random variable $X$ is defined by $P(x) =Pr\{X\leq x\}$.Suppose that we draw a list of $n$ random variables $X_1,X_2,…,X_n$ from a continuous probability distribution function $P$ that is computable in $O(1)$ time. Give an algorithm that sorts these numbers in linear averagecase time.
asked Jun 28, 2019 in Algorithms akash.dinkar12 224 views
0 votes
0 answers
12
We are given $n$ points in the unit circle, $P_i=(x_i,y_i)$, such that $0<x_i^2+y_i^2<1$ for $i=1,2, .,n$.Suppose that the points are uniformly distributed; that is, the probability of finding a point in any region of the circle is proportional to the ... from the origin. (Hint: Design the bucket sizes in BUCKET-SORT to reflect the uniform distribution of the points in the unit circle.)
asked Jun 28, 2019 in Algorithms akash.dinkar12 191 views
0 votes
1 answer
13
1 vote
1 answer
14
Explain why the worst-case running time for bucket sort is $\Theta(n^2)$. What simple change to the algorithm preserves its linear average-case running time and makes its worst-case running time $O(n\ lg\ n)$?
asked Jun 28, 2019 in Algorithms akash.dinkar12 158 views
0 votes
1 answer
15
BUCKET-SORT(A) 1 let B[0...n-1] be a new array 2 n = A.length 3 for i – 0 to n – 1 4 make B[i] an empty list 5 for i = 1 to n 6 insert A[i] into list B[nA[i]] 7 for i = 0 to n – 1 8 sort list B[i] with insertion sort 9 concatenate the lists B[0] , B[1] , ….,B[n-1] together in order illustrate the operation of BUCKET-SORT on the array $A=\langle .79,.13,.16,.64,.39,.20,.89,.53,.71,.42\rangle$
asked Jun 28, 2019 in Algorithms akash.dinkar12 134 views
1 vote
2 answers
16
0 votes
0 answers
17
Use induction to prove that radix sort works. Where does your proof need the assumption that the intermediate sort is stable?
asked Jun 28, 2019 in Algorithms akash.dinkar12 220 views
0 votes
2 answers
18
Which of the following sorting algorithms are stable: insertion sort, merge sort, heapsort, and quicksort? Give a simple scheme that makes any sorting algorithm stable. How much additional time and space does your scheme entail?
asked Jun 28, 2019 in Algorithms akash.dinkar12 651 views
0 votes
1 answer
19
RADIX-SORT(A, d) 1 for i = 1 to d 2 use a stable sort to sort array A on digit i illustrate the operation of RADIX-SORT on the following list of English words: COW, DOG, SEA, RUG, ROW, MOB, BOX, TAB, BAR, EAR, TAR, DIG, BIG, TEA, NOW, FOX.
asked Jun 28, 2019 in Algorithms akash.dinkar12 354 views
0 votes
2 answers
20
Describe an algorithm that, given $n$ integers in the range $0$ to $k$ preprocesses its input and then answers any query about how many of the $n$ integers fall into the range $[a..b]$ in $O(1)$ time.Your algorithm should use $\Theta(n+k)$ preprocessing time.
asked Jun 28, 2019 in Algorithms akash.dinkar12 297 views
0 votes
0 answers
21
Suppose that we were to rewrite the for loop header in line $10$ of the COUNTINGSORT as 10 for j = 1 to A.length Show that the algorithm still works properly. Is the modified algorithm stable?
asked Jun 28, 2019 in Algorithms akash.dinkar12 173 views
0 votes
0 answers
23
COUNTING-SORT(A, B, k) 1 let C[0, ,k] be a new array 2 for i = 0 to k 3 C[i] = 0 4 for j = 1 to A.length 5 C[A[j]] = C[A[j]] + 1 6 // C[i] now contains the number of elements equal to i . 7 for i =1 to k 8 C[i] = C[i] + C[i-1] 9 // C[i] now contains the ... [C[A[j]]] = A[j] 12 C[A[j]] = C[A[j]] - 1 illustrate the operation of COUNTING-SORT on the array $A=\langle 6,0,2,0,1,3,4,6,1,3,2 \rangle $
asked Jun 28, 2019 in Algorithms akash.dinkar12 150 views
0 votes
0 answers
24
Suppose that you are given a sequence of $n$ elements to sort.The input sequence consists of $n/k$ subsequences, each containing $k$ elements.The elements in a given subsequence are all smaller than the elements in the succeeding subsequence and larger than the ... this variant of the sorting problem. (Hint: It is not rigorous to simply combine the lower bounds for the individual subsequences.)
asked Jun 28, 2019 in Algorithms akash.dinkar12 122 views
0 votes
0 answers
25
Show that there is no comparison sort whose running time is linear for at least half of the $n!$ inputs of length $n$.What about a fraction of $1/n$ inputs of length $n$? What about a fraction $1/2^n$?
asked Jun 28, 2019 in Algorithms akash.dinkar12 95 views
0 votes
1 answer
26
...