Szybkie sortowanie macierzy 10x10 metodą "dziel i zwyciężaj"

Witajcie.
Mam do napisania program w którym mam posortować macierz 10x10 szybką metodą "dziel i zwyciężaj". Znalazłem na internecie kod sortowania, ale jest to kod dotyczący tak jakby tylko jednego wiersza. A ja potrzebuję ten sam kod ale do macierzy M[n][m] a nie do tablicy d[i]. Sam próbowałem to jakoś pozmieniać ale za chiny nie udaje mi się to ... Więc proszę was o pomoc ;)

void Sortuj_szybko(int lewy, int prawy)
{
  int i,j,piwot;

  i = (lewy + prawy) / 2;
  piwot = d[i]; d[i] = d[prawy];
  for(j = i = lewy; i < prawy; i++)
  if(d[i] < piwot)
  {
    swap(d[i], d[j]);
    j++;
  }
  d[prawy] = d[j]; d[j] = piwot;
  if(lewy < j - 1)  Sortuj_szybko(lewy, j - 1);
  if(j + 1 < prawy) Sortuj_szybko(j + 1, prawy);
} 

to jest po prostu quick sort. Wiec uzyj juz gotowego

std::sort(poczatek, koniec, pred);

fasadin ale że jak to ma wyglądać ??? Bo ja w tym programie najpierw mam zastosować funkcję rand() do utworzenia macierzy z liczb pseudolosowych a pozniej ją posortować.

http://stackoverflow.com/questions/11344228/how-to-sort-elements-into-c-matrix

(zajelo mi to 15 sekund znalezenie... wystarczylo wpisac w google "std sort matrix"...)

fasadin rozumiem że jest to szybsza metoda, ale ja mało co rozumiem z tego kodu który jest na tej stronie ..... Jestem początkujący i nie mógł byś jakoś przekształcić tego kodu który ja znalazłem, żeby sortował dla macierzy 10x10 a nie tylko dla tablicy /?

Jak na razie próbuję to zrobic tak żeby z tą macierzą przejsc do tablicy jednowymiarowej i tak to posortować a pozniej znowu na dwuwymiarową przekształcić ale jak na razie same zera mi wyskakują w posortowanej macierzy...

nie nie napisze Ci niczego. Chcesz zebym Ci cos napisal to zaplac 50 euro
Moge Ci pomoc zrozumiec co chcesz zrobic, ale do tego musisz tego chciec

Teraz seria Czy wiesz ze:

Czy wiesz ze maciez to tablica dwuwymiarowa?

majac ta wiedze mozesz sobie poradzic z reszta

To ze jestes poczatkujacy i nie rozumiesz tamtych "kodow" nie zwalnia Cie z myslenia i czytania i po prostu uczenia sie co to tamto robi.

Hahah, 50 euro xd Tak jak pisałem teraz próbuję iść inną drogą i przejśc z tą macierzą na tablice jednowymiarową. I odpowiem na Twoje głupie komentarze. Nie nie czekam na gotowca ..... Cały program nie opiera się tylko na tej części sortowania. Ja ciągle się uczę i jeżeli mi nie chcesz pomóc to po prostu nie pisz i się nie ośmieszaj....

Do tego mi się udało teraz dojśc, ale dalej ma jakiś błąd, którego nie widzę i nie sortuje jak na razie macierzy.

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <time.h>

using namespace std;

const int n = 10, m = 10; // LiczebnoϾ zbioru

int d[100];
int M[n][m];


//----------------------------------------------------
// sortowanie
void Sortuj(int lewy, int prawy)
{
  int i,j,piwot;

  i = (lewy + prawy) / 2;
  piwot = d[i]; d[i] = d[prawy];
  for(j = i = lewy; i < prawy; i++)
  if(d[i] < piwot)
  {
    swap(d[i], d[j]);
    j++;
  }
  d[prawy] = d[j]; d[j] = piwot;
  if(lewy < j - 1)  Sortuj(lewy, j - 1);
  if(j + 1 < prawy) Sortuj(j + 1, prawy);

}


int main()
{
  int i,j;

  srand((unsigned)time(NULL));

  cout << "Sortowanie szybkie" << endl;
//----------------------------------------------------------------------
//wype³niamy tablicê d[] liczbami pseudolosowymi

  for(i = 0; i < n; i++)
    for(j = 0; j < n; j++)
        M[i][j] = rand() % 100;
  for(i = 0; i < n; i++)
    for(j = 0; j < n; j++)
        cout << setw(4) << M[i][j];
    cout << endl;


//------------------------------------------------------------------
//Przejście z tablicy dwuwymiarowej do jednowymiarowej
int t = 0;
for (int i = 0; i < 10; i++)
    {
        for (int j = 0; j < 10; j++)
        {
            d[t] = M[i][j];
            t++;
        }
    }

// Sortujemy

Sortuj(0,n - 1);

//------------------------------------------------------------------
//Przejście z tablicy jednowymiarowej do dwuwymiarowej
int x = 0;
for (int i = 0; i < 10; i++)
    {
        for (int j = 0; j < 10; j++)
        {
            M[i][j]= d[x];
            x++;
        }
    }


// Wyœwietlamy wynik sortowania

  cout << "Po sortowaniu:" << endl;
    for(i = 0; i < n; i++)
        for(j = 0; j < n; j++)
            cout << setw(4) << M[n][m];
  cout << endl;

  return 0;
}
 

Dobra już poradziłem sobie bez waszej pomocy ;)

Po dłuższej chwili patrzenia do konsoli okazało się że jednak dalej coś nie tak. Zamiast sortowania każdego wiersza od najmniejszego do największego elementu, program sortuje tylko pierwszy wiersz a następne tylko przepisuje w niezmienionej formie....

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <time.h>

using namespace std;

const int n = 10, m = 10; // LiczebnoϾ zbioru

int d[100];
int M[n][m];


//----------------------------------------------------
// sortowanie
int Sortuj(int lewy, int prawy)
{
  int i,j,piwot;

  i = (lewy + prawy) / 2;
  piwot = d[i]; d[i] = d[prawy];
  for(j = i = lewy; i < prawy; i++)
  if(d[i] < piwot)
  {
    swap(d[i], d[j]);
    j++;
  }
  d[prawy] = d[j]; d[j] = piwot;
  if(lewy < j - 1)  Sortuj(lewy, j - 1);
  if(j + 1 < prawy) Sortuj(j + 1, prawy);

  return(0);

}


int main()
{
  int i,j;

  srand((unsigned)time(NULL));

  cout << "Sortowanie szybkie" << endl;
//----------------------------------------------------------------------
//wype³niamy tablicê d[] liczbami pseudolosowymi

  for(i = 0; i < n; i++)
    for(j = 0; j < n; j++)
        M[i][j] = rand() % 100;
  for(i = 0; i < n; i++)
    {
        for(j = 0; j < n; j++)
        cout<< setw(4) << M[i][j];
        cout << endl;
    }

//------------------------------------------------------------------
//Przejście z tablicy dwuwymiarowej do jednowymiarowej
int t = 0;
for (int i = 0; i < 10; i++)
    {
        for (int j = 0; j < 10; j++)
        {
            d[t] = M[i][j];
            t++;
        }
    }

// Sortujemy

Sortuj(0,n - 1);

//------------------------------------------------------------------
//Przejście z tablicy jednowymiarowej do dwuwymiarowej
int x = 0;
for (int i = 0; i < 10; i++)
    {
        for (int j = 0; j < 10; j++)
        {
            M[i][j]= d[x];
            x++;
        }
    }


// Wyœwietlamy wynik sortowania

cout << "Po sortowaniu:" << endl;

for (int i=0;i<n;i++)
    {
        for (int j=0; j<m; j++)
            cout<<M[i][j]<<"   ";
        cout<<endl;
    }

  return 0;
}
 

Super:) przy okazji Twojego poprzedniego wątku pokazałem Ci jak sortować wiersze tablicy dwuwymiarowej, teraz zmienił się tylko algorytm sortowania. Jeżeli chcesz sortować poszczególne wiersze a nie całą tablicę to konwersja do tablicy jednowymiarowej nie ma najmniejszego sensu bo i tak niczego nie upraszcza. Sortuj po prostu każdy wiersz tak jakby był osobną tablicą a w kodzie QuickSorta zmień po prostu sposób odwoływania się do kolejnych elementów tablicy z d[numer elementu] na d[numer aktualnie sortowanego wiersza][numer elementu]. No chyba, że jednak chcesz posortować całą tablicę...

Twój kod nie działa tak jakbyś chciał bo:

// Sortujemy
 
Sortuj(0,n - 1);

uruchamiasz sortowanie dla pierwszych n elementów czyli właśnie dla pierwszego wiersza. Zamiast kopiować bez zastanowienia kawałki kodu z internetu postaraj się:

1. Zrozumieć algorytm
2. jak trzeba to zapisać sobie pseudokod
3. napisać implementację
4. Stworzyć kilka testów i jak coś się sypie to użyć debuggera i/lub głowy do znalezienia błędu
5. Zapytać na forum:)

Sortuj(0,n*m-1); 

raczej tak powinno być...

Niikelion niestety nie o to chodzi ;) Bo tak to będzie sortować wszystkie elementy od najmniejszego do największego, a ja potrzebuję tak posortować ale tylko w wierszach ;) Próbuję teraz to zrobić bez zamiany na tą jednowymiarową, ale jakies dziwne błędy mi się pokazują. Dymul w zupełności rozumiem Twój tok rozumowania i od początku chciałem tak zrobić tylko miałem ( i chyba nadal mam) problem z tym jak zrobić właśnie żeby przeskakiwało z jednego wiersza do drugiego. Teraz spróbowałem to jakąś pętlą, ale znowu chyba nie wyszło ...

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <time.h>

using namespace std;

const int n = 10, m = 10; // LiczebnoϾ zbioru
int d[100];
int M[n][m];


//----------------------------------------------------
// sortowanie
int Sortuj(int lewy, int prawy)
{
int i,j,piwot;

for(int x=0 ; x < n ; x++)
{
  i = (lewy + prawy) / 2;
  piwot = d[x][i]; d[x][i] = d[x][prawy];
  for(j = i = lewy; i < prawy; i++)
  if(d[x][i] < piwot)
  {
    swap(d[x][i], d[x][j]);
    j++;
  }
  d[x][prawy] = d[x][j]; d[x][j] = piwot;
  if(lewy < j - 1)  Sortuj(lewy, j - 1);
  if(j + 1 < prawy) Sortuj(j + 1, prawy);
}
  return(0);

}


int main()
{
  int i,j;

  srand((unsigned)time(NULL));

  cout << "Sortowanie szybkie" << endl;
//----------------------------------------------------------------------
//wype³niamy tablicê d[] liczbami pseudolosowymi

  for(i = 0; i < n; i++)
    for(j = 0; j < n; j++)
        M[i][j] = rand() % 100;
  for(i = 0; i < n; i++)
    {
        for(j = 0; j < n; j++)
        cout<< setw(4) << M[i][j];
        cout << endl;
    }


Sortuj(0, n - 1);


// Wyœwietlamy wynik sortowania

cout << "Po sortowaniu:" << endl;

for (int i=0;i<n;i++)
    {
        for (int j=0; j<m; j++)
            cout<<M[i][j]<<"   ";
        cout<<endl;
    }

  return 0;
}
 

Chyba nie wyszło czyli nie chce mi się nawet przeczytać jakie błędy wypluwa kompilator.

W funkcji sortuj używasz tablicy jednowymiarowej o wdzięcznej nazwie d jakby było tablicą o równie wdzięcznej nazwie M. Usuń deklarację d bo jest niepotrzebna, i zmień nazwy w funkcji sortuj z d na M. Poza tym działa.

Jezuuuu jaki głupi błąd XD Zamieszałem sobie trochę z tą zamianą dwuwymiarowej do jednowymiarowej. No teraz wszystko śmiga jak trzeba, aż miło. Dzięki wielkie ;) Ostateczna dobra wersja :

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <time.h>

using namespace std;

const int n = 10, m = 10; // LiczebnoϾ zbioru

int M[n][m];


//----------------------------------------------------
// sortowanie
int Sortuj(int lewy, int prawy)
{
int i,j,piwot;

for(int x=0 ; x < n ; x++)
{
  i = (lewy + prawy) / 2;
  piwot = M[x][i]; M[x][i] = M[x][prawy];
  for(j = i = lewy; i < prawy; i++)
  if(M[x][i] < piwot)
  {
    swap(M[x][i], M[x][j]);
    j++;
  }
  M[x][prawy] = M[x][j]; M[x][j] = piwot;
  if(lewy < j - 1)  Sortuj(lewy, j - 1);
  if(j + 1 < prawy) Sortuj(j + 1, prawy);
}
  return(0);

}


int main()
{
  int i,j;

  srand((unsigned)time(NULL));

  cout << "Sortowanie szybkie" << endl;
//----------------------------------------------------------------------
//wype³niamy tablicê d[] liczbami pseudolosowymi

  for(i = 0; i < n; i++)
    for(j = 0; j < n; j++)
        M[i][j] = rand() % 100;
  for(i = 0; i < n; i++)
    {
        for(j = 0; j < n; j++)
        cout<< setw(4) << M[i][j];
        cout << endl;
    }


Sortuj(0, n - 1);


// Wyœwietlamy wynik sortowania

cout << "Po sortowaniu:" << endl;

for (int i=0;i<n;i++)
    {
        for (int j=0; j<m; j++)
            cout<<setw(3)<< M[i][j]<<"   ";
        cout<<endl;
    }

  return 0;
}