Sortieren Tutorial (2)

Übersicht BlitzMax, BlitzMax NG FAQs und Tutorials

Neue Antwort erstellen

 

Macintosh

Betreff: Sortieren Tutorial (2)

 BeitragDo, Jun 10, 2010 12:21
Antworten mit Zitat
Benutzer-Profile anzeigen
In diesem Tutorial will ich versuchen zu erklären welche verschiedenen Sortier - Algorithmen es gibt, wie diese Funktionieren und wie man sie programmiert.

Was können wir denn sortieren? Wir können Arrays und Listen sortieren.
Allerdings werde ich mich in diesem Tutorial erstmal den Arrays zuwenden.
Wollen wir eine Liste mit diesen Algorithmen sortieren, so können wir unsere Liste mit liste.toArray() in ein Array konvertieren.


1. Der SelectionSort


Der SelectionSort ist die einfachste Methode, aber auch die schlechteste (langsam + dumm) Daten zu sortieren.
Der Algorithmus sortier ungefähr so wie Wir beim Karten spielen sortieren.
Er geht die Werte der reihe nach durch und vertauscht Zwei so das der Kleinere von beiden nach vorne kommt, der andere wert wird an die _position des Kleineren verschoben.

Wir haben 2 Finger oder "Zeiger" die auf ein Array element bzw. dessen index Zeigen. Rot und Grün.

user posted image
(Der grüne Zeiger fängt am Roten + 1 an und endet am Array ende.
Ergeht wie auch der Rote jeweils 1 schritt weiter)
(Grau = schon Sortiert)

Wir haben Folgende Variablen:

Code: [AUSKLAPPEN]

Array:Int[] = [ 6,2,5,9,2,7,4,12 ]
I:Int      'Roter "Zeiger"
J:Int      'Grüner "Zeiger"
_min:Int   'kleinster Wert
_pos:Int   '_position im array des kleinsten wertes (_min) (gelber zeiger)


I entspricht dem Roten Zeiger auf dem Bild, J dem Grünen. Array, ist unsere Array, dessen Daten wir Sortieren wollen.

Legen wir erst einmal eine neue Funktion an, in diesem fall nenne ich sie einfach SeelectionSort.

Code: [AUSKLAPPEN]

Function SelectionSort( _array:Int[] )
   
EndFunction


So... nun an den Eigentlichen Sortier Algorithmus.
Wir haben einen For-To loop für den Roten und einen für den Grünen Zeiger.

Code: [AUSKLAPPEN]
 
For Local i:Int =  0 To _array.length - 1

   _pos = i
_min = _array[ i ]

For Local j:Int = _pos + 1 To _array.length – 1

   If _array[ j ] < _min
      _pos = j
      _min = _array[ j ]
   EndIf

Next
Next


Wir gehen schritt für Schritt in (i) durch das Array, aber bei Jedem schritt gehen wir von (i) aus durch das komplette Array. Dort werden wir dann die Werte vergleichen.
Die Variable _min enthält immer den Kleinsten Wert im array (von i aus gezählt).
Bei „If _array[ j ] < _min“ wird die kleinste zahl von i ab gezählt aus dem Array gesucht und _min übergeben, dies wird für jeden wert hinter i gemacht. Somit sind wir 100% sicher den Kleinsten wert nach i gefunden zu Haben.

Nun müssen die Werte nurnoch vertauscht werden.
Dies muss in der For-To schleife i geschehen, und zwar am ende.

Code: [AUSKLAPPEN]

_array[ _pos ] = _array[ i ]
_array[ i ] = _min


erst vertauschen wir den kleinsten wert mit dem wert an position i, danach den von position i mit dem kleinsten wert, den wir (auch) in _min gespeichert haben.

Hier die Schrittfolge in Bildern, alees wiederholt sich, bis man am ende des Array angelangt ist.
Der Gelbe Pfeil entspricht der Variable _pos also der Position des kleinsten Wertes.
user posted image
user posted image
user posted image
user posted image
(danach würde der Gelbe zeiger auf der 3 stehen)

Die komplette Funktion sieht dann so aus.

Code: [AUSKLAPPEN]
 
Function SelectionSort( _array:Int[] )

   Local _pos:Int = 0
   Local _min:Int = 0

   For Local i:Int = 0 To _array.length - 2
   
      _pos = i
      _min = _array[ i ]
      
      For Local j:Int = _pos + 1 To _array.length - 1
         
         If _array[ j ] < _min
         
            _min = _array[ j ]
            _pos = j
         
         EndIf
      
      Next
   
      _array[ _pos ] = _array[ i ]
      _array[ i ] = _min
   
   Next

EndFunction


! Dieser Algorithmus ist nicht besonders schnell... er ist auch der "dümmste" Sortier Algo. da er auch schon sortierte Array sortiert, usw. !

Ich hoffe das Tutorial hat ein bisschen geholfe, diesen recht simplen Algo. zu verstehen. Kritik (gute als auch schlechte) ist erwünscht :)
  • Zuletzt bearbeitet von Macintosh am So, Jun 13, 2010 11:36, insgesamt 17-mal bearbeitet
 

Macintosh

Betreff: BubbleSort

 BeitragDo, Jun 10, 2010 12:29
Antworten mit Zitat
Benutzer-Profile anzeigen
2. Der BubbleSort

Der BubbleSort ist einen Tick besser als der Selection sort, ist aber auch noch nicht grade schnell.
Warum Bubble? Das Wort Bubble im BubbleSort kommt daher,wir uns diesmal die dauten untereinander (nicht nebeneinander) vorstellen, nun steigen die Großen Zahlen
nach oben, das sind dann die Blasen, die im Wasser nach oben steigen.

user posted image
(Grau ist Falsch. Nicht beachten, in diesem Algo gibt es kein Grau und wenn dann ist es am ende des Array -> Optimierung)

Der BubbleSort ist immer noch ein recht Simpler Algorithmus.
So werden immer jeweils 2 neben/übereinander liegende Werte verglichen und getauscht, falls der untere Wert größer als der über ihm ist. Er steigt nach oben.

Wir brauchen wieder ein paar Variablen:

BlitzMax: [AUSKLAPPEN] 

_value:Int
_swapped:Byte


_value wird einen Wert zwischenspeichern, _swapped (T/F) gibt an ob 2 werte getauscht werden, wenn falsch, dann ist das Array sortiert.

Wir schreiben uns wieder eine Funktion, ich nenne sie jetzt mal bubbleSort.

BlitzMax: [AUSKLAPPEN] 

Function bubbleSort[ _array:Int[] ]

EndFunction


Diesmal brauchen wir nicht 2 For-To loops sondern eine Repeat-until Schleifen und einen For-To loop.
Die Repeat-until Schleife wiederholt so lange _swapped = true ist.

BlitzMax: [AUSKLAPPEN] 

Repeat

	_swapped = False

	For Local i:Int = 0 To _array.length – 1

	Next

Until _swapped


Wir gehen so oft durch das Array durch, bis wir _swapped = False ist.
Ähnlich wie beim SelectionSort haben wir auch hier wieder einen „Zeiger“, sagen wir mal der ist Rot und seine Position ist i. Und wir haben auch wieder einen Gelben "Zeiger" dessen position i + 1 ist.
Ist der Wert am Roten Zeiger GRößer als der am Gelben so wird getauscht.

user posted image
user posted image
(Tauschen)

Nun das eigentliche Sortieren.
Wir prüfen ob _arrray[ i ] > _array[ i+1 ] ist, wenn ja, dann vertauschen wir beide Werte mit einander.
Das sähe dann so aus:

BlitzMax: [AUSKLAPPEN] 

If ( _array[ i ] > _array[ i + 1 ] )
	_value = _arra[ i ]
	_array[ i ] = _array[ i + 1 ]
	_array[ i + 1 ] = _value
	_swapped = True
EndIf


Wir vertauschen die Beiden Werte und setze _swapped auf True, das heist wir gehen alles noch einmal durch.

Der ganze Code sähe dann so aus:

BlitzMax: [AUSKLAPPEN] 

Function bubbleSort[ _array:Int[] ]

	Local _value:Int = 0
	Local _changed:Int = False

	Repeat

	_swapped = False

		For Local i:Int = 0 To _array.length – 1

			If ( _arra[ i ] > _array[ i + 1 ] )
				_value = _arra[ i ]
				_array[ i ] = _array[ i + 1 ]
				_array[ i + 1 ] = _value
				_swapped = True
			EndIf

		Next

	Until _swapped

EndFunction



Danke ☺

EDIT:

Diesen algorithmus können wir noch einen Tick optimieren.
Dazu legen wir uns eine Locale Variable _count vom Typ Integer in der Funktion an.
Diese Variable Count zählen wir in der Repeat-Until schleife immer +1 hoch.
Im For-To loop, wird dann ...to _array.length - 1 - _count geschreiben.
Diese Optimierung bewirkt das wir die schon sortierten Zahlen nicht noch einmal durch gehen.

Optimierte Version:
BlitzMax: [AUSKLAPPEN] 
Function BubbleSort( _a:Int[] )

	Local _value	:Int = 0
	Local _swapped	:Byte = True
	Local _count	:Int = 0

	While _swapped
	
		_swapped = False
		_count:+ 1
		
		For Local i:Int = 0 To _a.length - 1 - _count
		
			If _a[ i ] > _a[ i + 1 ]
					
				_value = _a[ i ]
				_a[ i ] = _a[ i+1 ]
				_a[ i+1 ] = _value
					
				_swapped = True
					
			EndIf
		
		Next		
	
	Wend

EndFunction
_swapped
  • Zuletzt bearbeitet von Macintosh am So, Jun 13, 2010 11:39, insgesamt 14-mal bearbeitet
 

Macintosh

Betreff: Platzhalter MergeSort

 BeitragDo, Jun 10, 2010 12:29
Antworten mit Zitat
Benutzer-Profile anzeigen
Platzhalter
 

Macintosh

 BeitragSa, Jun 12, 2010 20:31
Antworten mit Zitat
Benutzer-Profile anzeigen
es währe ganz schön wenn wenigstens einer etwas schreiben würde, ich würd gern weitermachen, aber so ohne feedback?

das wurgel

 BeitragSa, Jun 12, 2010 21:12
Antworten mit Zitat
Benutzer-Profile anzeigen
Die Leute schreiben meistens nur dann etwas, wenn es was zu bemänglen gibt, das liegt eben in der Natur des Menschen. In diesem Fall gibt es nichts zu bemänglen. Also: Weiter so! Wink
1 ist ungefähr 3

Xeres

Moderator

BeitragSo, Jun 13, 2010 0:43
Antworten mit Zitat
Benutzer-Profile anzeigen
Ähm... hübsche bebilderung! Ich frag mich allerdings, wozu Platzhalter Beiträge gut sein sollen.
Zum Thema: www.sorting-algorithms.com
Win10 Prof.(x64)/Ubuntu 16.04|CPU 4x3Ghz (Intel i5-4590S)|RAM 8 GB|GeForce GTX 960
Wie man Fragen richtig stellt || "Es geht nicht" || Video-Tutorial: Sinus & Cosinus
THERE IS NO FAIR. THERE IS NO JUSTICE. THERE IS JUST ME. (Death, Discworld)

M0rgenstern

 BeitragSo, Jun 13, 2010 3:42
Antworten mit Zitat
Benutzer-Profile anzeigen
Hey.
Finde das Tutorial super.
Dein Schreibstil ist auch gut und man kann auch gut nachvollziehen was grade gezeigt und erklärt wird.
Das einzige was ich zu bemängeln hätte: Den Code könntest du doch kommentieren. Dann wärs (für ein Tutorial) noch besser.

Ansonsten: Weiter so. Freue mich auf die anderen Methoden. Mich interessieren die verschiedenen Funktionsweisen.

Lg, M0rgenstern

Firstdeathmaker

 BeitragSo, Jun 13, 2010 10:18
Antworten mit Zitat
Benutzer-Profile anzeigen
Ich würde an deiner Stelle erstmal schnell weiter machen, vor allem Merge und Quicksort vorstellen, die sind ja am gebräuchlichsten. Cool wäre dann am Ende auch noch Binary sort Wink
www.illusion-games.de
Space War 3 | Space Race | Galaxy on Fire | Razoon
Gewinner des BCC #57 User posted image

Neue Antwort erstellen


Übersicht BlitzMax, BlitzMax NG FAQs und Tutorials

Nach Oben

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group