Merge sort

Odpowiedz Nowy wątek
2018-12-12 01:21
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
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
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
1

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


#Dżunior React Devloper wanna be#
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
Liczba odpowiedzi na stronę

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