|
Introduction
This chapter helps you to understand:
- What Is Sorting?
- Why Sorting
- Sorting Algorithms
What Is Sorting?
Sorting is to organize a collection of data elements based on the order of a comparable
property of each element.
There are three concepts in this definition:
- "Data element": A unit of information.
- "Comparable property": A property in each element that can be used to compare element A
with element B. The comparison must give
one of three possible results: 1. A is in higher order than B; 2. A is in equal order as B;
3. A is in lower order than B.
- "Collection": Sorting works on a collection of data elements, not on a single
data element.
Examples of sorting:
A yellow-page book:
- Data element: A business name, its phone number, and possibly its address.
- Comparable property: The alphabetical sequence of the business name.
- Collection: All businesses that registered in the yellow book.
An English dictionary:
- Data element: An English word, its pronunciation, and its meanings.
- Comparable property: The alphabetical sequence of the word.
- Collection: All words collected in the dictionary.
Warning: For certain types of data elements, the comparable property is not so easy to find.
For example, what is the comparable property that can be used to sort the characters in
a Chinese dictionary?
Why Sorting?
Sorting makes it possible to search a particular data element in a collection quickly
by applying the binary search technique.
Everyone knows what is the binary search technique?
We are using it every time when we look up a word in a dictionary.
How much time we can save by using the binary search technique?
Let's do a rough calculation. Assume that we have a sorted dictionary and
an un-sorted dictionary with the same collection of words printed on about 1000 pages.
Looking up a word in the un-sorted dictionary, the best case is that you found the word
on the first page; the worst case is that you looked through all 1000 the pages, and found
the word on the last page. So roughly the average time you spend is checking 500 pages.
Looking up a word in the sorted dictionary, the best case is that you found the word on
the center page, which is the first page you will be checking based on the binary search
technique; the worst case is that you found the word on the final page after you have
divided the dictionary 10 times. So roughly the average time you spend is checking 5 pages.
The answer is obvious. We are saving about 99% of our time by using the sorted dictionary!
Sorting Algorithms
There are many sorting algorithms have been developed over the years. I will only try
to cover the following popular ones:
- Selection Sort
- Insertion Sort
- Bubble Sort
- Quicksort
- Merge Sort
- Heap Sort
- Shell Sort
| 