LECTURE 9
Sorting algorithms
(sorting elements of files or tables)
Programs: e4_1.c ...... e4_3.c
Tomasz Zieliński
SORTING METHODS
1)  simple-sort method
minimum
x1 x2 x3 x4 x5 x6 x7
?
2)  bubble-sort method
x1 x2 x3 x4 x5 x6 x7
? do the same
for next number pairs
minimum
to the left
SORTING METHODS (cont.)
3)  quick-sort method
x1 x2 x3 x4 x5 x6 x7
lower than x1 greater than x1
==================================================
on the left on the right
we are leaving we are leaving
numbers lower than x1 numbers higher than x1
if not, than stop if not, than stop
exchange
id++ iu--
x1 x2 x3 x4 x5 x6 x7
==================================================
iu id
x1 x2 x3 x4 x5 x6 x7
exchange
/* Example 4.1  SORTING TABLES  SIMPLE-SORT method */
#include
#define DIM 11
void sort( int data[ ], int N ); // sorting function
int minim( int data[ ], int start, int N ); //  find minimum function
/* main program -------------------------------------------------------------------- */
void main()
{
int tab[ DIM ] = { 0, 9, 2, 7, 4, 5, 6, 3, 8, 1, 10 };
int i;
sort( tab, DIM ); /* sort data -------------- */
for( i=0; i < DIM; i++) /* print result of sorting */
printf(" %d \n", tab[ i ] );
}
/* auxiliary functions -------------------------------------------------------------- */
void sort( int data[ ], int N )
{
int x, i, j;
for( i=0; i < N-1; i++ ) // repeat for i = 0, 1, 2, ..., N-2
{ // find index j of the sample with min
j = minim( data, i+1, N ); // value lying above data[i]
if ( data[ j ] < data[ i ]) // exchange data[i] and data[j],
{ // if data[ j ] < data[ i ]
x = data[ i ];
data[ i ] = data[ j ];
data[ j ] = x;
}
}
}
/* ---------------------------------------------------------------------------------------- */
/* Find index  i of the sample, i = start, ..., N, */
/* for which value of data[ i ] is the smallest */
/* ---------------------------------------------------------------------------------------- */
int minim( int data[ ], int start, int N )
{
int i, imin, vmin;
imin = start; // minimum index = start
vmin = data[ start ]; // minimum value = data[start]
for( i = start+1; i < N; i++ ) // next element of the table
{
if (vmin > data[i] ) // if lower than min,
{
imin=i; vmin = data[ i ]; // then it will be a new minimum
}
}
return( imin );
}
/* Example 4.2 - SORTING TABLES  BUBBLE-SORT method */
#include
#define DIM 11 /* number of elements in a table */
#define NO 0
#define YES 1
void sort( int data[ ], int N ); /* sorting function */
/* main program -------------------------------------------------------------------- */
void main()
{
int tab[ DIM ] = { 0, 9, 2, 7, 4, 5, 6, 3, 8, 1, 10 };
int i;
sort( tab, DIM ); /* sort data */
for( i=0; i < DIM; i++) /* result of sorting */
printf(" %d \n", tab[ i ] );
}
/* Auxiliary function --------------------------------------------------------------- */
void sort( int data[ ], int N )
{
int x, i, j, repeat = YES;
for( i=0; (i < N-1) && repeat==YES; i++ ) // waves of  bubbles
{ repeat = NO;
for( j=0; j < N-i-1; j++) // if wrong order
{ if (data[ j ] > data[ j+1 ]) // then  bubble ,
{ repeat = YES; // i.e. exchange positions
x = data[ j ];
data[j] = data[j+1];
data[j+1] = x;
}
}
}
}
/* PROGRAM DESCRIPTION
1) The algorithm consists of so-called  waves of bubbles .
2) In each wave every two neighboring elements, i.e. (0 and 1), (1 and 2), (2 and 3), ... are
compared in succession and their positions are exchanged ( bubble !), if the element with
smaller index has greater value.
3) After each  wave of bubbles the greatest element is shifted to the end of file (or table).
Therefore each next  wave of bubbles is one element shorter.
4) If in a  wave there is no  bubble , it means that all elements lie in order: they start from the
smallest element and end with the biggest one.
5) Therefore the next  wave of bubbles is performed only when there was at least one
 bubble in the previous wave and no all waves were done (for N element file N-1 waves
can be performed).
6) Before the biggest value is found and taken into comparison,  bubbling causes initial
sorting of smaller values lying in front of it. After that the biggest value is a winner in all
remaing comparisons and is shifted to the end of file (table).
7) If the file is already sorted, only one empty  wave of bubbles is performed (no exchange of
element positions is done).
*/
/* Example 4.3a - SORTING TABLES */
/* - fast method - QUICK-SORT */
/* - recursive version */
#include
#define DIM 11 // number of elements in a table
void sort( int data[ ], int down, int up ); // sorting function
void display( int data[ ], int N ); // display result
/* main program -------------------------------------------------------------------- */
void main()
{
// int tab[ DIM ] = { 0,9,2,7,4,5,6,3,8,1,10 }; /* ver.1 */
int tab[ DIM ] = { 25,57,48,37,12,92,86,33,5,66,77 }; /* ver.2 */
sort( tab, 0, DIM-1 );
display( tab, DIM );
}
/* Display function ------------------------------------------------------------------ */
void display( int data[ ], int N )
{
int i;
for( i=0; i < N; i++)
printf(" %2d ", data[ i ] );
}
/* Sorting function ----------------------------------------------------------------- */
// Sort elements of the table data[], starting from index down
// and finishing with index up
void sort( int data[ ], int down, int up )
{
int id, iu; // work indexes: down and up
int a, x; // id is going up (id -->) and iu is going down ( <-- iu)
id = down; iu = up; a = data[ down ]; // initialization of id, iu, a
while ( id < iu ) // divide
{ // file
while ( (data[ id ] <= a) && (id < up) ) id++; // into two sets of
while ( (a < data[ iu ] ) && (down < iu ) ) iu--; // elements that are
if ( id < iu ) // lower
{ // or
x = data[ id ]; // greater
data[ id ] = data[ iu ]; // than
data[ iu ] = x; // the first
} // element
} //
data[ down ] = data[ iu ]; //
data[ iu ] = a; //
if ( down < iu-1 ) sort( data, down, iu-1 ); // now sort below
if ( iu+1 < up ) sort( data, iu+1, up ); // and then above
}
/* PROGRAM DESCRIPTION
1) Index id  goes up when below it is left element lower or equal to a=data[down] and when
there are still elements above it. At one moment its movement  up is stopped by the first
element greater than a=data[down].
2) Index iu  goes down when above it is left element greater than a=data[down] and when
there are still elements below it. At one moment its movement is stopped by the first
element lower than a=data[down].
3) In this situation the position of  blocking elements is changed: too big is shifted up and too
small is shifted down.
4) After  unblocking , indexes id and iu start again to move until the condition id < iu is fulfilled.
5) When the condition id < iu is not fulfill, index iu is pointing to the last element lower then
a=data[down]. Therefore position of elements data[down] and data[iu] is exchanged.
6) Next, the function is recursively executed on two sets of elements, having indexes lower
than iu [down, iu-1] and greater than iu [iu+1, up].
*/
/* Example 4.4a - SORTING TABLES */
/* - fast method - QUICK-SORT */
// Nonrecursive version using a table as a static stack
// WARNING: analyze the program after lecture 10
#include
#include
#include
/* definition of data structures ---------------------------------------------------- */
#define DIM 11 // number of elements to be sorted
#define MAXSTACK 1000 // size of the program stack
#define YES 1
#define NO 0
struct typedu // definition of new variable type typedu
{ // each complex variable of this type
int down; // will consists of two numbers, e.g.
int up; // struct typedu x; // declaration
}; // x.down = 0; x.up = 10; // initialization
struct typestack // definition of new variable type typestack
{ // e.g. struct typestack x;
int top; // x.top = -1;
struct typedu borders[ MAXSTACK ]; // x.borders[0].down = 0;
}; // x.borders[0].up = 0;
/* declaration of functions calling ------------------------------------------------ */
int emptyStack( struct typestack *ps );
void toStack( struct typestack *ps, struct typedu *pdu );
void fromStack( struct typestack *ps, struct typedu *pdu );
void sort( int data[ ], int N );
void division( int data[ ], int down, int up, int *center );
void display( int data[ ], int N );
/* main program -------------------------------------------------------------------- */
void main()
{
// int tab[ DIM ] = { 0,9,2,7,4,5,6,3,8,1,10 }; /* ver.1 */
int tab[ DIM ] = { 25,57,48,37,12,92,86,33 }; /* ver.2 */
int i;
sort( tab, DIM );
display( tab, DIM );
}
/* Auxiliary functions ------------------------------------------------- */
void sort( int data[ ], int N )
{
int i, j;
struct typedu newdu; // declaration of variable newdu
struct typestack stack; // declaration of variable stack
stack.top = -1; // stack is empty
newdu.down = 0; // lower index of table to be sorted
newdu.up = N-1; // upper index of table to be sorted
toStack( &stack, &newdu ); // store on stack
printf(" " );
for( i=0; i < N; i++) // auxiliary display
printf(" %2d ", i );
printf("\n");
while( !emptyStack( &stack ) ) /* repeat */
/* first SMALLER sub-tables */
{
fromStack( &stack, &newdu ); /* take from stack down and up */
while ( newdu.up > newdu.down ) /* first SMALLER sub-table */
{
printf(" d=%2d g=%2d ", newdu.down, newdu.up );
display( data, N ); /* actual order */
division( data, newdu.down, newdu.up, &j);
printf(" s=%2d\n", j ); /* returned value of center */
if ( j-newdu.down > newdu.up-j )
{ /* write on stack lower GREATER sub-table */
i = newdu.up;
newdu.up = j-1;
toStack( &stack, &newdu );
/* process upper SMALLER sub-table */
newdu.down = j+1;
newdu.up = i;
}
else
{ /* write on stack upper GREATER sub-table */
i = newdu.down;
newdu.down = j+1;
toStack( &stack, &newdu );
/* process lower SMALLER sub-table */
newdu.down = i;
newdu.up = j-1;
} /* end if */
} /* end while up > down */
} /* end while emptyStack */
printf(" " );
} /* end sort */
/* File division ------------------------------------------------------------------------ */
/* function exchanges order of elements, return center index = median */
/* it is identical as in program e4_3a.c */
void division( int data[ ], int down, int up, int *center )
{
int a, id, iu, x;
a = data[ down ]; /* we are looking for new position of this element */
id = down; /* lower work index */
iu = up; /* upper work index */
while( id < iu )
{
while( (data[ id ] <= a) && (id < up) )
id++; /* go up */
while( (data[ iu ] > a) && (iu > down) )
iu--; /* go down */
if ( id < iu )
{
x = data[ id ]; /* exchange positions */
data[ id ] = data[ iu ]; /* of elements */
data[ iu ] = x; /* if id < iu */
}
}
data[ down ] = data[ iu ]; /* final exchange */
data[ iu ] = a; /* down <--> iu */
*center = iu; /* return index of a center */
}
/* OPERATIONS ON THE STACK ---------------------------------------------- */
int emptyStack( struct typestack *ps )
{
if ( ps->top == -1 ) // writing: *ps.top = ps->top
return( YES );
else
return( NO );
}
/* ------------------------------------------------------------------------------ */
void fromStack( struct typestack *ps, struct typedu *pdu )
{
if ( emptyStack(ps) )
{
printf("Stack is empty !\n"); exit(1);
}
pdu->down = ps->borders[ ps->top ].down;
pdu->up = ps->borders[ ps->top ].up;
(ps->top)--;
} // *ps.borders[ *ps.top ].down
// *ps.borders[ *ps.top ].up
/* ------------------------------------------------------------------------------ */
void toStack( struct typestack *ps, struct typedu *pdu )
{
if (ps->top == MAXSTACK-1)
{
printf("Error! Stack is full!\n"); exit(1);
}
else
{
(ps->top)++; // (*ps.top)++
ps->borders[ ps->top ].down = pdu->down; // as above
ps->borders[ ps->top ].up = pdu->up; // as above
}
}
/* PROGRAM DESCRIPTION
As one can see, programming the algorithm QuickSort is much more complicated when no
recursion is used. After putting the first table element in a proper place we have to repeat the
 division operation on two files (sets) of elements: lying below and above the already
positioned element. Start/down and stop/up indexes of the bigger file are stored on the software
stack and smaller file is next processed.
While the condition:
while ( newdu.up > newdu.down )
is not fulfilled, we start to take (pop) from stack remembered lower and higher indexes of sub-
tables that are still to be sorted:
fromStack( &stack, &newdu );
Function ends when stack is empty:
while( !emptyStack( &stack ) ) {  go Johny, go ! }.
In the begining we push to stack lower and upper index of the whole table:
stack.top = -1; // stack is empty
newdu.down = 0; // lower index of the table to be sorted
newdu.up = N-1; // higher index of the table to be sorted
toStack( &stack, &newdu ); // push to stack
Stack structure is shown in figure below.
Parameter top is pointing out to last  multiple variable of the type down/up that was stored in
the table borders[ ].
top
d0 u0
d1 u1
d2 u2
d3 u3
borders[ MAXSTOS ]
down up
*/