CHAPTER
11
SORTING: ORDERING IT TO SEARCH FASTER
Can you imagine trying to
locate a word in a dictionary that is not sorted or put in order? You would have
quite a bit of difficulty finding the word.
Sorting makes searching not only efficient but in many applications possible.
How does a computer sort the data? It is very
similar to the way you sort a series of numbers or a deck of cards. There are
many ways that the data can be sorted, therefore many algorithms are there to
look into and analyze. Among various existing algorithms one algorithm may
perform better than another one in certain circumstances. While one sort
algorithm will do the job of sorting,
it is important to understand various sorting techniques, trends and
circumstances so that a proper algorithm can be chosen. The complexity
of a sorting algorithm is measured in terms of speed (time), amount of space
required for memory storage and/or
its simplicity. The three categories of
sorting techniques include exchange sort, selection sort and insertion sort.
These categories are based on the movement and exchange of the two next items
(exchange), selecting the next item (selection), and inserting the next item in
the right position (insertion). In most of the sorting techniques, the unsorted
data is already placed in an array and the same array is used to hold the sorted
data so as not to waste memory. There are cases
where an array is not used. The data may be
stored in the files or even in some other data structure such as a
linked list built by pointers.
Imagine that there are 10
cards sitting next to each other on your desk
and your task is to put them in order (sort it) from smallest to largest
(ascending order). You manage to do it right away. How did you do that? Now, try
to write down each step as you did the sort. Did you continuously compare each
card with the next card and then exchange (swap) the cards?
If not, did you pick up the smallest card and place it at the beginning? Or did
you place each card in its spot as you performed the sort? If you didn’t
follow any of above, then what did you do? Did you follow the same steps over
and over? If I ask you to do it over would you be able to perform the same task?
Be aware that others may have different approaches than you have in sorting the
cards. No matter how the intermediate work is done the result should be the
same- data is sorted. However one thing is common to every one. Data is scanned
over and over. This is why we need a systematic approach to programming.
Now let’s consider what would have happened if all ten cards were already sorted except one card? While there are different techniques to sort a list of data, one technique may be preferable due to circumstances. This is why consideration of the three sorting approaches (exchange, selection, insertion) may be helpful.