Merge sort

Odpowiedz Nowy wątek
2018-12-12 01:21

Rejestracja: 2 lata temu

Ostatnio: 2 miesiące temu

0

void scal(int tab[], int lewy, int srodek, int prawy) 
{
    int i = lewy, j = srodek + 1;

  //kopiujemy lewą i prawą część tablicy do tablicy pomocniczej
  for(int i = lewy;i<=prawy; i++) 
    pom[i] = tab[i];  

  //scalenie dwóch podtablic pomocniczych i zapisanie ich 
  //we własciwej tablicy
  for(int k=lewy;k<=prawy;k++) 
  if(i<=srodek)
    if(j <= prawy)
         if(pom[j]<pom[i])
             tab[k] = pom[j++];
         else
             tab[k] = pom[i++];
    else
        tab[k] = pom[i++];
  else
      tab[k] = pom[j++];
}

void sortowanie_przez_scalanie(int tab[],int lewy, int prawy)
{
    //gdy mamy jeden element, to jest on już posortowany
    if(prawy<=lewy) return; 

    //znajdujemy srodek podtablicy
    int srodek = (prawy+lewy)/2;

    //dzielimy tablice na częsć lewą i prawa
    sortowanie_przez_scalanie(tab, lewy, srodek); 
    sortowanie_przez_scalanie(tab, srodek+1, prawy);

    //scalamy dwie już posortowane tablice
    scal(tab, lewy, srodek, prawy);
}

int main()
{
    int *tab,
    n; //liczba elementów tablicy

    cin>>n;
    tab = new int[n]; //przydzielenie pamięci na tablicę liczb
    pom = new int[n]; //przydzielenie pamięci na tablicę pomocniczą

    //wczytanie elementów tablicy
    for(int i=0;i<n;i++)
        cin>>tab[i];

    //sortowanie wczytanej tablicy
    sortowanie_przez_scalanie(tab,0,n-1);

    //wypisanie wyników
    for(int i=0;i<n;i++)
        cout<<tab[i]<<" ";

    system("pause");
    return 0;
}

To cały algorytm sortujący przez scalanie , mam pytanie do tej części

 for(int k=lewy;k<=prawy;k++) 
  if(i<=srodek)
    if(j <= prawy)
         if(pom[j]<pom[i])
             tab[k] = pom[j++];
         else
             tab[k] = pom[i++];
    else
        tab[k] = pom[i++];
  else
      tab[k] = pom[j++];

Ta część jest odpowiedzialna za właśnie sortowanie ?

Pozostało 580 znaków

2018-12-12 01:39

Rejestracja: 3 lata temu

Ostatnio: 3 godziny temu

1

Masz na półce CLRS, "Algorithms in Java" - Sedgewick, Wayne, albo internet i youtube ? Odsyłam tam.


edytowany 1x, ostatnio: lion137, 2018-12-12 01:39

Pozostało 580 znaków

2018-12-12 09:45
Moderator

Rejestracja: 16 lat temu

Ostatnio: 53 minuty temu

1

Odpowiedź brzmi: nie. Jest odpowiedzialna za to co w komentarzu, czyli za scalenie 2 posortowanych podtablic.


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...

Pozostało 580 znaków

2018-12-12 10:03

Rejestracja: 17 lat temu

Ostatnio: 2 godziny temu

Lokalizacja: Kraków

1

No ja bym właśnie powiedział że "tak", bo w trakcie tego scalania tak naprawdę sortujemy ;)


It's easy to hate code you didn't write, without an understanding of the context in which it was written.
To odpal samo scalanie i sprawdź czy ci coś posortowało... - Shalom 2018-12-12 10:29
przy zachowaniu odpowiednich niezmienników danych wejściowych oczywiście że posortowało :D, to raczej jest problem filozoficzny, co uznajemy za sortowanie a co nie :D - neves 2018-12-12 11:09

Pozostało 580 znaków

Odpowiedz

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