How to resolve the algorithm Sorting algorithms/Bogosort step by step in the Action! programming language

Published on 12 May 2024 09:40 PM
#Action!

How to resolve the algorithm Sorting algorithms/Bogosort step by step in the Action! programming language

Table of Contents

Problem Statement

Bogosort a list of numbers.

Bogosort simply shuffles a collection randomly until it is sorted. "Bogosort" is a perversely inefficient algorithm only used as an in-joke.
Its average run-time is   O(n!)   because the chance that any given shuffle of a set will end up in sorted order is about one in   n   factorial,   and the worst case is infinite since there's no guarantee that a random shuffling will ever produce a sorted sequence. Its best case is   O(n)   since a single pass through the elements may suffice to order them.

Pseudocode:

The Knuth shuffle may be used to implement the shuffle part of this algorithm.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Sorting algorithms/Bogosort step by step in the Action! programming language

Source code in the action! programming language

PROC PrintArray(INT ARRAY a INT size)
  INT i

  Put('[)
  FOR i=0 TO size-1
  DO
    IF i>0 THEN Put(' ) FI
    PrintI(a(i))
  OD
  Put(']) PutE()
RETURN

PROC KnuthShuffle(INT ARRAY tab BYTE size)
  BYTE i,j
  INT tmp

  i=size-1
  WHILE i>0
  DO
    j=Rand(i+1)
    tmp=tab(i)
    tab(i)=tab(j)
    tab(j)=tmp
    i==-1
  OD
RETURN

BYTE FUNC IsSorted(INT ARRAY tab BYTE size)
  BYTE i

  IF size<2 THEN
    RETURN (1)
  FI
  FOR i=0 TO size-2
  DO
    IF tab(i)>tab(i+1) THEN
      RETURN (0)
    FI
  OD
RETURN (1)

PROC BogoSort(INT ARRAY a INT size)
  WHILE IsSorted(a,size)=0
  DO
    KnuthShuffle(a,size)
  OD
RETURN

PROC Test(INT ARRAY a INT size)
  PrintE("Array before sort:")
  PrintArray(a,size)
  BogoSort(a,size)
  PrintE("Array after sort:")
  PrintArray(a,size)
  PutE()
RETURN

PROC Main()
  INT ARRAY
    a(10)=[1 4 65535 0 7 4 20 65530],
    b(21)=[3 2 1 0 65535 65534 65533],
    c(8)=[101 102 103 104 105 106 107 108],
    d(12)=[1 65535 1 65535 1 65535 1
      65535 1 65535 1 65535]
  
  Test(a,8)
  Test(b,7)
  Test(c,8)
  Test(d,12)
RETURN

You may also check:How to resolve the algorithm Water collected between towers step by step in the Factor programming language
You may also check:How to resolve the algorithm Metallic ratios step by step in the J programming language
You may also check:How to resolve the algorithm Null object step by step in the Raven programming language
You may also check:How to resolve the algorithm Magic squares of odd order step by step in the Ruby programming language
You may also check:How to resolve the algorithm Date manipulation step by step in the Raku programming language