19
Insertion sort
- #include <stdio.h>
- static void print( int tab[], const int siz ) {
- int i;
- for ( i=0; i < siz; i++ )
- printf((i < siz-1) ? "%d, " : "%d\n", tab[ i ]);
- }
- void sort( int tab[], const int siz ) {
- /* insertion sort */
- int i;
- for ( i = 0; i < siz; i++ ) {
- int j, v;
- print( tab, siz );
- v = tab[i];
- /* insert tab[i] into sorted sublist */
- for ( j = i - 1; j >= 0; j-- ) {
- if ( tab[ j ] > v )
- break;
- tab[ j + 1 ] = tab[ j ];
- }
- tab[ j + 1 ] = v;
- }
- }
- main() {
- int tab[] = { 5, 9, 8, 2, 9, 1, 6, 4, 3, 7, 1 };
- int siz = sizeof (tab) / sizeof (int);
- printf("Sorting %d integers:\n", siz);
- sort( tab, siz );
- print( tab, siz );
- }
$ gcc -o insertion insertion.c
$ ./insertion
Sorting 11 integers:
5, 9, 8, 2, 9, 1, 6, 4, 3, 7, 1
5, 9, 8, 2, 9, 1, 6, 4, 3, 7, 1
9, 5, 8, 2, 9, 1, 6, 4, 3, 7, 1
9, 8, 5, 2, 9, 1, 6, 4, 3, 7, 1
9, 8, 5, 2, 9, 1, 6, 4, 3, 7, 1
9, 9, 8, 5, 2, 1, 6, 4, 3, 7, 1
9, 9, 8, 5, 2, 1, 6, 4, 3, 7, 1
9, 9, 8, 6, 5, 2, 1, 4, 3, 7, 1
9, 9, 8, 6, 5, 4, 2, 1, 3, 7, 1
9, 9, 8, 6, 5, 4, 3, 2, 1, 7, 1
9, 9, 8, 7, 6, 5, 4, 3, 2, 1, 1
9, 9, 8, 7, 6, 5, 4, 3, 2, 1, 1- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- static void print( int tab[], const int siz ) {
- int i;
- for ( i=0; i < siz; i++ )
- printf((i < siz-1) ? "%d, " : "%d\n", tab[ i ]);
- }
- static int compint( const int *x, const int *y ) {
- if ( *x == *y )
- return 0;
- return *x > *y ? 1 : -1;
- }
- void sort( void *base, size_t nmemb, size_t siz, int(*compare)( const void *, const void * ) ) {
- /* fake quick sort with an insertion sort */
- unsigned char *p, *q;
- #ifdef ALLOCA
- unsigned char *v = (unsigned char *) alloca( siz );
- #else
- unsigned char *v = (unsigned char *) malloc( siz );
- #endif
- for ( p = (unsigned char *) base; p < (unsigned char *) base + (nmemb * siz); p += siz ) {
- memcpy( v, p, siz );
- /* insert v into sorted sublist */
- for ( q = p - siz; q >= (unsigned char *) base; q -= siz ) {
- if ( compare( v, q ) == -1 )
- break;
- memcpy( (q + siz), q, siz );
- }
- memcpy( (q + siz), v, siz );
- }
- #ifndef ALLOCA
- free(v);
- #endif
- }
- main() {
- int tab[] = { 5, 9, 8, 2, 9, 1, 6, 4, 3, 7, 1 };
- int nmemb = sizeof (tab) / sizeof (int);
- printf("Sorting %d integers:\n", nmemb);
- print( tab, nmemb );
- sort( (void *)tab, nmemb, sizeof (int), (int (*)(const void *,const void *))compint );
- print( tab, nmemb );
- }
$ gcc -o fakeqsort -DALLOCA fakeqsort.c
$ ./fakeqsort
Sorting 11 integers:
5, 9, 8, 2, 9, 1, 6, 4, 3, 7, 1
9, 9, 8, 7, 6, 5, 4, 3, 2, 1, 1
Comments