|
Sorting is generally considered to be one of the most
fundamental problems in computer science. It is said that about
a quarter of computer cycles used are spent sorting. So, a
suitable sorting method can improve computer working
efficiently. In this 20th century, there are many people studied
in how to improve the method, which is efficiently and suit
any case to solve the sorting problems. There are several
useful methods that usually to be used in computer. For example,
Insertion sort, Quicksort, Merge sort and so on. Each method
has its strengths and weaknesses and none is "universally"
efficient, the ideal of "adaptive sorting algorithms" or "input
sensitive algorithms" naturally arises. In the following
paper we take a point of view by considering
persorting algorithms i.e. planed to mixed two or more methods
cooperative to increasing the efficient of sorting. In general a
presorting algorithm especially for a simple as sorting, must
be simple and efficient. In the procedure of sorting in
computer that spent more times are "Compare" and "Move",
especially for "Compare". Compare spent more times than Move
(When the memory enough in computer). So, how to reduce the
numbers of comparison in sorting algorithms is very important.
We often use the average number of comparison to determine the
sorting algorithms. Because if we can reduced the average
number of comparison in sorting algorithm then we will
improve this sorting. In this paper we use two presorting
algorithms as follows to improve Quicksort algorithms.
[median-of-3] The optimal method for three element to find the
second ordered element. It takes 8/3 times
in average for finding second element.
[MI7 : Merge Insertion sort of seven elements] Merge Insertion
sort of seven elements, It takes 62784/5040
times in average in Merge Insertion sort of
seven elements. From a more
practical viewpoint, there is a different approach to these
problems. If we fix a sorting algorithm, we may ask questions as
how to tune it so that it is less input sensitive and, more
relevant to this paper, how topreproess inputs to increase the
average efficiency of the algorithm. We denote q is the
average number of comparison for Quicksort, q-3-∞ is the
average number of comparison for Quicksort using persorting
algorithm "median-of-3", q-MI7-∞ is the average number
of comparison for Quicksort using presorting algorithm
"MI7". We can introduce the following asymptotic
[Quicksort] => q ~ 2n log n
[Quicksort using median-of-3] => q-3-∞ ~ (1.714285714)n log n
[Quicksort using MI7] => q-MI7-∞~ (1.642228739)n log n
It is easily to show that Quicksort using median-of-3 is better
than Quicksort and Quicksort using MI7 is better than
Quicksort using median-of-3. In the end of this paper we provide
C language program and Maple language program. In our
machine test using these programs, we get the results as
follows. Quicksort using median-of-3 is better than Quicksort
about 30%. Quicksort using MI7 is better than Quicksort
using median-of-3 about 5%~10%, In general about 8%. Although,
Quicksort using MI7 is not a optimal sorting algorithm, but it
is really a good algorithm.
|