search
Log In

Recent questions tagged sorting

3 votes
4 answers
1
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 in Algorithms Satbir 561 views
1 vote
3 answers
2
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 in Algorithms Satbir 328 views
4 votes
2 answers
3
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 442 views
0 votes
0 answers
4
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 137 views
0 votes
0 answers
5
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 101 views
0 votes
1 answer
6
1 vote
1 answer
7
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 64 views
0 votes
1 answer
8
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 72 views
1 vote
1 answer
9
0 votes
0 answers
10
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 60 views
0 votes
2 answers
11
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 141 views
0 votes
1 answer
12
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 114 views
0 votes
1 answer
13
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 87 views
0 votes
0 answers
14
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 64 views
0 votes
0 answers
16
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 60 views
0 votes
0 answers
17
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 67 views
0 votes
0 answers
18
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 40 views
0 votes
1 answer
19
0 votes
0 answers
20
Banks often record transactions on an account in order of the times of the transactions, but many people like to receive their bank statements with checks listed in order by check number. People usually write checks in order by check number, and merchants ... problem of sorting almost-sorted input. Argue that the procedure INSERTION-SORT would tend to beat the procedure QUICKSORT on this problem.
asked Jun 27, 2019 in Algorithms akash.dinkar12 52 views
0 votes
0 answers
21
What value of $q$ does PARTITION return when all elements in the array $A[p..r]$ have the same value? Modify PARTITION so that $q=\lfloor(p+r)/2 \rfloor$ when all elements in the array $A[p..r]$ have the same value.
asked Jun 27, 2019 in Algorithms akash.dinkar12 58 views
0 votes
0 answers
22
PARTITION(A,p,r) 1 x = A[r] 2 i = p – 1 3 for j = p to r – 1 4 if A[j] <= x 5 i = i + 1 6 exchange A[i] with A[j] 7 exchange A[i+1] with A[r] 8 return i + 1 illustrate the operation of PARTITION on the array $A=\langle 13,19,9,5,12,8,7,4,21,2,6,11\rangle$
asked Jun 27, 2019 in Algorithms akash.dinkar12 106 views
0 votes
1 answer
23
We can express the insertion sort as a recursive procedure as follows.In order to sort $A[1\dots n]$, we recursively sort $A[1 \dots n-1]$ and then insert $A[n]$ into the sorted array $A[1 \dots n-1]$. Write a recurrence for the running time of this recursive version of insertion sort.
asked Jun 26, 2019 in Algorithms akash.dinkar12 84 views
0 votes
0 answers
24
Rewrite the MERGE procedure so that it does not use sentinels, instead of stopping once either array $L$ or $R$ has had all its elements copied back to $A$ and then copying the remainder of the other array back into $A$.
asked Jun 26, 2019 in Algorithms akash.dinkar12 69 views
0 votes
1 answer
25
Using Figure $2.4$ as a model, illustrate the operation of merge sort on the array $A=\langle 3,41,52,26,38,57,9,49 \rangle $
asked Jun 26, 2019 in Algorithms akash.dinkar12 72 views
0 votes
1 answer
26
0 votes
0 answers
27
Should not there be a second condition stating i = j-1 in While loop's conditional statement,if not then it seems to me while loop will be a infinite loop..
asked Jun 12, 2019 in Algorithms souren 205 views
0 votes
1 answer
30
An array $A$ of size n is known to be sorted except for the first $k$ elements and the last $k$ elements, where $k$ is a constant. Which of the following algorithms will be the best choice for sorting the array $A?$ $a)$Insertion Sort $b)$Bubble sort $c)$Quicksort ... ? Quick Sort sorts part by part using pivot. So, why not will it be answer?? How do we know it is asking for almost sorted array??
asked May 12, 2019 in Algorithms srestha 461 views
...