suche: laufzeitanalyse bogo-sort

TheTester

tach...

hat jmd grad mal die laufzeitanalyse von bogo-sort zur hand? es muss glaub ich was mit n! sein bin zu faul das jetzt selbst zu machen *gg*

bye

tt

Bubble sort - O(n2)
Cocktail sort (bidirectional bubble sort) - O(n2)
Comb sort * - O(n log n)
Selection sort - O(n²)
Insertion sort - O(n²)
Bucket sort - O(n); requires O(n) extra memory
Counting sort - O(n+k); requires O(n+k) extra memory
Heapsort * - O(n log n)
Smoothsort * - O(n log n)
Merge sort - O(n log n)
Quicksort * - O(n log n)
Binary tree sort - O(n log n); requires O(n) extra memory
Pigeonhole sort - O(n+k); requires O(k) extra memory
Radix sort - O(n log k); requires O(n) extra space
Shell sort - O(n1.25)
Bogosort * - O((n/2)!); requires O(n) extra space

wofür braucht man so einen scheiß algorithmus?

/* BOGOSORT                                                        */
/*                                                                 */
/* Jens Kager <jenskager@gmx.net>                                  */
/* 17. 05. 2001                                                    */
/*                                                                 */
/* Implementierung des Bogosort:                                   */
/*   Arrayelemente werden willkürlich vertauscht, wenn sie dann    */
/*   sortiert sind, werden sie ausgegeben, wenn nicht, wird        */
/*   weitergetauscht.                                              */
/*                                                                 */
/*   Das Programm leidet unter dem Problem, daß die Zufallszahlen  */
/*   nicht wirklich besonders zufällig sind, sondern sich oft      */
/*   wiederholen und damit auch die Kombinationen des Arrays.      */
/*   So sind hunderttausende Durchläufe keine Seltenheit, je mehr  */
/*   Zahlen es sind, desto mehr.                                   */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 20
#define TRUE 1
#define FALSE 0

void rand_seed(void);
int rand_int(int max);
void bogo(int *a, int n);
void show_array(int *a, int n);

void rand_seed(void)
{
  srand48(time(0));
}

int rand_int(int max)
{
  return rand() % max;
}

main(int argc, char *argv[])
{
  int i, j, n=argc-1, sortiert=TRUE, durchlaeufe=0;
  int a[n];

  for (i=0; i<n; i++) {
    a[i] = 0;
  }

  if (n>0) {
    for (i=1; i<=n; i++) {
      a[i-1] = atoi(argv[i]);
    }

    for (i=0; i<n; i++) {
      printf("%d ", a[i]);
    }
    printf("\n");

    for (i=0; i<n-1; i++) {
      if (a[i] > a[i+1]) {
        sortiert = FALSE;
      }
    }

    if (sortiert == FALSE) {
      while (sortiert == FALSE) {
        durchlaeufe++;
        bogo((int *) &a, n);
        sortiert = TRUE;
        for (i=0; i<n-1; i++) {
          if (a[i] > a[i+1]) {
            sortiert = FALSE;
          }
        }
        show_array((int *) &a, n);
      }
    }

    for (i=0; i<n; i++) {
      printf("%d ", a[i]);
    }
    printf("\n");
    printf("Bogosort brauchte %d Durchläufe.\n", durchlaeufe);
  } else {
    printf("Keine Eingabefolge.\n");
  }
}

void bogo (int *a, int n)
{
  int i=0, j=0;
  int t[n], tmp, zzahl=0;
  int indices[n];

  for (i=0; i<n; i++) {
    t[i] = a[i];
    indices[i] = 0;
  }

  rand_seed();
  for (i=0; i<n; i++) {
    zzahl = rand_int(n);
    while (indices[zzahl] == TRUE) {
      zzahl = rand_int(n);
    }
    a[i] = t[zzahl];
    indices[zzahl] = TRUE;
  }
}

void show_array(int *a, int n)
{
  int i=0;

  for (i=0; i<n; i++) {
    printf("%d ", a[i]);
  }
  printf("\n");
}