Algorithmen

BinarySearch

      /********************************************************************
      *  Name:       binary search
      *  Zweck:      Binaere Suche in einem sortierten Array
      *  Prototyp:   int binary_search(int size, const int input[], int value);
      *  Parameter:  
      *     size:    (E) Anzahl an Werten in dem Array
      *     input:   (E) Vorsortiertes Array der Groesse size +1 in dem 
      *                  gesucht werden soll
      *     value:   (E) Der zu suchende Wert
      *  Funtionswert:  Der gesuchte Index oder -1 falls nicht gefunden
      ********************************************************************/
      
      int binary_search(int size, const int input[], int value)
      {
         const char false = 0, true = 1;
         int left, right, mid, found, res;
         
         left = 0;
         right = size-1;
         found = false;
         res = -1;
         
         while (!found && left <= right) {
            mid = (left + right) / 2;
            if (input[mid] == value)
               found = true;
            else if (input[mid] > value)
               right = mid-1;
            else 
               left = mid-1;
         }
         
         if (found)
            res = mid;
         
         return res;
      }

ShellSort

      /********************************************************************
      *  Name:       shellsort
      *  Zweck:      Sortieren durch Einfügen mit abnehmender Schrittweite
      *  Prototyp:   void shellsort(int v[], int n);
      *  Parameter:  
      *     n:       (E) Die zu sortierende Anzahl von Elementen in dem 
      *                  Array
      *     v:       (E/A) Array mit den zu sortierenden Elementen
      *  Funtionswert:  keiner
      ********************************************************************/
      
      void shellsort(int v[], int n)
      {
         int gap, i, j, tmp;
      
         for (gap = n/2; gap > 0; gap /= 2)
            for (i = gap; i < n, i++)
               for (j = i-gap; i >= 0 && v[j] > v[j+gap]; j-=gap) {
                  tmp = v[j];
                  v[j] = v[j+gap];
                  v[j+gap] = tmp;
               }
      }

SelectionSort

      /********************************************************************
      *  Name:       Selectionsort
      *  Zweck:      Sortieren eines Arrays durch direktes Auswählen
      *  Prototyp:   void selectionsort(int max, int *a);
      *  Parameter:
      *     max:     (E) Maximale Anzahl an zu sortierenden Elementen 
      *                 eines Arrays
      *     a:       (E/A) Zeiger auf das Array mit den zu sortierenden 
      *                    Elementen
      *  Funktionswert: keiner
      ********************************************************************/
      
      void selectionssort(int max, int *a)
      {
         int i, j, tmp;
         
         tmp = 0;
         
         for (i = 0; i < max-1; i++) {
            for (j = i+1; j < max; j++) {
               if (a[j] < a[i]) {
                  tmp = a[i];
                  a[i] = a[j];
                  a[j] = tmp;
               }
            }
         }
      }

BubbleSort

      /********************************************************************
      *  Name:       Bubblesort
      *  Zweck:      Sortieren eines Arrays durch direktes Austauschen
      *  Prototyp:   void bubblesort(int max, int *a);
      *  Parameter:
      *     max:     (E) Maximale Anzahl an zu sortierenden Elementen 
      *                 eines Arrays
      *     a:       (E/A) Zeiger auf das Array mit den zu sortierenden 
      *                    Elementen
      *  Funktionswert: keiner
      ********************************************************************/
      void bubblesort(int max, int *a)
      {
         int i, j, tmp;
         
         tmp = 0;
         
         for (i = 1; i < max; i++) {
            for (j = 0; j < max-i; j++) {
               if (a[j] > a[j+1]) {
                  tmp = a[j];
                  a[j] = a[j+1];
                  a[j+1] = tmp;
               }
            }
         }
         
      }
      
      
      /* Verbesserte Version: optimale Anpassung der Grenzen bei jedem Durchlauf,
      statt der Vertauschungen Verschiebungen wie bei der Einfügesortierung */
      
      void bubblesort(int max, float *a)
      {
         float save;
         int right, right_new, i;
         
         right = max -1;
         
         while (right > 0) {
            right_new = 0;
            for (i = 0; i < right; i++) {
               if (a[i] > a[i+1]) {
                  save = a[i];
                  while (i < right && save > a[i+1]) {
                     a[i] = a[i+1];
                     right_new = i;
                     i++;
                  }
                  a[i] = save;
               }
            right = right_new;
         }
      }