PHP Eigenes Sortierverfahrren

[ReDeYeDRaVeN]

Ich habe derzeit folgende Aufgabe vorliegen:

Ein Feld wird einmal vollständig von links nach rechts durchlaufen. 
Dabei werden die jeweiligen Nachbarelemente miteinander verglichen
und ggf. ausgetauscht. Am Ende befindet sich das größte Element 
am Ende des Feldes. Nun wird das kleinere Teilfeld wieder vollständig
durchlaufen, aber diesmal von rechts nach links. Dabei werden die
jeweiligen Nachbarelemente wieder miteinander verglichen 
und ggf. ausgetauscht. Am Ende befindet sich das kleinste 
Element am Anfang des Feldes. Dieser Schritt wird nun mit dem 
kleineren Teilfeld (Feld ohne das erste und letzte Element) wiederholt und wiederholt und ... 
Und irgendwann sind wir fertig und die Elemente sind sortiert.

Als einer der wenig Kaufleute quäle ich mich in der IT-Klasse doch sehr mit dem Programmieren und erhoffe mir ein wenig Hilfe hier

Ich kann per Bubblesort sortieren, dies soll aber irgendwie ein eigenes Sortierverfahren darstellen. Ich fühl mich ein wenig wie "schreibe einen Aufsatz auf französisch obwohl du die Sprache nicht kannst".

<?php

 
 
//$array_size = 10;
 

//for($x = 0; $x < $array_size; $x++)
//  $ran[$x] = rand(0, 10);
 $ran = array(5,8,2,9,0,3,6,8,7,88,567,99);
$array_size=count($ran);
for($x = 0; $x < $array_size; $x++) {
  for($y = 0; $y < $array_size; $y++) {
    if($ran[$x] < $ran[$y]) {
      $hold = $ran[$x];
      $ran[$x] = $ran[$y];
      $ran[$y] = $hold;
    }
  }
}
 
for($x = 0; $x < $array_size; $x++)
  print $ran[$x] . "<br>";
 
 
?>

Das funktioniert, ist aber nicht das was sich unser Lehrer vorstellt. Wir sollen das halt so machen wie in der Aufgabenbeschreibung.

Habt ihr nen kleinen Denkanstupser für mich? Ich blick hier garnix >.>

grüße
ReD

 

[Madman1209]

Hi,

im Prinzip ist es ein BubbleSort...aber mit der Einschränkung, dass du bei den "geraden" Durchläufen nicht das Größte nach rechts sondern das Kleinste nach links schiebst.

Also,
Durchlauf 1,3,5,7... suchen das GRÖSSTE und schieben es nach RECHTS (Feld-Ende).
Durchlauf 2,4,6,8... suchen das KLEINSTE und schieben es nach LINKS (Feld-Anfang).

Hilft dir das als Denkanstoss?


VG,
Mad

 

[Killkrog]

Verwende zwei zusätzliche Variablen, wobei die eine von ganz Links (0) sich weiter in die Mitte bewegt, die andere sich von Rechts (array_size) ebenfalls in die Mitte bewegt. Damit hast du die Grenzen abgesteckt. Nach jedem Durchgang verschiebst du die Grenzen entsprechend. Sobald die zwei Grenzen auf das selbe Element zeigen, bist du fertig.

 

[engelswut]

Das ist Bubblesort

Wie soll man das anders lösen ?

 

[ReDeYeDRaVeN]

Hm, das Prinzip wird auf jeden Fall klarer.

Ich ärger mich nur so das mir der Kram überhaupt nicht liegt (Ich arbeite beruflich im Bereich Beratung&Verkauf von Hard und Softwarelösungen), habe damit also rein garnix zu tun. Nur ist das leider Teil meiner Ausbildung...Für mich liest sich das alles wie böhmische Dörfer :<

Ich verstehe das Prinzip, kann aber jetzt nicht Anfangen das ganze in irgendwelche functions etc. zu wandeln. Das wäre wie Deutsch>Englisch (was kein Problem aufwirft), es funktioniert halt nicht bei Aufgabenbeschreibung>PHP-Code.

Ich will euch hier nicht volljaulen über Ausbildungsinhalte und was sie mit meinem Job als Kaufmann zu tun haben, ich will auch keine Lösung zu der Aufgabe. Aber über nen Beispiel würde ich mich freuen :>

Vielen Dank schonmal!
ReD

 

[Killkrog]

@engel
Hast du die Aufgabenstellung und seine Lösung angesehen? Das sind riesige Unterschiede drin...

 

[HRaffnix]

Bubble Sort sieht so aus im Pseudo Code:

void BubbleSort(item a[1...n])
index i,j;
for i<--1 to n - 1 do
for j<--n downto i+1 do
if a[j] < a[j-1]
then
exchange a[j] and a[j-1]

funktionsweise:
Der Algorithmus vergleicht der Reihe nach zwei benachbarte Elemente und vertauscht sie, falls sie in der
falschen Reihenfolge vorliegen. Dieser Vorgang wird solange wiederholt, bis keine Vertauschungen mehr
nötig sind. Hierzu sind in der Regel mehrere Durchläufe erforderlich. Im ersten Durchlauf wandert somit die
kleinste Zahl ganz nach links. Der zweite Durchlauf braucht somit die erste und zweite Position nicht mehr
zu vergleichen.

 

[Killkrog]

@ ReDeYeDRaVeN
So, auch wenn sich das jetzt komisch anhört, aber probier doch mal folgendes...
Nimm mal 10 Papierschnippsel in die Hand, schreibe da zufällige Zahlen drauf, lege sie vor dir auf den Tisch und sortiere sich nach dem dir gegebenen Verfahren.
Achte dabei auf das, was du dir denkst, was du ansiehst, was du dir alles merkst und was deine Hände tun.

Dann schreibe das genauso in php.

 

[Madman1209]

Hi,

Das ist Bubblesort

Wie soll man das anders lösen ?

Nicht direkt. Der klassische BubbleSort sortiert entweder aufsteigend in eine Richtung oder absteigend. Hier soll am Ende eine Mischform je nach Durchlaufzähler herauskommen, immer abwechselnd groß nach rechts und danach klein nach Links. Also kein "reiner" BubbleSort.

VG,
Mad

 

[Limit]

Wo liegt denn das Problem? Wie du die Elemente austauschst weißt du ja.

Du könntest eine Funktion schreiben, die die Liste einmal von einem Index min bis zu einem Index max durchläuft und dabei ggf. Elemente tauscht.

Diese Funktion packst du dann in eine Schleife, die so oft durchlaufen wird bis mix = max ist. in Pseudocode würde das dann evtl. so aussehen:

richtung = 1
while (min < max) do
	geheDurchFeld(feld, min, max, richtung)
	if (richtung = 1) then
		max = max - 1
	else
		min = min + 1
	richtung = richtung * (-1)

 

[Shagg]

Ok, also du hast ein Array a[l] das Sortiert werden muss, von einer gewissen länge l.
Du schreibst eine funktion, sortLeft() die einen integer wert i initialisiert und dann immer a > a[i+] abfragt. trifft das zu, dann machst du folgendes: save = a, a = a[i+1] und a[i+1] = save , mit anderen worten eine einfache swichfunktion. trifft die abfrage nicht zu, musst du nichts tauschen. in beiden fällen musst du dann i um eins erhöhen. sort left läuft dabei als schleife solange, bis i = länge des arrays ist. danach brauchst du das nochmal für links nach rechts umsetzen, dabei verändert sich die abfrage logischerweise. da du insgesamt ja das array der länge l hast, musst du beim nächsten rekursiven aufruf der funktionen, die funktionen mit l-1 als länge aufrufen, damit sie nicht mehr das gesamte array sortieren, sondern eins weniger.