DATA STRUCTURES – SORTING
EXAM QUESTIONS AND ANSWERS
Internal and external sorting - Correct Answers -What are the two types of sorting?
the number of comparisons of keys AND the number of times entries must be moved
inside a list - Correct Answers -What are the two major factors used to evaluate the
performance of a sorting algorithm?
internal sorting - Correct Answers -records to be sorted are kept in RAM
external sorting - Correct Answers -records are kept in external files on disks, tapes, or
other secondary storage devices
The performance of a sorting algorithm is closely related to the ... - Correct Answers -
underlying data structure of a list (algorithm should be aware of the implementation of
the list - preferable to implement the sorting algorithm as a method of the list class
[sortable list]}
when the list is already in sorted order (only n - 1 comparison of keys) - Correct
Answers -The best case for contiguous insertion sort occurs...
when the list is in reverse order - Correct Answers -The worst case for contiguous
insertion sort occurs...
Selection sort is more suitable for long contiguous list than insertion sort - Correct
Answers -In what situation may you select selection sort over insertion sort?
It is easy to implement. - Correct Answers -What is the advantage of bubble sort?
numbers that are multiples of each other - Correct Answers -When Shell sort is used,
what types of increments should you avoid?
quicksort - Correct Answers -best: O(n lg n)
avg: O(n lg n)
worst: O(n^2)
idea: partition the list using some chosen key called the pivot (those less than pivot in
one sublist, those greater in another); sort separately and merge at the end
radix sort - Correct Answers -best: O(nk)
EXAM QUESTIONS AND ANSWERS
Internal and external sorting - Correct Answers -What are the two types of sorting?
the number of comparisons of keys AND the number of times entries must be moved
inside a list - Correct Answers -What are the two major factors used to evaluate the
performance of a sorting algorithm?
internal sorting - Correct Answers -records to be sorted are kept in RAM
external sorting - Correct Answers -records are kept in external files on disks, tapes, or
other secondary storage devices
The performance of a sorting algorithm is closely related to the ... - Correct Answers -
underlying data structure of a list (algorithm should be aware of the implementation of
the list - preferable to implement the sorting algorithm as a method of the list class
[sortable list]}
when the list is already in sorted order (only n - 1 comparison of keys) - Correct
Answers -The best case for contiguous insertion sort occurs...
when the list is in reverse order - Correct Answers -The worst case for contiguous
insertion sort occurs...
Selection sort is more suitable for long contiguous list than insertion sort - Correct
Answers -In what situation may you select selection sort over insertion sort?
It is easy to implement. - Correct Answers -What is the advantage of bubble sort?
numbers that are multiples of each other - Correct Answers -When Shell sort is used,
what types of increments should you avoid?
quicksort - Correct Answers -best: O(n lg n)
avg: O(n lg n)
worst: O(n^2)
idea: partition the list using some chosen key called the pivot (those less than pivot in
one sublist, those greater in another); sort separately and merge at the end
radix sort - Correct Answers -best: O(nk)
