1)Illustrate the operation of Counting-Sort on the array A={6,0,2,0,1,3,4,6,1,3,2}
2)Illustrate the operation of Radix-Sort on the following list of English words: COW,DOG,SEA,RUG,ROW,MOB,RAT,BAT,BAR,EAR,TAR,DIG,BIG,TEA,NOW,FOX}.
3)Illustrate the operation of Bucket Sort on the array A={.81,.09,.13,.61,.43,.23,.98,.60,.75,.41}.
4)Explain how to sort n integers in the range 0 to n^2-1 in O(n) time.
5)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 the scheme take?
6)What is the worst-case running time for the bucket-sort algorithm? What simple change to the algorithm preserves its linear expected running time and makes its worst-case running time O(nlgn)?
7)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 a range [a...b] in O(1) time.The algorithm should use THETA(n+k) preprocessing time.
8)When are Radix and Bucket sorts used?
Search Your Question
Tuesday, July 22, 2008
Counting, Radix and Bubble sorts
Labels:
Data Structures
Subscribe to:
Post Comments (Atom)
Archives
-
▼
2008
(992)
-
▼
July
(288)
- Yahoo Interview
- Yahoo Interview Questions
- Yahoo Interview Questions-1
- Yahoo Interview Questions-2
- Visual Basic Interview Questions -7
- Visual Basic Interview Questions -6
- Visual Basic Interview Questions -5
- Visual Basic Interview Questions -4
- Visual Basic Interview Questions -3
- Visual Basic Interview Questions -2
- Visual Basic Interview Questions -1
- SQL Interview Questions -8
- SQL Interview Questions -7
- SQL Interview Questions -6
- SQL Interview Questions -5
- SQL Interview Questions -4
- SQL Interview Questions -3
- SQL Interview Questions -2
- SQl Job Interview Questions
- Solutions to C programming questions
- Modified Array based QuickSort with respect to the...
- Last Non Zero Digit of Factorial
- Quick Sort routine to find the kth smallest elemen...
- Run time Analysis of QuickSort ,Nature of Input,Pi...
- Tree Arithmetic
- Number of ways to express a number as summation of...
- Solutions to Logical Puzzles-2
- Combinations
- Solutions to Basic C Interview Questions
- Solutions to Logical Puzzles-1
- Solutions to Logical Puzzles-3
- C program to find the height of a binary search tree
- C program to determine the number of nodes in a bi...
- C program to delete a tree
- Minimum Value of a Binary Search Tree
- Solutions to Questions on recursion
- C program to create mirror copy of a tree
- Solutions to Amazon Intern Interview Questions
- Traversals of a Binary Tree
- Solutions to Google Top Interview Puzzles
- Solutions to problems in recursion analysis
- solution1
- C-program to make a copy of a tree
- C-program to check whether a binary tree is a Bina...
- C-program to delete a node from a tree
- Search On a Binary Search Tree
- C-program to count the leaves in a tree
- Some Basic Questions on sorting and their solutions
- Resume Tips
- Secrets of a Selling Resume
- The Three R's of Resume Writing
- Top Ten Pitfalls of a Resume
- Ten Tips for Writing Better Resumes
- Frequently Asked Questions - Object oriented Concepts
- Frequently Asked Questions - Operating System Conc...
- Frequently Asked Questions - Database
- Frequently Asked Questions - Networking
- UNIX Concepts
- Resources For Placements Preparation
- Essentials Of Operating Systems
- Networking Concepts
- Microsoft Puzzles
- Important Puzzles
- Important Puzzles
- Important Puzzles
- Important Puzzles
- Important Puzzles
- Important Puzzles
- Important Puzzles
- Important Puzzles
- Important Puzzles
- Practise Puzzles - 1
- Practise Puzzles - 1
- Practise Puzzles - 2
- Practise Puzzles - 2
- Practise Puzzles - 2
- Answers For Practise Puzzles - 1
- Answers for Practise Puzzles - 2
- Practise Puzzles - 3
- Practise Puzzles - 3
- Practise Puzzles - 3
- Answers for Practise Puzzles - 3
- Practise Puzzles - 4
- Practise Puzzles - 4
- Answers For Practice Puzzles - 4
- Puzzles
- Logical Puzzles-1
- Logical Puzzles -2
- Logical Puzzles-3
- Algorithms And Programming #4
- Algorithms And Programming #5
- Algorithms And Programming #6
- Algorithms And Programming #7
- Algorithms And Programming #8
- Algorithms And Programming #9
- Prime Numbers!
- C Programming Puzzles
- C Programming Puzzles 2
- C Programming Puzzles 3
- C Programming Puzzles 4
-
▼
July
(288)
No comments:
Post a Comment