15

Insertion sort

  1. #include <stdio.h>
  2.  
  3. static void print( int tab[], const int siz ) {
  4.     int i;
  5.     for ( i=0; i < siz; i++ )
  6.         printf((i < siz-1) ? "%d, " : "%d\n", tab[ i ]);
  7. }
  8.  
  9. void sort( int tab[], const int siz ) {
  10.     /* insertion sort */
  11.     int i;
  12.     for ( i = 0; i < siz; i++ ) {
  13.         int j, v;
  14.  
  15.         print( tab, siz );
  16.  
  17.         v = tab[i];
  18.         /* insert tab[i] into sorted sublist */
  19.         for ( j = i - 1; j >= 0; j-- ) {
  20.             if ( tab[ j ] > v )
  21.                 break;
  22.             tab[ j + 1 ] = tab[ j ];
  23.         }
  24.         tab[ j + 1 ] = v;
  25.     }
  26. }
  27.  
  28. main() {
  29.     int tab[] = { 5, 9, 8, 2, 9, 1, 6, 4, 3, 7, 1 };
  30.     int siz = sizeof (tab) / sizeof (int);
  31.  
  32.     printf("Sorting %d integers:\n", siz);
  33.     sort( tab, siz );
  34.     print( tab, siz );
  35. }
$ 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
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. static void print( int tab[], const int siz ) {
  6.     int i;
  7.     for ( i=0; i < siz; i++ )
  8.         printf((i < siz-1) ? "%d, " : "%d\n", tab[ i ]);
  9. }
  10.  
  11. static int compint( const int *x, const int *y ) {
  12.     if ( *x == *y )
  13.         return 0;
  14.     return *x > *y ?  1 : -1;
  15. }
  16.  
  17. void sort( void *base, size_t nmemb, size_t siz, int(*compare)( const void *, const void * ) ) {
  18.     /* fake quick sort with an insertion sort */
  19.     unsigned char *p, *q;
  20.  
  21. #ifdef ALLOCA
  22.     unsigned char *v = (unsigned char *) alloca( siz );
  23. #else
  24.     unsigned char *v = (unsigned char *) malloc( siz );
  25. #endif
  26.  
  27.     for ( p = (unsigned char *) base; p < (unsigned char *) base + (nmemb * siz); p += siz ) {
  28.         memcpy( v, p, siz );
  29.         /* insert v into sorted sublist */
  30.         for ( q = p - siz; q >= (unsigned char *) base; q -= siz ) {
  31.             if ( compare( v, q ) == -1 )
  32.                 break;
  33.             memcpy( (q + siz), q, siz );
  34.         }
  35.         memcpy( (q + siz), v, siz );
  36.     }
  37.  
  38. #ifndef ALLOCA
  39.     free(v);
  40. #endif
  41. }
  42.  
  43. main() {
  44.     int tab[] = { 5, 9, 8, 2, 9, 1, 6, 4, 3, 7, 1 };
  45.     int nmemb = sizeof (tab) / sizeof (int);
  46.  
  47.     printf("Sorting %d integers:\n", nmemb);
  48.     print( tab, nmemb );
  49.     sort( (void *)tab, nmemb, sizeof (int), (int (*)(const void *,const void *))compint );
  50.     print( tab, nmemb );
  51. }
$ 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

Your comment:
[p] [b] [i] [u] [s] [quote] [pre] [br] [code] [url] [email] strip help 2000

Enter a maximum of 2000 characters.
Improve the presentation of your text with the following formatting tags:
[p]paragraph[/p], [b]bold[/b], [i]italics[/i], [u]underline[/u], [s]strike[/s], [quote]citation[/quote], [pre]as is[/pre], [br]line break,
[url]http://www.izend.org[/url], [url=http://www.izend.org]site[/url], [email]izend@izend.org[/email], [email=izend@izend.org]izend[/email],
[code]command[/code], [code=language]source code in c, java, php, html, javascript, xml, css, sql, bash, dos, make, etc.[/code].