Sortowanie kolumny – dlaczego kod daje błędną odpowiedź?

0

Cześć panie i panowie mam zadanko https://www.spoj.com/WWSIASD/problems/ASD_5_2/ oto mój kod:
który daje błędną odpowiedź co jest ?

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

const int C=3;
const int R=5;

void druk(int tab[R][C],int col,int row)
{
int i,j;
for(int i=0;i<row;i++)
{
for(int j=0;j<col;j++)
    printf("%d",tab[i][j]);
printf("\n");
} 
}

void zam(int *a,int *b)
{
int c;
c=*a;
*a=*b;
*b=c;
return;
}

void sort(int tab[R][C],int ile_col,int nr_col,int low,int high)
{
    int i,j,k;
    int x;
    x=tab[(low+high)/2][nr_col];
    i=low;
    j=high;

do
{
    while(tab[i][nr_col]<x)
        ++i;
    while(tab[j][nr_col]>x)
        ++j;

    if(i<=j)
    {
        for(k=0;k<ile_col;k++)
            zam(&tab[i][k],&tab[j][k]);
        ++i;
        ++j;

}
}

while(i<j);

    if(low<j)
        sort(tab,ile_col,nr_col,low,j);
    if(high>i)
        sort(tab,ile_col,nr_col,i,high);
    return;
}

int main()
{
  int nr_col;
  int tab[R][C];

  int i,j;
    time_t start,end;
  double dif;
  int col=C;
  int row=R;

  srand(time(NULL));

  for(j=0;j<col;j++)
      for(i=0;i<row;i++)
          tab[i][j]=rand()%4;

  druk(tab,col,row);

  printf("Enter");
  getchar();
  time(&start);

for(nr_col=0;nr_col<col;nr_col++)
      {
          sort(tab,col,nr_col,R,row-1);
          druk(tab,col,row);
          printf("Enter");
          getchar();
      }
time(&end);
dif=difftime(end,start);
printf("Czas sortowania\n",dif);
printf("ENTER...\n");
getchar();

return 0;
}
1
printf("%d",tab[i][j]);

nie oddzielasz spacjami

printf("Enter");

Na jakiej podstawie z przykładowego wyjścia wywnioskowałeś, że należy wypisać "Enter"?

1 0.89 0.33 0 1.33
2.5 1.97 0.33 0.5 2.33
1.5 -2.28 2 0.5 3
1 -3.94 2.33 0.5 2.83
2 -3.53 2.33 0.5 3.83
2 1.41 1 1 2
0 1.06 0.67 1.5 -0.83
1.5 -2.72 2.33 1.5 2.33
2.5 3.58 0 2 0.5
2.5 3.47 0.33 2 0.83
0 1 1 2 -1
2.5 2.58 1 2 1.5
0 -3.44 2.33 2 0.33
0 -3.44 2.33 2 0.33
2 -3.7 2.67 2 2.67
1 3.89 0.33 3 -1.67
1.5 3.22 1 3 -0.5
2 1.64 1.67 3 0.67
0.5 4.1 0.33 3.5 -2.67
2 -0.53 2.33 3.5 0.83
0

wiem ze nie trzeba , lecz chcę najpierw dowiedzieć się czemu nie sortuje ..

0

Niespecjalnie chce mi się wgryzać w ten kod. Zadanie z użyciem std::vector i std::sort/std::stable_sort powinno być trywialne.

0

Po pierwsze dzięki za odpowiedzi o tej godzinie , po drugie żeby było trywialne to mnie by tutaj nie było :)

3

Żeby nie rzucać słów na wiatr w 15 minut naklepałem prymitywne rozwiązanie:

int main()
{
    int col_count, sort_column_count;
    vector<int> sort_columns;
    cin >> col_count;
    cin >> sort_column_count;
    copy_n(
        istream_iterator<double>(cin),
        sort_column_count,
        back_inserter(sort_columns)
    );

    vector<vector<double>> matrix;

    double temp;
    vector<double> new_row;
    while(cin >> temp) {
        new_row.push_back(temp);
        if(new_row.size() == col_count) {
            matrix.push_back(move(new_row));
            new_row = {};
        }
    }

    auto cmp_by_column = [](int n){
        auto cmp = [=](auto&& l, auto&& r){
            return l.at(n) < r.at(n);
        };
        return cmp;
    };

    for(int i = 0; i < sort_column_count; i++) {
        stable_sort(matrix.begin(), matrix.end(), cmp_by_column(sort_columns[i]-1));
    }

    for(auto const& r : matrix) {
        copy(r.begin(), r.end(), ostream_iterator<double>(cout, " "));
        cout << '\n';
    }
}

Zapewne niektóre elementy składniowe mogą być niezrozumiałe, ale powiedzmy, że to takie prawie wzorcowe rozwiązanie bez nadmiernych optymalizacji. Na spoju wykonało się w 0.54s, więc bez rewelacji, ale bez tragedii.

0

Rozumiem że sam int main() wykonał ci się w 0.54 sekundy , bo na razie w takiej formie to nie zabardzo idzie :)

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

const int C=3;
const int R=5;

void druk(int tab[R][C],int col,int row)
{
int i,j;
for(int i=0;i<row;i++)
{
for(int j=0;j<col;j++)
    printf("%d",tab[i][j]);
printf("\n");
} 
}

void zam(int *a,int *b)
{
int c;
c=*a;
*a=*b;
*b=c;
return;
}

void sort(int tab[R][C],int ile_col,int nr_col,int low,int high)
{
    int i,j,k;
    int x;
    x=tab[(low+high)/2][nr_col];
    i=low;
    j=high;

do
{
    while(tab[i][nr_col]<x)
        ++i;
    while(tab[j][nr_col]>x)
        ++j;

    if(i<=j)
    {
        for(k=0;k<ile_col;k++)
            zam(&tab[i][k],&tab[j][k]);
        ++i;
        ++j;

}
}

while(i<j);

    if(low<j)
        sort(tab,ile_col,nr_col,low,j);
    if(high>i)
        sort(tab,ile_col,nr_col,i,high);
    return;
}

int main()
{
    int col_count, sort_column_count;
    vector<int> sort_columns;
    cin >> col_count;
    cin >> sort_column_count;
    copy_n(
        istream_iterator<double>(cin),
        sort_column_count,
        back_inserter(sort_columns)
    );

    vector<vector<double>> matrix;

    double temp;
    vector<double> new_row;
    while(cin >> temp) {
        new_row.push_back(temp);
        if(new_row.size() == col_count) {
            matrix.push_back(move(new_row));
            new_row = {};
        }
    }

    auto cmp_by_column = [](int n){
        auto cmp = [=](auto&& l, auto&& r){
            return l.at(n) < r.at(n);
        };
        return cmp;
    };

    for(int i = 0; i < sort_column_count; i++) {
        stable_sort(matrix.begin(), matrix.end(), cmp_by_column(sort_columns[i]-1));
    }

    for(auto const& r : matrix) {
        copy(r.begin(), r.end(), ostream_iterator<double>(cout, " "));
        cout << '\n';
    }
}

Znaczy zapytam inaczej , jak to się ma do mojego kodu bo nie ukrywam że ten co mi wysłałeś jest nie w pełni zrozumiałe dla mnie , z tym co ja napisałem . Napisałeś że program wykonał ci się w 0.54s no ok ale co tam wkleiłeś ? Bardzo doceniam twój wkład i wysiłek w napisanie tego kodu , lecz inne nazwy zmiennych są troszkę mylące . Pozdrawiam

Czy możesz dokładnie określić kod jakiego użyłeś ,który ci się wykonał w 0.54 s ?

Czy ktoś wie dlaczego na spoju ten kod wyruca błędną odpowiedź ? i jak ten kod powinien poprawnie wyglądac ?

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

const int C=3;
const int R=5;

void druk(int tab[R][C],int col,int row)
{
int i,j;
for(int i=0;i<row;i++)
{
for(int j=0;j<col;j++)
    printf("%d",tab[i][j]);
printf("\n");
} 
}

void zam(int *a,int *b)
{
int c;
c=*a;
*a=*b;
*b=c;
return;
}

void sort(int tab[R][C],int ile_col,int nr_col,int low,int high)
{
    int i,j,k;
    int x;
    x=tab[(low+high)/2][nr_col];
    i=low;
    j=high;

do
{
    while(tab[i][nr_col]<x)
        ++i;
    while(tab[j][nr_col]>x)
        ++j;

    if(i<=j)
    {
        for(k=0;k<ile_col;k++)
            zam(&tab[i][k],&tab[j][k]);
        ++i;
        ++j;

}
}

while(i<j);

    if(low<j)
        sort(tab,ile_col,nr_col,low,j);
    if(high>i)
        sort(tab,ile_col,nr_col,i,high);
    return;
}

int main()
{
  int nr_col;
  int tab[R][C];

  int i,j;
    time_t start,end;
  double dif;
  int col=C;
  int row=R;

  srand(time(NULL));

  for(j=0;j<col;j++)
      for(i=0;i<row;i++)
          tab[i][j]=rand()%4;

  druk(tab,col,row);

  printf("Enter");
  getchar();
  time(&start);

for(nr_col=0;nr_col<col;nr_col++)
      {
          sort(tab,col,nr_col,R,row-1);
          druk(tab,col,row);
          printf("Enter");
          getchar();
      }
time(&end);
dif=difftime(end,start);
printf("Czas sortowania\n",dif);
printf("ENTER...\n");
getchar();

return 0;
}
0

Po co się zamęczasz pisaniem własnego sortowania? W STL masz gotowca, który sam się optymalizuje dla zadanego kontenera.

A twój kod daje błędną odpowiedź, bo drukuje rzeczy, o których nie ma ani słowa w treści zadania i brakuje separatora miedzy liczbami.
Czy twój algorytm sortowania jest stabilny? Czyli jeśli dane elementy są uznawane za równe, to ich wzajemna kolejność pozostanie bez zmian po posortowaniu?

Uruchomiłeś swój kod z przykładowymi danymi?

Dostałeś gotowca od @kq i masz jeszcze od mnie: https://wandbox.org/permlink/GEGwcUGdlnXBGofL

0

i twój też na spoju jest odrzucany .

A po drugie nie chcę tego pisać na wektorach ale na czymś prostszym do wytłumaczenia . Wolę to napisać nie stosując wektorów i wiedzieć co się w tym kodzie dzieje .

0

Kod @kq nie zawiera tylko kilku instrukcji include.

Natomiast jeśli chesz wiedzieć co jest źle z Twym rozwiązaniem, to przynajmniej popraw wypisywanie wyników, bo w takiej formie nie ma szans na accepta.

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0