[WikiDyd] [TitleIndex] [WordIndex

To jeszcze nie jest gotowe

Algorytmy i struktury danych

Sortowanie

1. Proste algorytmy sortowania (złożoność O(n*n) )

Makro do zamiany dwoch el. wektora double:

  #define swap( V, i, j ) {  \
       double tmp= (v)[(i)]; \
      (v)[(i)]= (v)[(j)];    \
      (v)[(j)]= tmp;         \
  }

1.1. Sortowanie bąbelkowe

   1   void bublesort( double v[], int n ) {
   2     int bylazamiana;
   3 
   4     do {
   5       register int i;
   6 
   7       bylazamiana= 0;
   8 
   9       for( i= 1; i < n; i++ )
  10         if( v[i] < v[i-1] ) {
  11           swap( v, i, i-1 );
  12           bylazamiana= 1;
  13         }
  14     } while( bylazamiana );
  15   }

1.2. Sortowanie przez wybieranie

   1   void choosesort( double v[], int n ) {
   2     register int i,j;
   3     for( i= 0; i < n-1; i++ ) {
   4       register int min= i;
   5       for( j= i+1; j < n; j++ )
   6         if( v[j] < v[min] )
   7           min= j;
   8       swap( v, i, min );
   9     }
  10   }

1.3 Sortowanie przez wstawianie

   1   void insertsort( double v[], int n ) {
   2     register int i,j;
   3     for( i= 1; i < n; i++ ) {
   4       double tmp= v[i];
   5       for( j= i-1; j >= 0 && v[j] > tmp; j-- )
   6         v[j+1]= v[j];
   7       v[j+1]= tmp;
   8     }
   9   }

1.4 Sortowanie Shella

   1   void shellsort( double v[], int n ) {
   2      register int i,j;
   3      register int gap= 1;
   4 
   5      while( gap <= n/9 )
   6        gap= 3*gap + 1; /* Ustalamy maks. gap 
   7                           - ciag zalecany przez Knuth'a dla n <= 1000 */
   8 
   9      for( ; gap >= 1; gap /= 3 )
  10        for( i= gap; i < n; i++ ) {
  11          double tmp= v[i];
  12          for( j= i-gap; j >= 0 && v[j] > tmp; j-= gap )
  13            v[j+gap]= v[j];
  14          v[j+gap]= tmp;
  15        }
  16   }

2. Algorytmy optymalne (złożoność O(n*log_2(n)))

2.1 Sortowanie szybkie (najlepszy znany algorytm oparty na porównywaniu elementów)

   1   int rozdziel( double a[], int s, int k ) {
   2   /* rozdziela wektor a wzgledem a[0],
   3      zwraca pozycje a[0] w wektorze wynikowym */
   4      
   5      int i, j;
   6      double tmp;
   7 
   8      j= s;
   9      for( i= s+1; i <= k; i++ )
  10         /* niezmiennik: a[s+1..j] < a[s] i a[j+1..i-1] >= a[s] */
  11         if( a[i] < a[s] ) {
  12            tmp= a[++j]; a[j]= a[i]; a[i]= tmp;
  13         }
  14      tmp= a[j];
  15      a[j]= a[s];
  16      a[s]= tmp;
  17      return j;
  18   }
  19 
  20   void mqsort( double a[], int s, int k ) {
  21   /* sortuje in situ, rosnaco a[s..k] */
  22      if( s < k ){
  23         int j= rozdziel( a, s, k );
  24         mqsort( a, s, j-1 );
  25         mqsort( a, j+1, k );
  26      }
  27   }
  28 
  29   void quicksort( double a[], int na ) {
  30      mqsort( a, 0, na-1 );
  31   }

   1   #define MAXS 1024  /* maksymalna gleb. stosu */
   2 
   3   void mqsort( double a[], int s, int k ) {
   4   /* sortuje in situ, rosnaco a[s..k] */
   5 
   6      int ss[MAXS], ks[MAXS], sp= 0;  /* ss <- "poczatki",
   7                                         ks <- "konce" pod-wektorow */
   8      if( s < k ){
   9         ss[0]= s;
  10         ks[0]= k;
  11         sp= 1;
  12         while( sp ) {
  13            int bs= ss[--sp];
  14            int bk= ks[sp];
  15            int j= rozdziel( a, bs, bk );
  16            if( j-1 > bs ) {
  17               ss[sp]= bs;
  18               ks[sp++]= j-1;
  19            }
  20            if( k > j+1 ) {
  21               ss[sp]= j+1;
  22               ks[sp++]= bk;
  23            }
  24         }
  25      }
  26   }

2.2 Sortowanie stogowe

Zagadnienia wstępne:

   1     typedef struct {
   2       Data d;          /* jakiekolwiek dane */
   3       int key;         /* klucz porządkujący */
   4     } Elem;
   5 
   6     typedef Elem * Heap;  /* stog jest tablica elementów */
   7 
   8     #define swap( h, i, j ) { Elem tmp= (h)[(i)]; (h)[(i)]= (h)[(j)]; (h)[(j)]= tmp; }
   9 

   1       void heap_up( Heap s, int n ) {
   2         int i= n;
   3         int p= (i-1)/2;
   4 
   5         while ( i > 0 && s[p].key > s[i].key )
   6         {
   7                 swap( s, p, i );
   8                 i= p;
   9                 p= (i-1)/2;
  10         }
  11       }

   1       void heap_down( Heap s, int n ) {
   2 
   3         int p= 0;
   4         int d= 2*p+1;
   5 
   6         while ( d < n )
   7         {
   8                 if( d+1 < n && s[d+1].key < s[d].key )
   9                         d++;
  10                 if( s[p].key < s[d].key )
  11                         return;
  12                 swap( s, p, d );
  13                 p= d;
  14                 d= 2*p+1;
  15         }
  16       }

   1   void hsort(void *t, int n, size_t s, int (* cmpf)(const void *, const void *))
   2   {
   3     int i;
   4     int b, p;
   5     char *tmp = malloc(s);
   6     char *v = t;
   7 
   8     int k;
   9 
  10     for (i = 1; i < n; i++)
  11     {
  12       /* dogory(t[i]... */
  13       b = i;
  14       p = (n-1)/2;
  15 
  16       while (cmpf(v+p*s, v+b*s) < 0) {
  17         memcpy(tmp, v+p*s, s);
  18         memcpy(v+p*s, v+b*s, s);
  19         memcpy(v+b*s, tmp, s);
  20 
  21         b = p;
  22         p = (b-1)/2;
  23       }
  24 
  25       for (k = 0; k <= i; k++)
  26         printf("%g ", *(float *)(v+k*s));
  27       printf("\n");
  28     }
  29 
  30     for (i = 0; i < n; i++)
  31       printf("%g ", *(float *)(v+i*s));
  32     printf("\n");
  33 
  34     for (i = n-1; i > 0; i--) {
  35       memcpy(tmp, v, s);
  36       memcpy(v, v+i*s, s);
  37       memcpy(v+i*s, tmp, s);
  38 
  39       b = 0;
  40       p = 2*b+1;
  41 
  42       while (p < i) {
  43         if (p+1 < i && cmpf(v+(p+1)*s, v+p*s) > 0)
  44           p++;
  45         if (cmpf(v+p*s, v+b*s) <= 0)
  46           break;
  47 
  48         memcpy(tmp, v+p*s, s);
  49         memcpy(v+p*s, v+b*s, s);
  50         memcpy(v+b*s, tmp, s);
  51         b = p;
  52         p = 2*b+1;
  53       }
  54     }
  55   }

Zagadnienia dodatkowe:


2015-09-23 06:32