rootuss

sortowanie scalanie

Feb 17th, 2017
201
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. #include<iostream>
  3. #include<cstdlib>
  4. using namespace std;
  5.  
  6. int *pom; //tablica pomocnicza, potrzebna przy scalaniu
  7.  
  8. //scalenie posortowanych podtablic
  9. void scal(int tab[], int lewy, int srodek, int prawy)
  10. {
  11.   int i = lewy, j = srodek + 1;
  12.  
  13.   //kopiujemy lew¹ i praw¹ czêœæ tablicy do tablicy pomocniczej
  14.   for(int i = lewy;i<=prawy; i++)
  15.     pom[i] = tab[i];
  16.  
  17.   //scalenie dwóch podtablic pomocniczych i zapisanie ich
  18.   //we w³asciwej tablicy
  19.   for(int k=lewy;k<=prawy;k++)
  20.   if(i<=srodek)
  21.     if(j <= prawy)
  22.          if(pom[j]<pom[i])
  23.              tab[k] = pom[j++];
  24.          else
  25.              tab[k] = pom[i++];
  26.     else
  27.         tab[k] = pom[i++];
  28.   else
  29.       tab[k] = pom[j++];
  30. }
  31.  
  32. void sortowanie_przez_scalanie(int tab[],int lewy, int prawy)
  33. {
  34.   //gdy mamy jeden element, to jest on ju¿ posortowany
  35.   if(prawy<=lewy) return;
  36.  
  37.   //znajdujemy srodek podtablicy
  38.   int srodek = (prawy+lewy)/2;
  39.  
  40.   //dzielimy tablice na czêsæ lew¹ i prawa
  41.   sortowanie_przez_scalanie(tab, lewy, srodek);
  42.   sortowanie_przez_scalanie(tab, srodek+1, prawy);
  43.  
  44.   //scalamy dwie ju¿ posortowane tablice
  45.   scal(tab, lewy, srodek, prawy);
  46. }
  47.  
  48. int main()
  49. {
  50.   int *tab,
  51.   n; //liczba elementów tablicy
  52.  
  53.   cin>>n;
  54.   tab = new int[n]; //przydzielenie pamiêci na tablicê liczb
  55.   pom = new int[n]; //przydzielenie pamiêci na tablicê pomocnicz¹
  56.  
  57.   //wczytanie elementów tablicy
  58.   for(int i=0;i<n;i++)
  59.     cin>>tab[i];
  60.  
  61.   //sortowanie wczytanej tablicy
  62.   sortowanie_przez_scalanie(tab,0,n-1);
  63.  
  64.   //wypisanie wyników
  65.   for(int i=0;i<n;i++)
  66.     cout<<tab[i]<<" ";
  67.  
  68.   system("pause");
  69.   return 0;
  70. }
RAW Paste Data