Page 266 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 12: Sorting

12.10 Summary Notes

z Arranging objects in a specified order is called sorting.
z Bubble sort, insertion sort, selection sort, quick sort, heap sort, radix sort are some of very
common search algorithms.

z The comparison starts with the first element (or at the last element) and continues
sequentially till either we find a match or the end of the list is encountered. Linear search

makes as many comparisons as there are elements in the array. Even if the array is sorted
(either in ascending or descending order) the number of comparisons remains the same.

12.11 Keywords

Bubble sort: A sorting technique in which the largest element of the remaining list bubbles up to
its proper ordering position in each pass through the list.

Heap sort: A sorting technique in which all the entries in the list are arranged to satisfy heap
property, and then top of the heap is removed and another entry is promoted to take its place
repeatedly.
Merge sort: A sorting technique in which the given list is broken down into smaller lists repeatedly
until the list become easy to sort, then the sorted lists are merged to obtain the final sorted list.

Quick sort: A sorting technique in which an array is sorted by picking some value in the array

as a key element, then swapping the first element of the list with the key element so that the key

comes in the first position. The proper place of key in the list is found out repeatedly.
Sorting: A technique to arrange the elements of a list in some pre-specifi ed order.

12.12 Self Assessment

Choose the appropriate answers:
1. Which one is not the method of internal sorting?
(a) Heap sort

(b) Merge sort
(c) Quick sort
(d) Bubble sort
2. Polyphase sort is a
(a) Internal sort

(b) External sort
(c) Both of the above
(d) None
3. ........................ is a sorting technique which sorts a contiguous list of length n with O(nlog2(n)
comparisons and movement of entries, even in the worst case.
(a) Heap sort
(b) Merge sort
(c) Quick sort

LOVELY PROFESSIONAL UNIVERSITY 261