1) What is sorting?
Sorting is arranging or ordering the data in some logical order either increasing or decreasing.
2) What are the fundamental types of sorting?
i) Internal Sorting
ii) External Sorting
3) What is internal sorting?
If the data to be sorted remains in main memory and also the sorting is carried out in main memory it is called internal sorting.
4) What is external sorting?
If the data resides in auxiliary memory and is brought into main memory in blocks for sorting and then result is returned back to auxiliary memory is called external sorting.
5) What is stable sorting?
Sorting technique is said to be stable, if for all records i and j such that k[I]=k[j], if r[i] precedes r[j] in original file, r[i] precedes r[j] in sorted file also.
6) What is sorting by address?
In sorting the auxiliary table pointers may be used so that the pointers are moved instead of actual data. This reduces the time needed for sorting.
7) What are the factors to be considered while selecting a sorting method?
Three factors are:
i) Length of time for the programmer to code the sorting program.
ii) Amount of machine time necessary for running the program.
iii) Amount of space necessary for the program to execute.
8) List the names of some internal sorting methods.
i) Bubble sort
ii) Insertion sort
iii) Selection sort
iv) Shell sort
v) Quick sort
vi) Heap sort
9) Write about any one external sorting method?
Merge sort is an example of external sorting. This sorts the sub arrays and the sorted sub arrays are stored in an auxiliary table. Then the sorted sub arrays are brought in to main memory for merging and sorting.
10) What is bubble sort?
Bubble sort arranges the array of integers as x[i]<=x[j], 0<=I
This was given the name as each element bubbles to the proper position.
11) What is quick sort or partition exchange sort?
Quick sort moves the data item into the correct direction, with the following rules:
i) Select a pivot element, from the array x.
ii) Initialize the down and up as the lower bound and upper bound of array.
iii) Increment down pointer, until x[down]>a
iv) Decrement up pointer, until x[up]<=a v) If up>down, interchange x[down] with x[up]
vi) If up<=down, interchange x[up] with pivot.
12) What is Pivot?
The element around which a file is partitioned is called a pivot.
13) What are the different methods for choosing a pivot?
i) The median of the first, last and middle elements of the sub file to be sorted can be chosen as pivot.
ii) The mean sort uses the mean of the sub file as pivot for sorting.
iii) Bsort uses the middle element of subfile as pivot.
14) What is selection sort?
Selection sort is one in which successive elements are sorted in order and placed into their proper sorted position.
15) What is straight selection sort or push down sort?
Straight selection sort is an in-place sort, from which the largest element should be chosen and interchanged with the element at end.
16) What is binary tree sort?
In binary tree sort, a binary tree of descending priority queue is created first and inorder traversing of the tree gives a sorted list.
17) What is Heap sort?
Heap sort is also an in-place sort, which creates a binary search tree in which elements are to be sorted and stored.
18) What is descending heap/Max heap/Descending partially ordered queue?
Descending heap of size n is an almost complete binary tree of nodes such that the content of each node is less than or equal to the content of its father.
19) What is Ascending heap/Min heap?
Min heap is an almost complete binary tree such that the content of each node is greater than or equal to the content of its father.
20) What is the inequality/ condition for sequential representation of heap?
Info[j]<=info[(j-1)/2] for 0<=((j-1)/2)
Other Questions…
1) What is sorting and explain the various sorting methods.
2) Discuss about the efficiency considerations while selecting a sorting algorithm
3) What are the types of Exchange sorts. Explain algorithms with examples.
4) Explain bubble sort with example.
5) Explain Quick sort with example and their efficiency considerations.
6) What are the various ways of choosing a pivot in quick sort?
7) What is selection sort and write the general selection sort algorithm.
8) What is straight selection sort/ Push down sort?
9) Explain Binary tree sorts.
10) Explain with example- How sorting is performed in a heap with descending heap?
11) Write about simple insertion sort.
12) What is shell sort / Diminishing increment sort? Explain with example.
13) What is address calculation sort / Sorting by hasing?
14) Explain the external sorting methods.
15) Briefly explain about any four internal sorting methods.
16) Explain merge sort with example.
17) Explain Cook-Kim algorithm and what are the advantages of it?
18) Explain Radix sort / Radix exchange sort with example.
Works for You…
1) What is a sort decision tree?
2) What is sort by counting?
3) What is distribution sort?
4) What is odd-even transposition sort?
5) What is quadratic selection sort?
6) What is a tournament?
7) What is a almost complete ternary tree?
8) What is a ternary heap?
9) What is two way insertion sort?
10) What is merge insertion sort?
11) Sort the following list of numbers with the sorting methods mentioned with all steps in clear.
96 23 65 8 28 15 67 32
i) Bubble sort
ii) Quick sort
iii) Selection sort
iv) Heap sort
v) Simple insertion sort
vi) Shell sort
vii) Address calculation sort
viii) Merge sort
ix) Radix sort
No comments:
Post a Comment