Data Structures and Algorithms with Object-Oriented Design Patterns in C#
next up previous contents index

Basics

Consider an arbitrary sequence tex2html_wrap_inline68688 comprised of of tex2html_wrap_inline58277 elements drawn from a some universal set U. The goal of sorting is to rearrange the elements of S to produce a new sequence, say S', in which the elements of S appear in order.

But what does it mean for the elements of S' to be in order? We shall assume that there is a relation, <, defined over the universe U. The relation < must be a total order, which is defined as follows:

Definition  A total order  is a relation, say <, defined on the elements of some universal set U with the following properties:
  1. For all pairs of elements tex2html_wrap_inline68712, exactly one of the following is true: i<j, i=j, or j<i.

    (All elements are commensurate ).

  2. For all triples tex2html_wrap_inline68720, tex2html_wrap_inline61093.

    (The relation < is transitive ).

In order to sort the elements of the sequence S, we determine the permutation tex2html_wrap_inline68728 of the elements of S such that

displaymath68686

In practice, we are not interested in the permutation P, per se. Instead, our objective is to compute the sorted sequence tex2html_wrap_inline68734 in which tex2html_wrap_inline68736 for tex2html_wrap_inline68738.

Sometimes the sequence to be sorted, S, contains duplicates. That is, there exist values i and j, tex2html_wrap_inline68746, such that tex2html_wrap_inline68748. In general when a sequence that contains duplicates is sorted, there is no guarantee that the duplicated elements retain their relative positions. That is, tex2html_wrap_inline68750 could appear either before or after tex2html_wrap_inline68752 in the sorted sequence S'. If duplicates retain their relative positions in the sorted sequence the sort is said to be stable . In order for tex2html_wrap_inline68750 and tex2html_wrap_inline68752 to retain their relative order in the sorted sequence, we require that tex2html_wrap_inline68760 precedes tex2html_wrap_inline68762 in S'. Therefore, the sort is stable if tex2html_wrap_inline68766.


next up previous contents index

Bruno Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.