Buch Cover Buch Cover Buch Cover Buch Cover

Web-Code: - Webcode Help

Doofsort: Zahlen sortieren (Felder)

Gegeben ist ein Zahlenfeld [9, 8, 7, 6, 5, 4, 3, 2, 1, 0].

Dieses Zahlenfeld soll nach dem Doofsort sortiert werden, so dass das kleinste Element (i.e.: 0) als erstes steht, das größte (i.e.: 9) als letztes nach der Sortierung.

Der Doofsort (auch bekannt als Bogosort, PermutationSort, StupidSort, SlowSort, ShotgunSort oder MonkeySort mischt die gegebenen Elemente solange durcheinander, bis alle Elemente in Reihe stehen.

Als Ergebnis steht das sortierte Feld, gemeinsam mit der Anzahl der Versuche. 

 

5 Kommentare

Bitte melde dich an um einen Kommentar abzugeben

Kommentare (5)

c0der 15. Juni 2016 07:21   reply report
Die Abap Lösung funktioniert mit einer beliebigen Eingabe des Users. Zahlen werden durch ein Komma getrennt.
Passend zur Aufgabenstellung lautet die Eingabe dann: "9,8,7,6,5,4,3,2,1,0"
gressly 14. Juni 2016 06:37   reply report
virgil
Jeweils zwei variable Plätze zu vertauschen ist ein guter Ansatz, um den Agorithmus effizient zu machen. Darum geht es allerdings nicht.
Der Bogosort ist nicht effizienzorientiert und mischt tatsächlich ALLE Elemente eines Feldes komplett vor der Überprüfung durch.
Das Durchmischen eines Feldes ist somit Teil der eigentlichen Aufgabe.

Richtig, der RandomPositionSort ist bereits eine doppelte Verbesserung des Bysäth/Gressly Sort aus den späten 80er Jahren.
Ich habe dies im Code vermerkt.
Danke an virgil
CodeWreiter 13. Juni 2016 20:30   reply report
Ich hoffe meine Lösung in C entspricht der Aufgabe. Habe noch eine Eingabe für die Anzahl Durchgänge gemacht, so kann man ein wenig spielen.

Kommentare sind erwünscht!
virgil 11. Juni 2016 23:38   reply report
Jeweils zwei variable Plätze zu vertauschen ist ein guter Ansatz, um den Agorithmus effizient zu machen. Darum geht es allerdings nicht.
Der Bogosort ist nicht effizienzorientiert und mischt tatsächlich ALLE Elemente eines Feldes komplett vor der Überprüfung durch.
Das Durchmischen eines Feldes ist somit Teil der eigentlichen Aufgabe.
gressly 11. Juni 2016 23:03   reply report
Der Bysäth/Gressly-Sort geht in die ähnliche Richtung. Damit ein Array, das schon zu beginn zufällig sortiert ist, nicht in den Genuss eines jähen Abbruchs kommt, ist wie folgt vorzugehen:

wiederhole:
1. wähle zwei beliebige variable Plätze
(diese Plätze dürfen die selbe Stelle im Array bezeichnen)
2. Tausche die Elemente an diesen Plätzen
3. Ist der Array nun sortiert -> Ende
ansonsten zurück zum Start der Wiederholung.

11 Lösung(en)

/**
   * 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)

Aktionen

Bewertung

Durchschnittliche Bewertung:

Eigene Bewertung:
Bitte zuerst anmelden

Meta

Zeit: 0.5
Schwierigkeit: Leicht
Webcode: fcqp-zh5e
Autor: ()

Download PDF

Download ZIP

Zu Aufgabenblatt hinzufügen