Sortowanie Tablica N na N

Mam pytanie... jak posortować tablice dwuwymiarową za pomocą quicksort? Napisalem coś takiego:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define W 7

int por(const void* a, const void * b) {

 const int _a = (*(int*)a);
 const int _b = (*(int*)b);
 if (_a < _b) return -1;
 if (_a==_b) return 0;
 if (_a>_b) return 1;

}
int main(void)
{	
 int i;	
 int macierz[W];	
 srand(time(NULL));

 printf("\nElementy przed sortowaniem: \n");
	
	for(i=0; i<W; i++)
	{	

		macierz[i]= (1+rand() % 5); // Dolna granica = 1, górna = 10 
		printf("%d ", macierz[i]);				
				
		
	}

 printf("\nElementy po sortowaniu: \n");
	
	qsort(macierz, W, sizeof(int), por);
	
	for(i=0; i<W; i++)
	{	

		printf("%d ", macierz[i]);				
					
	}
	
return 0;
}

Sortowanie tablicy jedno wymiarowej... ok działa ale teraz zastanawiam sie jak zrobic to samo na tablicy dwuwymiarowej.... Głownie chodzi mi zeby elementy tablicy były poukładane rosnąco.

Jak to można zrobić?

to zależy, jeśli chcesz mieć tablicę o ustalonych rozmiarach WxN, to... w sortowaniu praktycznie zmieniać nie musisz, po prostu zmień definicję macierzy:

/* dodatkowy wymiar */
#define N 5
/* definicja macierzy */
int macierz[W][N];

trochę inaczej wypisywanie, wypełnianie będzie:

for(i=0; i<W; i++) {
        for(j=0; j<N; j++) {
            macierz[i][j]= (1+rand() % 10); // Dolna granica = 1, górna = 10
            printf("%d ", macierz[i][j]);
            }
        printf("\n");
        }

a samo sortowanie to będzie:

qsort(macierz, W*N, sizeof(int), por);

wynika to stąd, że tablica WxN jest w pamięci blokiem WxN liczb ułożonych po kolei wiersz za wierszem. Dla dynamicznych tablic to już tak prosto nie będzie. W zasadzie to nie widzę dla takich tablic zastosowania qsort w prosty sposób.

Kamil_T napisał(a)

Sortowanie tablicy jedno wymiarowej... ok działa ale teraz zastanawiam sie jak zrobic to samo na tablicy dwuwymiarowej.... Głownie chodzi mi zeby elementy tablicy były poukładane rosnąco.

przede wszystkim wyjasnij, co rozumiesz przez 'sortowanie rosnaco dwuwymiarowo', bo to nie jest takie oczywiste.. wszystkie 3 ponizej sa posortowane w '2d', kazda inaczej, i kazde sortowanie inaczej w kodzie wyglada..

[3 5 6]    [1 2 3]    [1 2 2]
[1 2 3]    [2 5 6]    [3 3 5]
[2 5 6]    [3 5 6]    [5 6 6]

Ok sortowanie jakoś działa. Mam pytanie jak zamienić tablice 2D na 1D... bo musze zrobić projekt w MPI a tam jakas instrukcja przesyla tablice tylko 1D

Kamil, do jasnej cholery, nie wyciągnąłeś wniosków z funkcji qsort?
Statyczną tablicę 2D możesz traktować jak 1D. Piszesz w C, więc może nawet rzutować nie musisz (może funkcja pobiera void*). A jak musisz, no to postaw przed tą nazwą tej cholernej tablicy to nieszczęsne (int*).

A jak chcesz zamienić po ludzku, wg jakiejś metody, to wyciągnij wnioski z kolei z wypowiedzi queztalcoatla: JAK ZAMIENIĆ?! Dane 2D można rozłożyć do wektora na 1000 sposobów.

I po cholerę w ogóle chcesz przekazać funkcji oczekującej 1D tablicę dwuwymiarową?!

/* ps. */ LPCSTR cholera = b_brzydkie_przeklenstwa[ rand() % N ];

Ranides nie złość się

Mam pewien projekt który ma macierz n na n i on sobie sortuje wiersz po wierszu (to juz mam w sekwencyjnym) a nastepnie liczy mediane itd. Ale żeby to zrównoleglić to za pomocą instrukcji MPI_Scatter musze przesłać tablice tylko że ta instrkcja lubi tablice jedno wymiarowe...

Jutro rano wstanę bede myślał

tego ze MPI_Scatter dziala tylko na wektorze 1D nie prezskoczysz, bo .... to wynika z definicji tej funkcji. ona ma go podzielic i (losowo) rozeslac.

jesli masz tablice 2D bedaca jedym duzym blokiem pamieci i chcesz powysylac wiersze, to rzeczywiscie, zakladajac ze wiersze sa rownej dlugosci :) mozesz uzyc scattera --- wtedy podzial na rowne czesci, jesli size czesci = dlugosc wiersza, sprawi ze faktycznie wyslesz po 1 calym wierszu do 1 odbiorcy. ale.. wsyzstkie te warunki musza byc spelnione scisle

jesli masz tablice ktora nie jest pojedynczym duzym blokiem pamieci (czyli int** albo int*[], a NIE int [][], ani NIE int (*)[] ktore nimi akurat są), to nie ma bata.. scattera wprost nie uzyjesz zebys sie skichal..

• musisz albo recznie 'przepakowac' tablice na taka ktora nim jest i spelnia w/w warunki i dopiero na niej uzyc MPI_Scatter
• albo ... nie mozesz uzyc MPI_Scatter.

bez obaw. MPI_Scatter wbrew pozorom jest dosc prosta funkcja. Na pewno juz poznales MPI_Send i MPI_Recv oraz ich asynchroniczne odpowiedniki? w takim razie, mozesz napisac swoj odpowiednik MPI_Scatter ktory dziala na tablicy 2d - dyn:

moj_scatter(int** tab, unsigned int X, unsigned Y)
    for i=0, i<X, i++
        wylosuj odbiorce
        wyslij asyc do niego tablice Y-elementowa  tab[i]
        zapamietaj uchwyt operacji async
    zakoncz zapamietane operacje async