Bogosortering

Fra Wikipedia, den frie encyklopedi
Gå til: navigasjon, søk

I informatikk er Bogosortering (en. bogosort) en særdeles ineffektiv sorteringsalgoritme. Dersom den brukes for å sortere en kortstokk vil den bestå i å kaste kortstokken i luften, plukke opp kortene tilfeldig, og etterpå sjekke om de ble liggende i rekkefølge. Prosedyren må gjentas inntil rekkefølgen viser seg å være riktig. Algoritmen er også kjent under navn som stupid sort, apesortering (en. monkey sort) og fyllesortering (en. drunk man sort).

BlitzMax kode[rediger | rediger kilde]

Function Bogosort:Int[](n:Int[])
	iter=0
	sortert = False
 
	While( Not sortert)
		iter:+1
		sortert=True
 
		For index=0 To n.length-2
			If(n[index] > n[index+1]) sortert=False
 
			If(Not sortert) 'bytt plass på to tilfeldige tall
				Local tilfeldig:Int = Rand(0,n.length-1)
				Local swap:Int = n[index]
				n[index] = n[tilfeldig]
				n[tilfeldig]=swap;
			EndIf
		Next
	Wend
	Print "sorteringen brukte "+iter+" iterasjoner"
	Return n
End Function

Tidsforbruk og terminering[rediger | rediger kilde]

Denne sorteringsalgoritmen er tilfeldig i natur. Hvis alle elementene som skal sorteres er forskjellige er antall forventede sammenlikninger ekvivalent til (e-1)* n!, og antall forventede vekslinger (swaps) er i gjennomstitt lik (e-1)× n!.[1] Forventet antall vekslinger øker fortere enn forventet antall sammenlikninger. Dersom elementene ikke er i rekkefølge kan dette oppdages etter bare noen få sammenlikninger uavhengig hvor mange elementer som finnes. Dog er arbeidet som må til for å blande elementene proporsjonal til samlingens størrelse. I verste fall er antall sammenlikninger og vekslinger begge ubegrensede, akkurat som en mynt kan lande på samme side uendelig mange ganger.

Det beste tilfellet er når listen allerede er sortert. Da er antall forventede sammenlikninger n-1, og innen vekslinger gjøres. Ved sortering av lister med to elementer er Bogosort blant de beste sorteringsmetodene. En sammenlikning og algoritmen avslutter eller gjør en veksling og en til sammenlikning.

Den eksakte kjøretiden avhenger av hvormange forskjellige elementer forekommer og hvor ofte hver av dem oppstår. En kan forvente at for ikke trivielle tilfeller er kjøretiden super-eksponentiell i n da n! overgår an for hver konstant a. Algoritmen termineres av samme grunn som «setningen om uendelig mange aper» holder; det er en viss sannsynlighet for å få riktig permutasjon. Så gitt ubegrenset antall forsøk må listen til slutt bli sortert. For at dette skal gå må veksleprosessen aldri gjenta samme mønster, noe som vil skje om det brukes en algoritme for tilfeldighet som ikke er perfekt. Alle psudo-tilfeldige algoritmer er utilstrekkelige.

Referanser[rediger | rediger kilde]

  1. ^ H. Gruber, M. Holzer and O. Ruepp: Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms, 4th International Conference on Fun with Algorithms, Castiglioncello, Italy, 2007, Lecture Notes in Computer Science 4475, pp. 183-197.