Lecture_09_Sorting.pdf

(143 KB) Pobierz
Microsoft Word - Lecture_09_Sorting.doc
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
x 1
x 2
x 3 x 4
x 5
x 6
x 7
?
2) „bubble-sort” method
x 1
x 2
x 3
x 4
x 5
x 6
x 7
?
do the same
for next number pairs
minimum
to the left
714114060.001.png 714114060.002.png
SORTING METHODS (cont.)
3) „quick-sort” method
x 1
x 2
x 3
x 4
x 5
x 6
x 7
lower than x 1
greater than x 1
==================================================
on the left
we are leaving
numbers lower than x 1
if not, than stop
on the right
we are leaving
numbers higher than x 1
if not, than stop
id++
exchange
iu--
x 1
x 2
x 3
x 4
x 5
x 6
x 7
==================================================
iu
id
x 1
x 2
x 3
x 4
x 5
x 6
x 7
exchange
714114060.003.png 714114060.004.png
/* Example 4.1 – SORTING TABLES – SIMPLE-SORT method */
#include <stdio.h>
#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 );
}

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin