Next:9.1 Bubble SortUp:DSAPrevious:8.7.2 Traveling Salesman Problem

# 9. Sorting Methods

The function of sorting or ordering a list of objects according to some linear order is so fundamental that it is ubiquitous in engineering applications in all disciplines. There are two broad categories of sorting methods: Internal sorting takes place in the main memory, where we can take advantage of the random access nature of the main memory; External sorting is necessary when the number and size of objects are prohibitive to be accommodated in the main memory.

The Problem:

• Given records r1, r2,..., rn, with key values k1, k2,..., kn, produce the records in the order
ri1, ri2,..., rin,
such that

ki1ki2...kin

• The complexity of a sorting algorithm can be measured in terms of
• *
number of algorithm steps to sort n records
*
number of comparisons between keys (appropriate when the keys are long character strings)
*
number of times records must be moved (appropriate when record size is large)
• Any sorting algorithm that uses comparisons of keys needs at least O(n log n) time to accomplish the sorting.

 Sorting Methods Internal External (In memory) Appropriate for secondary storage quick sort heap sort mergesort bubble sort radix sort insertion sort polyphase sort selection sort shell sort

Next:9.1 Bubble SortUp:DSAPrevious:8.7.2 Traveling Salesman Problem
eEL,CSA_Dept,IISc,Bangalore