Array "sortieren"

Hallo,

ich habe ein Array 4x5 mit Zahlen zwischen 10 und 99

a|10:40:70:50:30
b|20:70:20:30:90
c|30:60:80:10:40
d|80:50:60:70:20

nun möchte ich ein weiteres Array (4x5) mit einem "Ranking" (1 bis 4) je nachdem welche Zahl in der Spalte am höchsten ist
Das würde dann bei dem Beispiel oben so aussehen:

a|1:1:3:2
b|2:4:1:4
c|3:3:4:3
d|4:2:2:1

Wie müsste ich denn nun in etwa vorgehen? Ich denke mal das ein if-else Monster nicht die richtige Vorgehensweise ist. Mir fällt jetzt aber auch kein anderer Lösungsansatz ein

Ich hoffe ihr könnt mir da ein bissl auf die Sprünge Helfen.

Vielen Dank schonmal

Da das "Ranking" ja immer nur innerhalb einer Spalte ist, kannst du das Problem ja schonmal auf eine Spalte beschränken. Dann halt eine Schleife über alle Spalten.

Du könntest eine Schleife über die Zahlen in der Spalte machen und dir dabei die höchste Zahl merken, die im Ranking-Array noch keinen Wert hat. Das ist dann die 1. Im nächsten Durchgang wird dann quasi die zweithöchste Zahl gesucht etc.

mazal

Mal ein naiver Ansatz:

Matrix kopieren.

a|10:40:70:50:30
b|20:70:20:30:90
c|30:60:80:10:40
d|80:50:60:70:20

Spaltenweise sortieren.

a|10:40:20:10:20
b|20:50:60:30:30
c|30:60:70:50:40
d|80:70:80:70:90

Originalmatrix spaltenweise durchgehen und nachschauen an welcher Position das Element in der Spalte der sortierten Matrix ist.

a|1:1:3:3:2
b|2:4:1:2:4
c|3:3:4:1:3
d|4:2:2:4:1

mazal

*oops*

DerBaer

mazal schrieb:

Spaltenweise sortieren.

Originalmatrix spaltenweise durchgehen und nachschauen an welcher Position das Element in der Spalte der sortierten Matrix ist.

Es sind zwar nur je 4 Zeilen, aber man kann sich glaube ich eine Schleife sparen.
Du sortierst mit 2 Schleifen und suchst danach nochmals in einer.

Es sollte auch gehen, wenn du zunächst die kleinste zahl suchst. Die position an der diese Zahl steht in die zweite matrix reinkopieren. Dann die gefundene Zahl auf 100 setzten und wieder nach der kleinsten suchen, die insgesamt dann die zweitgrößte ist.
Die Folge ist im Prinzip ein Selectionsort wobei du nichtmehr die Position ermitteln musst wie bei mazals Methode

Dann die gefundene Zahl auf 100 setzten

wobei dann aber das originale array kaputt geht.

mazal

DerBaer schrieb:

mazal schrieb:

Spaltenweise sortieren.

Originalmatrix spaltenweise durchgehen und nachschauen an welcher Position das Element in der Spalte der sortierten Matrix ist.

Es sind zwar nur je 4 Zeilen, aber man kann sich glaube ich eine Schleife sparen.
Du sortierst mit 2 Schleifen und suchst danach nochmals in einer.

Es sollte auch gehen, wenn du zunächst die kleinste zahl suchst. Die position an der diese Zahl steht in die zweite matrix reinkopieren. Dann die gefundene Zahl auf 100 setzten und wieder nach der kleinsten suchen, die insgesamt dann die zweitgrößte ist.
Die Folge ist im Prinzip ein Selectionsort wobei du nichtmehr die Position ermitteln musst wie bei mazals Methode

Stimmt das ist schneller.

Wobei mir noch eine Variante eingefallen ist wird sich bei einer 4x5-Matrix kaum lohnen aber egal:

Für eine Spalte einen Heap erstellen die Elemente nacheinander mit Position in der Spalte einfügen

zB für die 2. Spalte

40-1
70-2
60-3
50-4

Dann aus dem Heap nacheinander wieder rausfischen

40-1
50-4
60-3
70-2

Das ist O(m*n*log n) vs O(m*n^2)

Aber in der praxisch wahrscheinlich wesentlich langsamer

#include <iostream>

using namespace std;

int array [4][5] = {
    {10,40,70,50,30},
    {20,70,20,30,90},
    {30,60,80,10,40},
    {80,50,60,70,20} };

int ranking [4][5];

void array_anzeigen ();
void ranking_anzeigen ();
void ranking_auf_null();
void ranking_machen ();

int main()
{
ranking_auf_null();
ranking_machen ();
array_anzeigen ();
cout << endl;
ranking_anzeigen ();
return 0;
}

void ranking_machen ()
{
int i; //index für die zahlen in einer spalte
int x; //spaltennummer
int max; //grösste gefundene zahl für spalte, die noch nicht einsortiert wurde
int maxplatz; //an welcher stelle in der spalte diese zahle steht
int platz;  //welcher platz gerade gesucht wird

x = 0;
while (x < 5)
    {
    platz = 0;
    while (platz < 5)
        {
        max = 0;
        i = 0;
        while (i < 4)
            {
            if (array[i][x] > max && ranking[i][x]==0) {
                max = array[i][x];
                maxplatz = i;
                }
            i++;
            }
            ranking[maxplatz][x] = platz;
        platz++;
        }
    x++;
    }

}

void array_anzeigen ()
{
for (int x=0; x < 4; x++) {
    for (int y=0; y < 5; y++) {
        cout << array [x][y] << " ";
        }
        cout << endl;}
}

void ranking_anzeigen ()
{
for (int x=0; x < 4; x++) {
    for (int y=0; y < 5; y++) {
        cout << " " << ranking [x][y] << " ";
        }
        cout << endl;}
}

void ranking_auf_null ()
{
for (int x=0; x < 4; x++) {
    for (int y=0; y < 5; y++) {
        ranking[x][y] = 0;
        }
}
}

Es funktioniert

mazal

Da du den Zahlenbereich beschränkst gibts nochwas schnelleres. Folgendes sollte um das Prinzip zu demonstrieren reichen.

int main()
{
	int test[] = {40, 70, 60, 50};
	int ranking[90] = { 0 };
	int i;

	for (i = 0; i < 5; ++i) {
		ranking[test[i] - 10] = i + 1;
	}
	for (i = 0; i < 90; ++i) {
		if (ranking[i] != 0) {
			printf("%d\n", ranking[i]);
		}
	}
}

*EDIT* Lohnt sich aber auch nicht bei 4x5-Matrtizen

Vielen Vielen DANK
ihr habt mir sehr geholfen!

Habe es umgesetzt und es läuft

(Das mit dem 4x5 war nur als Beispiel gedacht das eigentliche Array hat eine größe von 18x576)

Array &quot;sortieren&quot;

Array "sortieren"