Sortowanie tablicy dwuwymiarowej

Question

Witam mam taki problem muszę posortować tablice dwuwymiarową nie mogę przepisać jej do tablicy jednowymiarowej oraz nie mogę wykorzystywać wbudowanych algorytmów. Moim pytaniem jest czy istnieje jakaś implementacja np algorytmu qsort lub innego oprócz tych najprostszych bombelkowe czy przez wybieranie,  które zrealizują to sortowanie?

Comments

Jak pokażesz jak definiujesz tę tablicę 2-wymiarową, to będzie można pomóc. W C czy C++ można ją definiować na kilka sposobów.

Answer 1

#include <iostream>

using namespace std;
void sortowanieDwuWymiarowe(int arr[][5], const int firstSize, const int secoundSize);
int main()
{
    const int ONESIZE = 4;
    const int TWOSIZE = 5;
    int arr[ONESIZE][TWOSIZE] = {0};
    for(int i = 0; i < ONESIZE; i++) {
        for(int j = 0; j < TWOSIZE; j++) {
            cin>>arr[i][j];
        }
    }
    cout<<endl;
    sortowanieDwuWymiarowe(arr, ONESIZE, TWOSIZE);

    for(int i = 0; i < ONESIZE; i++) {
        for(int j = 0; j < TWOSIZE; j++) {
            cout<<arr[i][j]<<" ";
        }
    }
    return 0;
}

void Qsort(int arr[][5], int first, int last) {
    if(first > last) {
        return;
    }
    int left = first, right = last+1;
    int pivot = arr[first/5][first%5];
    while(true) {
        do {
            left++;
        }while(left <= last and arr[left/5][left%5] < pivot);
        do {
            right--;
        }while(arr[right/5][right%5] > pivot);

        if(left > right) {
            break;
        }
        swap(arr[left/5][left%5],arr[right/5][right%5]);
    }
    swap(arr[first/5][first%5],arr[right/5][right%5]);

    first++;
    Qsort(arr,first,right - 1);
    Qsort(arr,right + 1,last - 1);
}

void sortowanieDwuWymiarowe(int arr[][5], const int firstSize, const int secoundSize) {
    Qsort(arr,0, firstSize*secoundSize-1);
}

Aktualnie mam coś takiego i działa to dla danych wprowadzanych od końca np 20,19,18,...,3,2,1 lecz dla typowo losowych danych już przestaje działać

 

Comments

Do zwykłej procedury sortowania, w miejsce adresowania elementu tablicy np. tablica[3] wstawiasz funkcję na przykład tablica2D[3] która ci wylicza rząd i kolumnę w bardzo prosty sposób. Dzielisz z resztą i masz rząd a reszta z dzielenia to kolumna. Tylko dopasuj sobie dokładnie brzegi zakresu żeby się zgadzały obliczenia.