Programmieren lernen

/**
   * Gressly (2009)
   * Diese Lösung findet sich auch bei "Planetensortieren" in Aufgabe mit Web-Code 6gqw-5zue
   * Teste, ob sortiert.
   * Falls nicht: Wähle zwei beliebige Positionen und untersuche, ob
   * diese zwei Positionen auf Elemente zeigen, die nicht in Serie sind.
   * Tausche also nur, wenn nötig. ... und beginne dann von vorn.
   */
   @Sort
   public void randomPositionSort() {
     // Die Prüfung nach dem tauschen durchzuführen ist
     // noch "doofer". Insofern ist diese Reihenfolge bereits eine Verbesserung des doofsort.
      while(! istSortiert()) {
         rpSortTausche();   
      }
   }
  
   private void rpSortTausche() {
     int pos1 = (int) (Math.random() * (getLastSortPos() - getFirstSortPos() + 1)) + getFirstSortPos();  
     int pos2 = (int) (Math.random() * (getLastSortPos() - getFirstSortPos() + 1)) + getFirstSortPos();
     if(pos1 > pos2) {
         int tmp = pos1;
         pos1 = pos2;
         pos2 = tmp;   }
  // Die folgende Prüfung ist die zweite Verbesserung.
  // Der Doofsort (Bysäth/Gressly-Sort aus den späten 80er Jahren) lässt diese Prüfung weg und tauscht in jedem Fall.
     if(! istKleiner(pos1, pos2)) {
       this.tausche(pos1, pos2); }
   }
                

Lösung von: Philipp G. Freimann (BBW (Berufsbildungsschule Winterthur) https://www.bbw.ch)

function bogoSort(arr) {

  function shuffle(arr) {   // à la Fisher-Yates-Methode
    var returnArr = [];
    while (arr.length > 0)
      returnArr.push(arr.splice(Math.floor(Math.random() * arr.length), 1)[0]);
    return returnArr;
  }

  function isSorted(arr) {
    for (var i = 0; i < arr.length; i++)
      if (arr[i] > arr[i+1]) return false;
    return true;
  }

  var i = 0;
  while (!isSorted(arr)) {
    arr = shuffle(arr);
    i++;
  }
  console.log(arr);
  console.log("(" + i + " Versuche)")
}

// warnung: das kann schonmal bis zu n millionen versuche dauern
// mittel: O(n * n!)
bogoSort([9, 8, 7, 6, 5, 4, 3, 2, 1, 0]);                   // lissalanda@gmx.at

                

Lösung von: Lisa Salander (Heidi-Klum-Gymnasium Bottrop)

public class BogoSort {
    public static void main(String[] args) {
	// die zu sortierenden Zahlen
	int[] arr = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };

	BogoSort doof = new BogoSort();
	System.out.print("unsortiert :");
	doof.zahlenAnzeigen(arr);

	doof.bogo(arr);

	System.out.print("Sortiert: ");
	doof.zahlenAnzeigen(arr);
    }

    // Anzahl der Versuche
    void bogo(int[] arr) {

	int shuffle = 1;
	for (; !istSortiert(arr); shuffle++)
	    shuffle(arr);

	System.out.println("Anzahl der Versuche (Mischungen) " + shuffle);
    }

    // Fisher-Yates algorithmus
    void shuffle(int[] arr) {
	int i = arr.length - 1;
	while (i > 0)
	    austauschen(arr, i--, (int) (Math.random() * i));
    }

    // Austauschen
    void austauschen(int[] arr, int i, int j) {
	int temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
    }

    // sortieren
    boolean istSortiert(int[] arr) {

	for (int i = 1; i < arr.length; i++)
	    if (arr[i] < arr[i - 1])
		return false;
	return true;
    }

    // sortierte Zahlen anzeigen
    void zahlenAnzeigen(int[] arr) {
	for (int i = 0; i < arr.length; i++)
	    System.out.print(arr[i] + " ");
	System.out.println();
    }

}
                

Lösung von: Houssein Fofana ()

/* doofsort.c ¦¦ braucht ca 150 Durchgänge ¦¦ */

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

int main (void){

int i, max, temp ,doof = 0;
int feld[]={9,8,7,6,5,4,3,2,1,0};

printf("Wieviele Durchgaenge?\n>");             /* Anzahl Sortierdurchgänge **ca. 150 ** */
scanf("%d",&max);
printf("\nDiese Zahlen werden sortiert:\n");    /* Gibt array feld aus */

for (i=0;i<10;i++){
  printf ("%d ",feld[i]);
}
printf("\n\nZufallszahlen \"doof\":\n\n");          /*Gibt die Zufallszahlen aus zur kontrolle */

for (i=0;i<=max;i++){
  doof= rand()%9+0;
  printf("%d ",doof);
  if (feld[doof]>=feld[doof+1]){
    temp= feld[doof];
    feld[doof]=feld[doof+1];
    feld[doof+1]=temp;
  }
}
if (i> max-1){
  printf("\n\nSortiert:\n");                    /* Das sortierte Resultat */
    for (i=0;i<10;i++){
    printf ("%d ",feld[i]);
    }
}
return EXIT_SUCCESS;
}
                

Lösung von: Name nicht veröffentlicht

REPORT  zbogosort.

TYPES: BEGIN OF tt_input,
  input TYPE i,
  random TYPE i,
END OF tt_input.

PARAMETERS: pa_in TYPE string.

DATA: lt_input TYPE STANDARD TABLE OF tt_input,
      ls_input LIKE LINE OF lt_input,
      lv_inputstring TYPE string,
      lt_hilfstabelle TYPE TABLE OF string,
      ls_hilfstabelle LIKE LINE OF lt_hilfstabelle,
      lt_ergebnis TYPE STANDARD TABLE OF i,
      ls_ergebnis LIKE LINE OF lt_ergebnis,
      lv_ergebnisstring TYPE string,
      lv_versuche TYPE i,
      lv_counter TYPE i,
      lv_helper TYPE i,
      lv_fertig TYPE i,
      lv_string TYPE string.

SPLIT pa_in AT ',' INTO TABLE lt_hilfstabelle.

lv_counter = LINES( lt_hilfstabelle ).

LOOP AT lt_hilfstabelle INTO ls_hilfstabelle.
  ls_input-input = ls_hilfstabelle.
  CALL FUNCTION 'QF05_RANDOM_INTEGER'
    EXPORTING
      ran_int_max   = lv_counter
      ran_int_min   = 1
    IMPORTING
      ran_int       = ls_input-random
    EXCEPTIONS
      invalid_input = 1
      OTHERS        = 2.
  IF sy-subrc <> 0.
    MESSAGE ID sy-msgid TYPE sy-msgty NUMBER sy-msgno
            WITH sy-msgv1 sy-msgv2 sy-msgv3 sy-msgv4.
  ENDIF.

  APPEND ls_input TO lt_input.
ENDLOOP.

LOOP AT lt_input INTO ls_input.
  ls_ergebnis = ls_input-input.
  APPEND ls_ergebnis TO lt_ergebnis.
ENDLOOP.

SORT lt_ergebnis ASCENDING.

LOOP AT lt_ergebnis INTO ls_ergebnis.
  lv_string = ls_ergebnis.
  CONCATENATE lv_ergebnisstring lv_string INTO lv_ergebnisstring.
ENDLOOP.

WHILE lv_fertig NE 1.

  SORT lt_input by random ASCENDING.
  clear lv_inputstring.
  LOOP AT lt_input INTO ls_input.
    lv_string = ls_input-input.
    CONCATENATE lv_inputstring lv_string INTO lv_inputstring.
  ENDLOOP.
  IF lv_ergebnisstring EQ lv_inputstring.
    WRITE: / lv_versuche, ' Versuche', /, lv_inputstring.
    lv_fertig = 1.
  ELSE.
    ADD 1 TO lv_versuche.
    LOOP AT lt_input into ls_input.
      CALL FUNCTION 'QF05_RANDOM_INTEGER'
        EXPORTING
          ran_int_max   = lv_counter
          ran_int_min   = 1
        IMPORTING
          ran_int       = ls_input-random
        EXCEPTIONS
          invalid_input = 1
          OTHERS        = 2.
      IF sy-subrc <> 0.
        MESSAGE ID sy-msgid TYPE sy-msgty NUMBER sy-msgno
                WITH sy-msgv1 sy-msgv2 sy-msgv3 sy-msgv4.
      ENDIF.
      MODIFY lt_input from ls_input.
    ENDLOOP.
  ENDIF.
ENDWHILE.
                

Lösung von: Alexander S. (msg systems)

counter = 1

def doofsort(liste){
    sortcheck = 0
    Collections.shuffle(liste) // Liste per Zufall mischen
    // Überprüfung ob Liste aufsteigend sortiert ist
    for(i = 0; i < liste.size-1; i++) {
        if (liste[i] > liste[i+1]) {
            sortcheck = 1
        }
    }
    if (sortcheck > 0) {
        return 0
    }
}

while (doofsort([9, 8, 7, 6, 5, 4, 3, 2, 1, 0]) == 0){
    counter = counter + 1
}

println counter + " Versuche"

                

Lösung von: Name nicht veröffentlicht

import random


list = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
f = list[::]
f.sort()
zaehler = 0


while list != f:
    random.shuffle(list)
    zaehler = zaehler + 1


print("Es wurden", zaehler, "versuche gebraucht.")

                

Lösung von: Alexander None (None)

from random import shuffle as r_shuffle

def doof(*numbers):
    numbers = list(numbers)
    sorted_l = sorted(numbers)
    c = 0
    while numbers != sorted_l:
        r_shuffle(numbers)
        c += 1
    return numbers, 'Versuche:', c
                

Lösung von: Bester Mensch (Class)

'05.03.2017 - PowerBASIC 10

#COMPILE EXE
#DIM ALL

FUNCTION PBMAIN () AS LONG

    Stoppuhr(1)

    DIM meinArray(9) AS INTEGER
    DIM arrOut        AS STRING
    DIM i             AS INTEGER
    DIM x             AS QUAD

    ARRAY ASSIGN meinArray() = 9, 8, 7, 6, 5, 4, 3, 2, 1, 0

    DO UNTIL istSortiert(meinArray()) = 1
        INCR x
        CALL Shuffle(meinArray())
    LOOP

    FOR i = LBOUND(meinArray) TO UBOUND(meinArray)
        arrOut += FORMAT$(meinArray(i)) & CHR$(32)
    NEXT i

    MSGBOX arrOut & $CRLF & FORMAT$(x) & " Versuche(" & Stoppuhr(2) & ")", %MB_OK, EXE.NAME$

END FUNCTION

'---------------------------------------------------------

''Fisher-Yates Shuffle

SUB Shuffle(BYREF meinArray() AS INTEGER)

    DIM zwTemp AS LONG           'hält vorübergehend das zu tauschende Element
    DIM zwPos  AS LONG           'Zufällige Position im Array
    DIM i      AS LONG           '

    'Zufallsgenerator initialisieren
    RANDOMIZE TIMER

    FOR i = UBOUND(meinArray) TO (LBOUND(meinArray) + 1) STEP -1
        'Zufallszahl innerhalb der Array-Grenzen
        zwPos = CLNG(INT((i - LBOUND(meinArray) + 1) * RND + LBOUND(meinArray)))

        'Das zu tauschende Element zwischenspeichern
        zwTemp = meinArray(i)

        'Zufällig gewähltes Element einfügen
        meinArray(i) = meinArray(zwPos)

        'Das zwischengespeicherte Element an der Stelle einfügen,
        'wo das andere herkam
        meinArray(zwPos) = zwTemp
    NEXT i

END SUB

'---------------------------------------------------------

FUNCTION IstSortiert(meinArray() AS INTEGER) AS BYTE

    DIM i AS LONG
    FUNCTION = 0

    FOR i = 1 TO UBOUND(meinArray)
        IF meinArray(i) < meinArray(i-1) THEN
            FUNCTION = 0
            EXIT FOR
        ELSE
            FUNCTION = 1
        END IF
    NEXT i

END FUNCTION

'---------------------------------------------------------

FUNCTION Stoppuhr(Signal AS BYTE) AS STRING
    STATIC startzeit AS DOUBLE
    DIM Hrs  AS LONG
    DIM Mins AS LONG
    DIM Secs AS LONG

    IF Signal = 1 THEN startzeit = TIMER
    IF Signal = 2 THEN
        Secs = TIMER - startzeit
        Hrs  = Secs \ 3600
        Mins = (Secs - (Hrs * 3600)) \ 60
        Secs = (Secs MOD 3600) MOD 60
        FUNCTION = FORMAT$(Hrs,"00") & ":" & FORMAT$(Mins,"00") & ":" & FORMAT$(Secs,"00")
    END IF
END FUNCTION

                

Lösung von: Markus Sägesser (keine)

// NET 6.x | C# 10.x | VS-2022

var src = new List<int> { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
var tgt = src.OrderBy(x => x).ToList();

var cnt = 0;
while (!tgt.SequenceEqual(src.OrderBy(x => new Random().Next()))) cnt++;

Console.WriteLine($"Anzahl Versuche: {cnt:##0,0} -> {string.Join(", ", tgt)}");
                

Lösung von: Jens Kelm (@JKooP)

// C++ 17

#include <iostream>
#include <vector>
#include <random>

int main() {
    std::vector<int> src{ 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
    std::reverse(src.begin(), src.end());
    auto cnt{ 0 };
    auto tgt{ src };

    do {
        shuffle(tgt.begin(), tgt.end(), std::random_device());
        cnt++;
    } while (tgt != src);

    std::cout << "Versuche: " << cnt << " Array: ";
    for (const auto& t : tgt)
        std::cout << t << " ";
}
                

Lösung von: Jens Kelm (@JKooP)

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

bool compare(int *lhs, int lhs_size, int *rhs, int rhs_size){
    if(lhs_size != rhs_size || lhs == NULL || rhs == NULL)
        return false;
    for(int i = 0; i < lhs_size; i++)
        if(lhs[i] != rhs[i])
            return false;
    return true;
}

void swap(int *lhs, int *rhs){
    int tmp = *lhs;
    *lhs = *rhs;
    *rhs = tmp;
}

void shuffle(int *array, int size) {
    for (int lhs = 0; lhs < size - 1; ++lhs) {
        int rhs = lhs + rand() / (RAND_MAX / (size - lhs) + 1);
        swap(&array[rhs],&array[lhs]);
    }
}

int main() {
    srand(time(NULL));
    int cnt = 0;
    int src[10] = {0,1,2,3,4,5,6,7,8,9};
    int tgt[10] = {9,8,7,6,5,4,3,2,1,0};

    do{
        shuffle(tgt, 10);
        cnt++;
    } while(!compare(tgt, 10, src, 10));

    printf("Versuche: %d\n\n", cnt);
    for(int i = 0; i < 10; i++)
        printf("%d ", tgt[i]);

    return 0;
}

                

Lösung von: Jens Kelm (@JKooP)