Array sortieren...

[BlackScorp]

Hallo leute,

ich habe ein kleines Problem.. ich dachte ich könnte programmieren aber musste heute feststellen dass ich viel zu verwöhnt bin fertige funktionen zu verwenden... ich muss ein mehrdimensionales array nach bestimmten kriterien sortieren OHNE vorgefertigte funktionen zu verwenden.. folgendes array ist vorhanden

$liste = array(
    0 => array('paketNr' => 424, 'priority' => 1, 'distance' => 8),
    1 => array('paketNr' => 290, 'priority' => 1, 'distance' => 5),
    2 => array('paketNr' => 295, 'priority' => 2, 'distance' => 9),
    3 => array('paketNr' => 129, 'priority' => 1, 'distance' => 1),
    4 => array('paketNr' => 176, 'priority' => 3, 'distance' => 2),
    5 => array('paketNr' => 131, 'priority' => 2, 'distance' => 2),
    6 => array('paketNr' => 121, 'priority' => 1, 'distance' => 4),
    7 => array('paketNr' => 934, 'priority' => 1, 'distance' => 8),
    8 => array('paketNr' => 385, 'priority' => 1, 'distance' => 5),
    9 => array('paketNr' => 323, 'priority' => 3, 'distance' => 7),
    10 => array('paketNr' => 287, 'priority' => 2, 'distance' => 4),
    11 => array('paketNr' => 350, 'priority' => 2, 'distance' => 5)
); 

so ich muss das array erstmal nach entfernung sortieren also kleiner 5 und größer 5.. alle werte die kleiner sind als 5 müssen dann nach priority sortiert werden also höhere zahl = höhere prioritat, bei gleicher entfernung und priorität, spielt es keine rolle , welche reihenfolge und das gleiche dann mit der entfernung höher als 5. mein ansatz war folgender:

$html = '<table border="1" width="100%">
    <tr>
<th>Paket Nummer</th>
<th>Priorität</th>
<th>Entfernung</th>
</tr>';

foreach ($liste as $index => $paket) {
    if ($liste[$index]['distance'] < 5) {
        $html .= '<tr>';
        $html .= '<td>' . $liste[$index]['paketNr'] . '</td>';
        $html .= '<td>' . $liste[$index]['priority'] . '</td>';
        $html .= '<td>' . $liste[$index]['distance'] . '</td>';
        $html .= '</tr>';
    } else {
        $html .= '<tr>';
        $html .= '<td>' . $liste[$index]['paketNr'] . '</td>';
        $html .= '<td>' . $liste[$index]['priority'] . '</td>';
        $html .= '<td>' . $liste[$index]['distance'] . '</td>';
        $html .= '</tr>';
    }
}
$html .= '</table>';
echo $html; 

somit habe ich erstmal die liste in 2 teile getrennt.. und danach? also ich nach "Array Sortieren " gegooled habe, kamen schon einige beispiele raus aber jedesmal wurde da entweder usort() oder andere funktionen verwendet... könnt ihr mir ein denkanstos geben? Ich müsste ja irgendwie ein wert zwischenspeichern und im nächsten durchlauf , den zwischengespeicherten wert mit dem aktuellen vergleichen.. irgendwie war da was.. kann mich nicht mehr erinnern weil ich halt immer funktionen verwendet habe.

MFG

[BlackScorp]

ja funktionen... ich muss den sortiert algorithmus in Pseudocode oder Sturktogramm darstellen ich habe das ganze in php geschrieben , weil ich es besser behersche als C++(dähmliche Cannot convert to fehler) werde mir mal dein code genauer anschauen und mal für mich verständlich umbauen.. Copy & Past bringt ja nichts.. danke dass du dir zeit genommen hast. Mal schauen was sich daraus ergibt

MFG

[Asipak]

Ich habe mich auch mal dran versucht. Habe zuerst dein Array in 2 Arrays aufgeteilt. Das Erste wird später nach den Kriterien für eine kurzen Distanz (< 5) sortiert und das Zweite enthält die Arrays, deren Eintrag unter distance >= 5 ist und wird dementsprechend auch anders sortiert, da du dafür andere Bedingungen definiert hast.

<?php
error_reporting(E_ALL | E_STRICT);

function shortDistanceSort(array &$array) {
  // evtl. Validierung des übergebenen Arrays
  // if (...) return false;
  
  // Sortieralgorithmus wie in Post #2
  for ($i = 0, $n = count($array)-1; $i < $n; ++$i) {
    $max = $j = $i + 1;
    while ($j <= $n) {
      if ($array[$j]['priority'] > $array[$max]['priority']) {
        $max = $j;
      }
      else if ($array[$j]['priority'] == $array[$max]['priority']) {
        if ($array[$j]['distance'] < $array[$max]['distance']) {
          $max = $j;
        }
      }
      ++$j;
    }
    if ($array[$i]['priority'] < $array[$max]['priority']) {
      $tmp = $array[$i];
      $array[$i] = $array[$max];
      $array[$max] = $tmp;
    }
  }

  return true;
}

function longDistanceSort(array &$array) {
  // evtl. Validierung des übergebenen Arrays
  // if (...) return false;

  // Sortieralgorithmus wie in Post #2
  for ($i = 0, $n = count($array)-1; $i < $n; ++$i) {
    $max = $j = $i + 1;
    while ($j <= $n) {
      if ($array[$j]['distance'] < $array[$max]['distance']) {
        $max = $j;
      }
      else if ($array[$j]['distance'] == $array[$max]['distance']) {
        if ($array[$j]['priority'] > $array[$max]['priority']) {
          $max = $j;
        }
      }
      ++$j;
    }
    if ($array[$i]['distance'] > $array[$max]['distance']) {
      $tmp = $array[$i];
      $array[$i] = $array[$max];
      $array[$max] = $tmp;
    }
  }

  return true;
}

$list = array(
        0 => array('paketNr' => 424, 'priority' => 1, 'distance' => 8),
        1 => array('paketNr' => 290, 'priority' => 1, 'distance' => 5),
        2 => array('paketNr' => 295, 'priority' => 2, 'distance' => 9),
        3 => array('paketNr' => 129, 'priority' => 1, 'distance' => 4),
        4 => array('paketNr' => 176, 'priority' => 3, 'distance' => 2),
        5 => array('paketNr' => 131, 'priority' => 2, 'distance' => 2),
        6 => array('paketNr' => 121, 'priority' => 1, 'distance' => 1),
        7 => array('paketNr' => 934, 'priority' => 1, 'distance' => 8),
        8 => array('paketNr' => 385, 'priority' => 1, 'distance' => 5),
        9 => array('paketNr' => 323, 'priority' => 3, 'distance' => 7),
        10 => array('paketNr' => 287, 'priority' => 2, 'distance' => 4),
        11 => array('paketNr' => 350, 'priority' => 2, 'distance' => 5)
);

$short_distance = array();
$long_distance = array();

foreach ($list as $element) {
  if ($element['distance'] < 5) {
    $short_distance[] = $element;
  }
  else {
    $long_distance[] = $element;
  }
}

// Sortieralgorithmus für Lieferungen über eine kurze Distanz
echo '<h1>Kurze Distanz</h1>';
echo '<h2>Unsortiert</h2>';
echo '<pre>', print_r($short_distance), '</pre>';

shortDistanceSort($short_distance);

echo '<h2>Sortiert</h2>';
echo '<pre>', print_r($short_distance), '</pre>';

// Sortieralgorithmus für Lieferungen über eine lange Distanz
echo '<h1>Lange Distanz</h1>';
echo '<h2>Unsortiert</h2>';
echo '<pre>', print_r($long_distance), '</pre>';

longDistanceSort($long_distance);

echo '<h2>Sortiert</h2>';
echo '<pre>', print_r($long_distance), '</pre>';

[BlackScorp]

Wieso? Entfernung ist gleich (und nicht kleiner 5!), Prio 1 kommt vor Prio 2 - oder nicht?

ja aber aufgabe ist. folgende

Angenommen ich muss Post versand verwalten und muss routen planen. Der zulieferer fährt erstmal die route bis entfernung 5 ab.. die pakete bis zur entfernung 5, müssen nach priorität verschickt werden(größere zahl zu erst) und danach nach der entfernung sortieren.. es spielt also keine rolle wie weit das ziel entfern ist, es wird erstmal nach priorität sortiert(solange entfernung unter 5 ist) ab entfernung 5, soll zu erst nach der entfernung sortiert werden, also kleinere zahl zu erst.. bei der gleichen entfernung, wird nach priorität geschaut.. also größere zahl zu erst.. in meinem ergebnis sieht man dass es 3 ziele gibt, die 5 punkte entfernt sind, jedoch hat einer davon 2 als priorität also muss das paket vor den anderen paketen mit priorität ausgeliefert werden. wobei gleiche entfernung und gleiche priorität keine rolle bei der reihenfolge haben..

@ Asipak

die erste schleife, sortiert das gesammte array nach der entfernung
danach die schleife teil das array in 2 teilen auf mit entfernung unter 5 und rest und in dem else sollte ich eigentlich nun nach priorität sortieren.. jedoch dabei dir reihenfolge der entfernung nicht zerstören.. das wollte ich damit erreichen

[Asipak]

nun scheint das ganze fast zu funktionieren

Das denke ich auch oft! Meist bedeutet es dann für mich, den ganzen Algorithmus nochmal auf Papier zu bringen und von vorne anzufangen

Jedenfalls möchte error_reporting mit dir reden! So ganz gelungen scheinen mir auch die Bedingungen in der zweiten Schleife nicht zu sein!

// for ...
if ($liste[$i]['distance'] < 5) {
        if ($liste[$i]['priority'] < $liste[$i + 1]['priority'] &&
                !empty($liste[$i + 1]['priority']) &&
                $liste[$i + 1]['distance'] < 5) {

            $tmp_arr = $liste[$i];
            $liste[$i] = $liste[$i + 1];
            $liste[$i + 1] = $tmp_arr;
        }
    } else {

        if ($liste[$i]['distance'] == $liste[$i + 1]['distance'] &&
                !empty($liste[$i + 1]['distance'])) {
            if ($liste[$i]['priority'] <= $liste[$i + 1]['priority'] &&
                    !empty($liste[$i + 1]['priority'])) {
                $tmp_arr = $liste[$i];
                $liste[$i] = $liste[$i + 1];
                $liste[$i + 1] = $tmp_arr;
            }
        }
    }
// ... end for 

Mir wird nicht ganz klar, wie der else-Block dabei mitspielt. Die Prüfungen mit empty() stehen wohl auch an der falschen Stelle (Reihenfolge), sind sogar nicht notwendig, wenn du die Indizes ($i) korrekt einschränkst.

[lstegelitz]

Wieso? Entfernung ist gleich (und nicht kleiner 5!), Prio 1 kommt vor Prio 2 - oder nicht?

[BlackScorp]

habs auch gesehen und geändert so nun scheint das ganze fast zu funktionieren:

<?php

$liste = array(
    0 => array('paketNr' => 424, 'priority' => 1, 'distance' => 8),
    1 => array('paketNr' => 290, 'priority' => 1, 'distance' => 5),
    2 => array('paketNr' => 295, 'priority' => 2, 'distance' => 9),
    3 => array('paketNr' => 129, 'priority' => 1, 'distance' => 1),
    4 => array('paketNr' => 176, 'priority' => 3, 'distance' => 2),
    5 => array('paketNr' => 131, 'priority' => 2, 'distance' => 2),
    6 => array('paketNr' => 121, 'priority' => 1, 'distance' => 4),
    7 => array('paketNr' => 934, 'priority' => 1, 'distance' => 8),
    8 => array('paketNr' => 385, 'priority' => 1, 'distance' => 5),
    9 => array('paketNr' => 323, 'priority' => 3, 'distance' => 7),
    10 => array('paketNr' => 287, 'priority' => 2, 'distance' => 4),
    11 => array('paketNr' => 350, 'priority' => 2, 'distance' => 5)
);

do {
    $zahl = 0;
    for ($i = 0; $i < count($liste); $i++) {

        if ($liste[$i]['distance'] >= $liste[$i + 1]['distance'] && !empty($liste[$i + 1]['distance'])) {
            if ($liste[$i]['distance'] == $liste[$i + 1]['distance']) {
                $zahl++;
            }
            $tmp_arr = $liste[$i];
            $liste[$i] = $liste[$i + 1];
            $liste[$i + 1] = $tmp_arr;
        } else {
            $zahl++;
        }
    }
} while ($zahl < count($liste));


for ($i = 0; $i < count($liste); $i++) {
    if ($liste[$i]['distance'] < 5) {

        if ($liste[$i]['priority'] < $liste[$i + 1]['priority'] &&
                !empty($liste[$i + 1]['priority']) &&
                $liste[$i + 1]['distance'] < 5) {

            $tmp_arr = $liste[$i];
            $liste[$i] = $liste[$i + 1];
            $liste[$i + 1] = $tmp_arr;
        }
    } else {

        if ($liste[$i]['distance'] == $liste[$i + 1]['distance'] &&
                !empty($liste[$i + 1]['distance'])) {
            if ($liste[$i]['priority'] <= $liste[$i + 1]['priority'] &&
                    !empty($liste[$i + 1]['priority'])) {
                $tmp_arr = $liste[$i];
                $liste[$i] = $liste[$i + 1];
                $liste[$i + 1] = $tmp_arr;
            }
        }
    }
}

$html = '
    <table border="1" width="100%">' . "\n" .
        '<tr>' . "\n" .
        '<th>Index</th>' . "\n" .
        '<th>Paket Nummer</th>' . "\n" .
        '<th>Priorität</th>' . "\n" .
        '<th>Entfernung</th>' . "\n" .
        '</tr>' . "\n";
foreach ($liste as $index => $paket) {
    $html .= '<tr>' . "\n";
    $html .= '<td>' . $index . '</td>' . "\n";
    $html .= '<td>' . $liste[$index]['paketNr'] . '</td>' . "\n";
    $html .= '<td>' . $liste[$index]['priority'] . '</td>' . "\n";
    $html .= '<td>' . $liste[$index]['distance'] . '</td>' . "\n";
    $html .= '</tr>' . "\n";
}

$html .= '</table>' . "\n";
echo $html;
print_R($liste);
?>

Ausgabe:

nur eine zeile scheint nicht richtig zu sortieren

EDIT: wenn sowas in meiner abschlussprüfung vorkommt... habe ich verloren

[Asipak]

Nö, noch einfacher!

$tmp_array = $liste[$i];

[edit] Da war ich wohl zu schnell

[BlackScorp]

achso du meinst?

if(bla bla){
$temp_array = $liste[$i];
$liste[$i] = $liste[$i+1];
$liste[$i+1] = $temp_array;
} 

hm.. bin da nicht direkt draufgekommen

[Asipak]

Das kommt darauf an, wie du deinen Algorithmus implementiert hast. Es wäre zumindest nicht sinnvoll, sich eine Sortierung durch einen zweiten Algorithmus wieder kaputtzumachen, wenn die Sortierung noch in bestimmtem Maße beibehalten werden soll.
Genauso sortierst du ja auch nach 2 oder mehr Spalten bei MySQL

ORDER BY col1 DESC, col2

Zunächst wird nach col1 absteigend sortiert und dann werden die Einträge, bei denen col1 denselben Eintrag hat, noch nach col2 aufsteigend sortiert.


So ganz verstehe ich auch nicht, wieso du jeden einzelnen Wert des Arrays einzeln zwischenspeicherst.

$tmp_nr = $liste[$i]['paketNr'];
$tmp_pri = $liste[$i]['priority'];
$tmp_dist = $liste[$i]['distance'];

Warum schreibst du dir nicht gleich das gesamte Array in eine temporäre Variable und schiebst das dann in einem Stück zurück an die richtige Position.

[BlackScorp]

ok bin ein stückchen weitergekommen.. habe mein array nach entfernung sortiert

$liste = array(
    0 => array('paketNr' => 424, 'priority' => 1, 'distance' => 8),
    1 => array('paketNr' => 290, 'priority' => 1, 'distance' => 5),
    2 => array('paketNr' => 295, 'priority' => 2, 'distance' => 9),
    3 => array('paketNr' => 129, 'priority' => 1, 'distance' => 1),
    4 => array('paketNr' => 176, 'priority' => 3, 'distance' => 2),
    5 => array('paketNr' => 131, 'priority' => 2, 'distance' => 2),
    6 => array('paketNr' => 121, 'priority' => 1, 'distance' => 4),
    7 => array('paketNr' => 934, 'priority' => 1, 'distance' => 8),
    8 => array('paketNr' => 385, 'priority' => 1, 'distance' => 5),
    9 => array('paketNr' => 323, 'priority' => 3, 'distance' => 7),
    10 => array('paketNr' => 287, 'priority' => 2, 'distance' => 4),
    11 => array('paketNr' => 350, 'priority' => 2, 'distance' => 5)
);

do {
    $zahl = 0;
    for ($i = 0; $i < count($liste); $i++) {

        if ($liste[$i]['distance'] >= $liste[$i + 1]['distance'] && !empty($liste[$i + 1]['distance'])) {
            if ($liste[$i]['distance'] == $liste[$i + 1]['distance']) {
                $zahl++;
            }
            $tmp_nr = $liste[$i]['paketNr'];
            $tmp_pri = $liste[$i]['priority'];
            $tmp_dist = $liste[$i]['distance'];

            $liste[$i]['paketNr'] = $liste[$i + 1]['paketNr'];
            $liste[$i]['priority'] = $liste[$i + 1]['priority'];
            $liste[$i]['distance'] = $liste[$i + 1]['distance'];

            $liste[$i + 1]['paketNr'] = $tmp_nr;
            $liste[$i + 1]['priority'] = $tmp_pri;
            $liste[$i + 1]['distance'] = $tmp_dist;
        } else {
            $zahl++;
        }
    }
} while ($zahl < count($liste));
$html = '
    <table border="1" width="100%">' . "\n" .
        '<tr>' . "\n" .
        '<th>Index</th>' . "\n" .
        '<th>Paket Nummer</th>' . "\n" .
        '<th>Priorität</th>' . "\n" .
        '<th>Entfernung</th>' . "\n" .
        '</tr>' . "\n";
foreach ($liste as $index => $paket) {
    $html .= '<tr>' . "\n";
    $html .= '<td>' . $index . '</td>' . "\n";
    $html .= '<td>' . $liste[$index]['paketNr'] . '</td>' . "\n";
    $html .= '<td>' . $liste[$index]['priority'] . '</td>' . "\n";
    $html .= '<td>' . $liste[$index]['distance'] . '</td>' . "\n";
    $html .= '</tr>' . "\n";
}

$html .= '</table>' . "\n";
echo $html; 

als nächstes muss ich alle werte , bei den distanz unter 5 ist, nach der priorität sortieren(größte zahl zu erst) wenn 2 prioritäten gleich sind, dann muss nach der entfernung geschaut werden und die mit der kleinsten entfernung wird zuerst angezeigt. wenn entfernung und priorität gleich sind, dann ist die reihenfolge egal.. so da ich denke dass es nicht möglich ist, alles in eine schleife zu packen.. muss ich nach der ersten sortierung noch eine schleife reinsetzen.. habe es so versucht:

for ($i = 0; $i < count($liste); $i++) {
    if ($liste[$i]['distance'] < 5) {

        if ($liste[$i]['priority'] < $liste[$i + 1]['priority'] &&
                !empty($liste[$i + 1]['priority']) &&
                $liste[$i + 1]['distance'] < 5) {

            $tmp_nr = $liste[$i]['paketNr'];
            $tmp_pri = $liste[$i]['priority'];
            $tmp_dist = $liste[$i]['distance'];

            $liste[$i]['paketNr'] = $liste[$i + 1]['paketNr'];
            $liste[$i]['priority'] = $liste[$i + 1]['priority'];
            $liste[$i]['distance'] = $liste[$i + 1]['distance'];

            $liste[$i + 1]['paketNr'] = $tmp_nr;
            $liste[$i + 1]['priority'] = $tmp_pri;
            $liste[$i + 1]['distance'] = $tmp_dist;
        }
    }
} 

hat wunderbar funktioniert auch bei gleicher priorität , wird der datensatz mit der kleinsten entfernung zuerst dargestellt, nur habe ich da keine abfrage

if($liste[$i]['priority'] == $liste[$i + 1]['priority']){
 //sortiere zusätzlich nach entfernung
} 

ist das ein zufall? oder benötigt man das nicht zu prüfen??

[BlackScorp]

ich weis was bubblesort ist dont worry... jedoch funktioniert das nicht einfach mit bubblesort da ich ja nicht erst nach einer kriterie sortieren muss und dann nach einer anderen.. sondern ich muss den haufen in 2 teile spalten und dann nach den beiden kriterien sortieren.. so ich mach jetzt forum aus und konzentrier mich ein wenig..

[Paul.Schramenko]

Mach doch einfach 2Bubblesorts drauf. Der erste sortiert erstmal nach Entfernung und der zweite schaut, dass wenn die Entfernung gleich ist, und schaut dann nach der priority.
Und wenn du nicht weißt, was ein Bubblesort ist, dann solltest du dir tatsächlich mal einige Grundlagen aneignen!

[Asipak]

i auf 1 setzen? ist nicht i das array index und muss es nicht 0 sein?

Klar, doch nach der Eingabe beginnen die Indizes der Zahlen bei 1

Eingabe: Natürliche Zahlen a1; : : : ; an mit n >= 1

was ist n? anzahl der datensätze?

Jap.

was ist max ? aktueller größter zwischengespeicherter wert?

Jein, der Index der Zahl, die einen Index > i hat.

und aj und amax?

j ist ein Index, genau wie max. a ist dein Array.

[BlackScorp]

i auf 1 setzen? ist nicht i das array index und muss es nicht 0 sein?

was ist n? anzahl der datensätze?
was ist max ? aktueller größter zwischengespeicherter wert?
und aj und amax?