Facebook
From Ja L O L, 1 Year ago, written in C++.
Embed
Download Paste or View Raw
Hits: 116
  1. // Sortowanie przez scalanie (mergesort)
  2. // Koszt algorytmu w kaツソdym przypadku:
  3. // T(n)=n log n
  4. // Marcin Krajewski
  5. // www.algorytm.org
  6.  
  7. #include <iostream>
  8. #define N 10
  9.  
  10. using namespace std;
  11.  
  12. int tab[N] ;
  13. int t[N];  // Tablica pomocnicza
  14.  
  15. /* Scalanie dwoch posortowanych ciagow
  16. tab[pocz...sr] i tab[sr+1...kon] i
  17. wynik zapisuje w tab[pocz...kon] */
  18. void merge(int pocz, int sr, int kon)
  19. {
  20. int i,j,q;
  21. for (i=pocz; i<=kon; i++) t[i]=tab[i];  // Skopiowanie danych do tablicy pomocniczej
  22. i=pocz; j=sr+1; q=pocz;                 // Ustawienie wskaナクnikテウw tablic
  23. while (i<=sr && j<=kon) {         // Przenoszenie danych z sortowaniem ze zbiorテウw pomocniczych do tablicy gツウテウwnej
  24. if (t[i]<t[j])
  25. tab[q++]=t[i++];
  26. else
  27. tab[q++]=t[j++];
  28. }
  29. while (i<=sr) tab[q++]=t[i++]; // Przeniesienie nie skopiowanych danych ze zbioru pierwszego w przypadku, gdy drugi zbiテウr siテェ skoテアczyツウ
  30. }
  31.  
  32. /* Procedura sortowania tab[pocz...kon] */
  33. void mergesort(int pocz, int kon)
  34. {
  35. int sr;
  36. if (pocz<kon) {
  37. sr=(pocz+kon)/2;
  38. mergesort(pocz, sr);    // Dzielenie lewej czテェナ田i
  39. mergesort(sr+1, kon);   // Dzielenie prawej czテェナ田i
  40. merge(pocz, sr, kon);   // ツ」ツケczenie czテェナ田i lewej i prawej
  41. }
  42. }
  43.  
  44. int main() {
  45. int i;
  46.  
  47. cout<<"Wpisz liczby"<<endl;
  48. for (i=0; i<N; i++)
  49.     cin>>tab[i];
  50.  
  51.  
  52. mergesort(0,N-1);
  53.  
  54. cout<<"Zbior po sortowaniu: "<<endl;
  55. for (i=0; i<N; i++)
  56. cout<<tab[i]<<endl;
  57. }
  58.