2D Array sortieren

Moinsen,
hab eine kleine Prüfungsleistung zu erledigen und stecke etwas fest.
Aufgabenstellung:
Ich soll einen Sortieralgorithmus für ein beliebig großes zweidimensionales Array entwickeln. Die einzelnen Elemente sollen der Grösse nach sortiert werden.

Z.B. so:

cin>>m; // z.B. 4
cin>>n; // z.B. 3

double werte[m][n];

Die fertige Sortierung sollte dann etwa wie folgt aussehen:

1 2 3
4 5 6
7 8 9
10 11 12

Oder vielleicht so:

1 5 9
2 6 10
3 7 11
4 8 12

Welche der beiden Varianten ich verwende ist nicht vorgegeben, also am besten die Einfachste

Nun zum Problem: Ein eindimensionales Array kann ich schon sortieren , aber bei einem 2D ist mein Latein am Ende, da es sich hierbei ja sicherlich um mehrere verschachtelte for Schleifen handelt und da spielt mein beschränktes abstraktes Denkvermögen noch nicht mit.

Arbeite mit VC++ 6.0

Kann mir BITTE jemand auf die Sprünge helfen ????

DarthZiu

Naja, weiß nicht, ob das am Thema vorbei geht. Aber sortier doch einfach ein 1D-Array und teile es dann auf ein 2D-Array auf:

// PSEUDO:

int m = 4;
int n = 3;

sortiere(1D-Array);

int counter = 0;

for(int i=0; i<m; i++)
{
    for(int j=0; j<n; j++)
    {
        2D-Array[i][j] = 1D-Array[counter];
        counter++;
    }
}

Die Idee hatte ich auch schon aber nach Rücksprache mit dem Prof ist mir das untersagt worden

DarthZiu

Also mir fällt kein Algorithmus ein, mit dem man ein 2D-Array sortieren kann. Wär aber mal interessant, ob es sowas gibt.
Wikipedia schweigt sich zu dem Thema auch aus.

Trotzdem erstmal vielen Dank. Werde dann wohl noch einige Nächte mit dicken Augenringen am Laptop sitzen und rumtesten

DarthZiu

Frag dein Prof doch nochmal, ob er dir wenigstens einen Ansatz geben kann. Kann dich ja nicht einfach so ins kalte Wasser werfen.

Oh doch, genau so ein A.... ist das

C++ Forumbot

Dieser Thread wurde von Moderator/in SideWinder aus dem Forum DOS und Win32-Konsole in das Forum C++ verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

Z2

2D-Array als 1D-Array behandeln:

Array[i%m][i/m]

i würde dann von 0 bis n*m-1 laufen

Swordfish

#include <cstdlib>
#include <iostream>
#include <ctime>

using namespace std;

void print_array2d( int **array, size_t rows, size_t cols );
void sort_array2d_horz( int **array, size_t rows, size_t cols );
void sort_array2d_vert( int **array, size_t rows, size_t cols );

int main( int argc, char *argv[] )
{
	size_t	cols	= 0;
	size_t	rows	= 0;
	int		max		= 0;

	srand( ( unsigned int ) time( 0 ) );

	cout << "columns: ";
	cin  >> cols;
	cout << "rows:    ";
	cin  >> rows;
	cout << "maximum: ";
	cin  >> max;

	cout << endl;

	if( !( rows && cols ) ) {
		cout << "Number of columns and rows needs to be > 0!" << endl;
		return -1;
	}

	max = ( max < 0 ? -max : max ) + 1;

	int **array = new int*[rows];
	for( size_t i = 0; i < rows; ++i )
		array[i] = new int[cols];

	for( size_t y = 0; y < rows; ++y )
		for( size_t x = 0; x < cols; ++x )
 			array[y][x] = rand() % max;

	cout << "Unsorted, random values:" << endl;
	print_array2d( array, rows, cols );

	sort_array2d_horz( array, rows, cols );

	cout << endl << "horizontal sorted array:" << endl;
	print_array2d( array, rows, cols );

	sort_array2d_vert( array, rows, cols );

	cout << endl << "vertical sorted array:" << endl;
	print_array2d( array, rows, cols );

    for( size_t i = 0; i < rows; ++i )
		delete[] array[i];
	delete[] array;
	array = 0;

	return 0;
}

void print_array2d( int **array, size_t rows, size_t cols )
{
	for( size_t y = 0; y < rows; ++y ) {
		for( size_t x = 0; x < cols; ++x ) {
			cout.width( 4 );
			cout << right << array[y][x];
		}
		cout << endl;
	}
}

void sort_array2d_horz( int **array, size_t rows, size_t cols )
{
	int tmp = 0;
	bool sorted = false;

	do {
		sorted = true;
		for( size_t y = 0; y < rows; ++y ) {
			for( size_t x = 0; x < cols; ++x ) {
				if( !( ( y == ( rows - 1 ) ) && ( x == ( cols - 1 ) ) ) ) {
					if( x < ( cols - 1 ) ) {
						if( array[y][x] > array[y][x+1] ) {
							tmp = array[y][x];
							array[y][x] = array[y][x+1];
							array[y][x+1] = tmp;
							sorted = false;
						}
					} else {
						if( array[y][x] > array[y+1][0] ) {
							tmp = array[y][x];
							array[y][x] = array[y+1][0];
							array[y+1][0] = tmp;
							sorted = false;
						}
					}
				}
			}
		}
	} while( !sorted );
}

void sort_array2d_vert( int **array, size_t rows, size_t cols )
{
	int tmp = 0;
	bool sorted = false;

	do {
		sorted = true;
		for( size_t x = 0; x < cols; ++x ) {
			for( size_t y = 0; y < rows; ++y ) {
				if( !( ( y == ( rows - 1 ) ) && ( x == ( cols - 1 ) ) ) ) {
					if( y < ( rows - 1 ) ) {
						if( array[y][x] > array[y+1][x] ) {
							tmp = array[y][x];
							array[y][x] = array[y+1][x];
							array[y+1][x] = tmp;
							sorted = false;
						}
					} else {
						if( array[y][x] > array[0][x+1] ) {
							tmp = array[y][x];
							array[y][x] = array[0][x+1];
							array[0][x+1] = tmp;
							sorted = false;
						}
					}
				}
			}
		}
	} while( !sorted );
}

Ist zwar nur ein dämlicher Bubblesort, aber bei solch einer Aufgabenstellung frag' ich mich sowieso, ob euer Professor ganz da ist.

Greetz, Swordfish

Wow ist das cool, zwar ein riesen Aufwand aber hauptsache es funzt.
DANKE

Swordfish

Na besten Dank für deinen Dank, aber WTF ist daran kompliziert?
Simpler gehts nimmer .

Greetz, Swordfish