<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0043)http://www.whisqu.se/per/docs/general18.htm -->
<HTML><HEAD><TITLE>Elementary Sorting Techniques</TITLE>
<META http-equiv=Content-Type content="text/html; charset=windows-1252">
<META content="MSHTML 6.00.2600.0" name=GENERATOR></HEAD>
<BODY text=#000000 vLink=#666699 aLink=#000000 link=#666699 bgColor=#ffffff>
<TABLE cellSpacing=0 cellPadding=5 width=640 bgColor=#666699 border=0>
<TBODY>
<TR>
<TD align=left width="90%" bgColor=#666699><FONT face=arial
color=#ffffff><B>Elementary Sorting Techniques</B></FONT> </TD>
<TD align=right bgColor=#000000><A
href="http://www.whisqu.se/per/docs/general.htm"><FONT face=arial
color=#ffffff><B>Back</B></A></FONT></TD></TR></TBODY></TABLE>
<CENTER><BR>
<CENTER>
<TABLE cellSpacing=0 cellPadding=10 border=0>
<TBODY>
<TR>
<TD><BR><BR><PRE>
Elementary Sorting Algorithms
There is a suprisingly diverse collection of algorithms that have been
developed to solve the apparently simple problem of "Sorting".
The general sorting problem is simple enough to describe: Given an
initially unordered array of N records, with one field distinguished as the
key, rearrange the records so they are sorted into increasing (or
decreasing) order, according to each record's key.
Sorting algorithms are used in all kinds of applications and are necessary,
for instance, if we plan to use efficient searching algorithms like Binary
Search or Interpolation Search, since these require their data to be
sorted.
Sorting algorithms are often subdivided into "elementary" algorithms that
are simple to implement compared to more complex algorithms that, while
more efficient, are also more difficult to understand, implement, and
debug.
It is not always true that the more complex algorithms are the preferred
ones. Elementary algorithms are generally more appropriate in the following
situations:
* less than 100 values to be sorted
* the values will be sorted just once
* special cases such as:
o the input data are "almost sorted"
o there are many equal keys
In general, elementary sorting methods require O(N2) steps for N random key
values. The more complex methods can often sort the same data in just O(N
log N) steps. Although it is rather difficult to prove, it can be shown
that roughly N log N comparisons are required, in the general case.
Internal vs. External Sorting
Normally, when considering a sorting problem, we will assume that the
number of records to be sorted is small enough that we can fit the entire
data set in the computer's memory (RAM) all at once. When this is true, we
can make use of an internal sorting algorithm, which assumes that any key
or record can be accessed or moved at any time. That is, we have "random
access" to the data.
Sometimes, when sorting an extremely large data set such as Canada's Census
Data, there are simply too many records for them to all fit in memory at
once. In this case, we have to resort to external sorting algorithms that
don't assume we have random access to the data. Instead, these algorithms
assume the data is stored on magnetic tapes or disks and only portions of
the data will fit in memory. These algorithms use "sequential access" to
the data and proceed by reading in, processing, and writing out blocks of
records at a time. These partially sorted blocks need to be combined or
merged in some manner to eventually sort the entire list.
Stability
When a sorting algorithm is applied to a set of records, some of which
share the same key, there are several different orderings that are all
correctly sorted. If the ordering of records with identical keys is always
the same as in the original input, then we say that the sorting algorithm
used is "stable".
This property can be useful. For instance, consider sorting a list of
student records alphabetically by name, and then sorting the list again,
but this time by letter grade in a particular course. If the sorting
algorithm is stable, then all the students who got "A" will be listed
alphabetically.
Stability is a difficult property to achieve if we also want our sorting
algorithm to be efficient.
Indirect Sorting
One final issue to keep in mind when implementing a sorting algorithm is
the size of the records themselves. Many sorting algorithms move and
interchange records in memory several times before they are moved into
their final sorted position. For large records, this can add up to lots of
execution time spent simply copying data.
A popular solution to this problem is called "indirect sorting". The idea
is to sort the indices of the records, rather than the records themselves.
---------------------------------------------------------------------------
</PRE></TD></TR></TBODY></TABLE></CENTER></CENTER></BODY></HTML>
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0043)http://www.whisqu.se/per/docs/general20.htm -->
<HTML><HEAD><TITLE>Comparison Of Sorting Algorithms</TITLE>
<META http-equiv=Content-Type content="text/html; charset=windows-1252">
<META content="MSHTML 6.00.2600.0" name=GENERATOR></HEAD>
<BODY text=#000000 vLink=#666699 aLink=#000000 link=#666699 bgColor=#ffffff>
<TABLE cellSpacing=0 cellPadding=5 width=640 bgColor=#666699 border=0>
<TBODY>
<TR>
<TD align=left width="90%" bgColor=#666699><FONT face=arial
color=#ffffff><B>Comparison Of Sorting Algorithms</B></FONT> </TD>
<TD align=right bgColor=#000000><A
href="http://www.whisqu.se/per/docs/general.htm"><FONT face=arial
color=#ffffff><B>Back</B></A></FONT></TD></TR></TBODY></TABLE>
<CENTER><BR>
<CENTER>
<TABLE cellSpacing=0 cellPadding=10 border=0>
<TBODY>
<TR>
<TD><BR><BR><PRE>
Comparison of Sorting Algorithms
The following table summarizes the basic strategies used in various sorting
algorithms, and lists the algorithms that use these strategies.
Comparison-Based Sorting Methods
Transposition (exchange adjacent values)
Bubble Sort **
Priority Queue (select largest value)
Selection Sort **
Heap Sort
Insert and Keep Sorted
Insertion Sort **
Tree Sort
Diminishing Increment
Shell Sort
Divide & Conquer
Quicksort
Merge Sort
Address-Calculation Sorting Methods
Radix Sort
Algorithms marked with ** have been discussed in class. Implementations of
some of these algorithms are available on the Pascal Page.
The diagrams below may help you develop an intuitive sense of how the
algorithms work. The vertical axis is the position within the array and the
horizontal axis is time. Values within the array are represented by small
squares with differing brightness. The goal of the algorithm is to sort the
values from darkest to lightest. In each diagram, the input array is
represented by a vertical column on the left, with an random assortment of
brightess values. (Click on an image to see a larger version.)
[bubble sort] [selection sort] [insertion sort] [quicksort]
bubble selection insertion quicksort
Bubble Sort exchanges adjacent values so lighter ones "bubble up" towards
the top, and darker ones "sink down" towards the bottom. Selection Sort
minimizes exchanges by scanning the unsorted portion to find the largest
remaining value on each iteration. Insertion Sort is familiar to anyone who
plays cards. It works by taking the next value from the unsorted portion
and inserting it into the already sorted portion of the array. Of these
three, Insertion Sort is the most efficient, on average, but Selection Sort
is preferred when the records are large. Bubble Sort is never preferred.
(Quicksort will be discussed later in this course.)
The following table summarizes what we have learned about the relative
efficiency of various sorting algorithms.
Bubble Sort (version discussed in class)
best case:
about N comparisons, 0 exchanges,
(input already sorted)
worst case:
about N^2 comparisons, N^2 exchanges,
(input sorted in reverse order)
average case:
quite close to worst case (difficult to analyze)
notes:
Very inefficient and should never be used. Uses an
excessive and unnecessary number of exchanges.
Bubble Sort (version in textbook)
best case:
about N^2/2 comparisons, 0 exchanges,
(input already sorted)
worst, average cases:
about N^2/2 comparisons, N^2/2 exchanges
Selection Sort
all cases:
about N^2/2 comparisons, N exchanges
notes:
minimizes the number of exchanges;
execution time quite insensitive to original ordering
of input data.
Insertion Sort
best case:
about N comparisons, 0 moves,
(input already sorted)
worst case:
about N^2/2 comparisons, N^2/2 moves,
(input sorted in reverse order)
average case:
about N^2/4 comparisons, N^2/4 moves
notes:
very efficient when input is "almost sorted";
moving a record is about half the work of exchanging
two records, so average case is equivalent to roughly
N^2/8 exchanges.
---------------------------------------------------------------------------
</PRE></TD></TR></TBODY></TABLE></CENTER></CENTER></BODY></HTML>
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0043)http://www.whisqu.se/per/docs/general19.htm -->
<HTML><HEAD><TITLE>Shell Sorting</TITLE>
<META http-equiv=Content-Type content="text/html; charset=windows-1252">
<META content="MSHTML 6.00.2600.0" name=GENERATOR></HEAD>
<BODY text=#000000 vLink=#666699 aLink=#000000 link=#666699 bgColor=#ffffff>
<TABLE cellSpacing=0 cellPadding=5 width=640 bgColor=#666699 border=0>
<TBODY>
<TR>
<TD align=left width="90%" bgColor=#666699><FONT face=arial
color=#ffffff><B>Shell Sorting</B></FONT> </TD>
<TD align=right bgColor=#000000><A
href="http://www.whisqu.se/per/docs/general.htm"><FONT face=arial
color=#ffffff><B>Back</B></A></FONT></TD></TR></TBODY></TABLE>
<CENTER><BR>
<CENTER>
<TABLE cellSpacing=0 cellPadding=10 border=0>
<TBODY>
<TR>
<TD><BR><BR><PRE>
Shell Sort
Shell Sort is the first sorting algorithm we'll look at that requires fewer
than O(N2) comparisons and exchanges, on average. Although it is easy to
develop an intuitive sense of how this algorithm works, it is very
difficult to analyze its execution time.
Shell Sort is really just an extension of Insertion Sort, with two
observations in mind:
* Insertion Sort is efficient if the input is "almost sorted".
* Insertion Sort is inefficient, on average, because it moves values
just one position at a time.
Shell Sort is similar to Insertion Sort, but it works by taking "bigger
steps" as it rearranges values, gradually decreasing the step size down
towards one. In the end, Shell Sort performs a regular Insertion Sort but
by then, the array of data is guaranteed to be "almost sorted".
Consider a small value that is initially stored in the wrong end of the
array. Using Insertion Sort, it will take roughly N comparisons and
exchanges to move this value all the way to the other end of the array.
With Shell Sort, we'll first move values using giant step sizes, so a small
value will move a long way towards it's final position, with just a few
comparisons and exchanges.
It's easiest to understand how Shell Sort works by looking at a specific
example. The table below shows what happens when we apply a version of
Insertion Sort that has been modified to use a step size of 4. (An asterisk
* indicates a value that has been exchanged.)
step size = 4
index input i=5i=6 i=7 i=8 i=9i=10 output
10 20 *26 26
9 28 *29 29
8 21 *22 22
7 25 25 25
6 23 *26 *23 23
5 27 *29 *28 28
4 22 *21 21
3 24 24 24
2 26 *23 *20 20
1 29 *27 27 27
As you can see, with a relatively small number of comparisons and
exchanges, smaller values (such as 20, 21) and larger values (such as 29)
have been moved a lot closer to their final sorted position.
Now that the array is a lot closer to being "almost sorted", we can apply
the usual Insertion Sort algorithm, with a step size of 1. In general, we
expect this final step to be quite efficient, although that may not be
apparent in this small example.
step size = 1
index input i=2 i=3i=4 i=5 i=6 i=7i=8 i=9 i=10 output
10 26 *29 29
9 29 29 *28 28
8 22 *28 28 *27 27
7 25 *28*27 *26 26
6 23 *28 *27*25 25 25
5 28 28 *27 *25*24 24
4 21 *27 27 *24 24*23 23
3 24 *27*24 *23 *22 22
2 20 *27 *24*21 21 21 21
1 27 *20 20 20 20
In general case, when the number of values to be sorted can be very large,
Shell Sort uses a sequence of diminishing step sizes. One popular sequence
is: ..., 1093, 364, 121, 40, 13, 4, 1, and this tends to work well in
practice.
A summary of the Shell Sort algorithm is given below. (A complete
implementation is given on the Pascal page.)
-----------------------------------------------------------------
procedure shellsort;
var
step : integer;
begin
step := 1;
repeat
step := 3*step+1
until step > n;
repeat
step := step div 3;
{ do insertion sort, ... }
{ ... with specified step size }
until step = 1;
end;
-----------------------------------------------------------------
The diagram below may help you develop an intuitive sense of how Shell Sort
actually works. The vertical axis is the position within the array and the
horizontal axis is time. Values in the array are represented by small
squares with differing brightness. The goal of the algorithm is to sort the
values from darkest to lightest. The input array is shown as the vertical
column on the left, with an initially random assortment of brightness
values. In this example, there are 64 values, and the step size sequence
is: 40, 13, 4, 1.
[shell sort]
shellsort
In the diagram above, a new "snapshot" of the partially sorted array was
output every time another N comparisons were completed, so the work done by
Shell Sort is roughly proportional to the area. Since the diagram is a
tall, thin rectangle, you can immediately see that significantly fewer than
N2 comparisons were needed for this example.
In general, Shell Sort is very difficult to analyze. In fact, no one has
been able to figure out a precise description of the execution time of
Shell Sort. For the implementation given above, it has been conjectured
that when N is large, the execution time is rougly proportional to N log2 N
or N1.25, but no one has been able to prove it.
---------------------------------------------------------------------------
[*] CompSci-1MD3
</PRE></TD></TR></TBODY></TABLE></CENTER></CENTER></BODY></HTML>
Paxal a écrit :
Je ne m'en sors pas: j'explique le pb:
Le but est de trier un tableau de chaines de caractères le plus rapidement possible!!!
Par tri fusion et compagnons recursifs, c'est pas possible, car aboutira a un outofmemory, vu que la ram est deja occupé au maximum! Commen tfaire un algo rapide sans recursivité et sans copie de tableaux! juste des mouvements dans le tableau!
freka
a écrit : Je croyais que je qsort devait etre un tri rapide?!
j'ai bien dit "m'a l'air" - je pourrais me tromper!), donc étant un défenseur de l'optimisation en taille, je ne peux que le recommander.
MadKeyboard a écrit :
Il existe un algorithme de tri, dont j'ai oublié le nom, et j'ai la flemme d'aller chercher mon "Algorithmes en C" en bas, qui est très efficace (quasi-linéaire, même), pour des clés peu diverses.
Par "clés", j'entends les éléments à trier.
Ca marche en gros comme ça (les détails, je les ai oubliés...) :
- on alloue un tableau d'entiers de la taille du nombre de clés différentes. Par exemple, si tu tries des bytes, tu alloues 256 entiers.
- on parcourt le tableau des données sources de gauche à droite... on compte le nombre d'occurences de chaque clé.
- ensuite, on utilise le tableau des occurences pour remplir le tableau source, et le tour est joué.
C'est valable si (taille de la chaîne) >> (nombre de clés différentes) et que (nombre de clés) << (espace mémoire)...
Je crois qu'une optimisation importante de l'algo est encore possible.
, c'est vrai que c'est rapide, mais par exemple sur un talbeua de chaine de caractère, ca ne serta rien c mort
