search
Log In
0 votes
135 views
Use induction to prove that radix sort works. Where does your proof need the assumption that the intermediate sort is stable?
in Algorithms 135 views

Please log in or register to answer this question.

Related questions

1 vote
1 answer
1
0 votes
1 answer
2
246 views
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 246 views
0 votes
2 answers
3
274 views
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 274 views
0 votes
0 answers
4
191 views
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 191 views
...