The Folklore of Sorting Algorithms

IJCSI International Journal of Computer Science Issues, Vol. 4, No. 2, 2009

The above sequence a = 5, 7, 4, 9, 7 has the inversion
sequence v = 0, 0, 2, 0, 1.

We now count the inversions (i, j) of a sequence a
separately for each position j. The resulting value of vj
gives the number of elements ai to the left of aj which are
greater than α₇∙. Obviously, we have v_i _ i for all
i = 0, ..., n-1. If all v_i are 0, then and only then the
sequence a is sorted. If the sequence a is a permutation,
then it is uniquely determined by its inversion sequence v.
The permutation n-1, ..., 0 has inversion sequence 0, ..., n-
1.

Let a = a0, ..., an-1 be a sequence and v = v0, ..., vn-1 be its
inversion sequence. Then the number of steps T (a)
required by insertion sort to sort sequence a is

T (a) = Ï i = o, ..., n-1 v_i                            (2)

Obviously, insertion sort takes v_i steps in each iteration i.
Thus, the overall number of steps is equal to the sum of all
vi. This can be proved by an example: The following table
shows the sequence a of the first example and its
corresponding inversion sequence. For instance, v₅ = 4
since 4 elements to the left of a5 = 2 are greater than 2
(namely 5, 7, 3 and 4). The total number of inversions is
17.

Table 1: Inversion Table

It is seen that insertion sort requires 17 steps to sort this
sequence.Thus the folklore 3 can be converged in to a
theorem as, Theorem 3 : The sorting algorithm
insertion sort has a worst case time complexity of
T(n) = n∙(n-1)/2 comparison-exchange steps to sort a
sequence of n data elements.

4.4 Folklore 4: Any comparison sort type of
algorithm requires lower bound comparisons in the
worst case.

Proof 4: From the folklore 2, it suffices to determine the
height of a decision tree in which each permutation
appears as a leaf. Consider a decision three of height h and
l leaves corresponding to a comparison sort on n elements.
Because each of the n! permutations of the input appear as
some leaf, we have n! ≤ l.

Since a binary tree of height h has no more than 2h leaves,
we have to conclude that n! ≤ l ≤ 2 , which by taking
logarithms , implies h ≥ log(n!) (Since the log function is
monotonically increasing).

Therefore,

h ≥ log(n!)

= log (n.n1.n2....2.1)

= log n + log (n1) + log (n2) + ... + log2 + log1

> log n + log (n1) + log(n2) + ... + log(n/2)

> log (n/2) + log (n/2) + ... + log (n/2)

= n/2 log (n/2)

= n/2logn - n/2

= Ω (n log n)                                       (3)

This folklore can be converged in to new theorem as,
Theorem 4: any comparison sort algorithm requires
Ω (n log n) comparisons in the worst case.

5. Some Convergence of Theorems into
Folklore

Now we take a theorem and show that it is a piece of
folklore. We know that time needed for these algorithms
like selection sort varies like N². [12]. Let’s deduce
folklore form this.

5.1 Deduction 1:

Algorithms like selection sort, takes each unsorted list and
goes through each item in order to identify the
smallest. The first unsorted list consists of all N items in
the original, and each successive unsorted list is one
smaller, as the smallest item each time is placed in its
correct position. So the first search for the smallest will
take N operations, the next search for the smallest will
take N-1 operations, the next N-2 operations, and so on
until the last search for the smallest take 2 operations (we
don't need to search when the list has only one
item). Thus the time needed will be a constant times the
following sum:

N + (N-1) + (N-2) + ... + 3 + 2 + 1          (4)

(We include the 1 to create a sum for which a standard
formula applies; it adds only a small constant which does
not affect the overall result.)

This sum, the sum of the first N integers, is known to be N
(N+1) / 2, which is approximately N²/2. Since we know
that this is multiplied by some constant representing the
time the operations take on a specific machine, we can see
that the time needed for this algorithm varies like N², the
square of the amount of data. Thus the time needed for
the selection sort algorithm behaves like; each time the

IJCSI

<<   <   2   3   4   5   6