Advertisement
desdemona

merge na watkach

Mar 26th, 2013
238
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.30 KB | None | 0 0
  1. #include <Windows.h>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <time.h>
  5. #include <vector>
  6. #include <iostream>
  7.  
  8. using namespace std;
  9. #pragma argsused
  10. struct dane
  11. {
  12.     int index_poczatek;
  13.     int index_koniec;
  14. };
  15.  
  16. DWORD WINAPI merge_sort(void* argumenty);
  17.  
  18. const int MAX = 20;
  19. int tablica[MAX];
  20. DWORD id;
  21. int main(int argc, char **argv)
  22. {
  23.    
  24.     struct dane* bogdan = new dane;
  25.     bogdan->index_koniec = MAX-1;
  26.     bogdan->index_poczatek = 0;
  27.     srand(time(NULL));
  28.     for(int i=0; i<MAX; i++)
  29.         tablica[i]=rand()%1000;
  30.     for(int i=0; i<MAX; i++)
  31.     {
  32.         cout << tablica[i] << " ";
  33.     }
  34.     cout << "\n";
  35.     HANDLE watek;
  36.     watek = CreateThread( NULL, 0, merge_sort, (void*)bogdan, 0, &id);
  37.     WaitForSingleObject(watek,  INFINITE);
  38.     for(int i=0; i<MAX; i++)
  39.     {
  40.         cout << tablica[i] << " ";
  41.     }
  42.     cout << "\n";
  43.     return 0;
  44. }
  45.  
  46. DWORD WINAPI merge_sort(void* argumenty)
  47. {
  48.    
  49.     //struct dane* bogdan = new dane;
  50.     struct dane* bogdan = (struct dane*)argumenty;
  51.     //deklaruj strukta i z nim wywolaj nowy watek, derp
  52.     struct dane* lewy;
  53.     struct dane* prawy;
  54.     int poczatek = bogdan->index_poczatek;
  55.     int koniec= bogdan->index_koniec;
  56.     int n=koniec-poczatek+1;
  57.     int *tab_lewa, *tab_prawa;
  58.     HANDLE lewy_watek, prawy_watek;
  59.     if(poczatek<koniec)
  60.     {
  61.         lewy=new dane;
  62.         prawy = new dane;
  63.         lewy->index_poczatek = poczatek;
  64.         lewy->index_koniec = (poczatek+koniec)/2;
  65.         prawy->index_poczatek = lewy->index_koniec + 1;
  66.         prawy->index_koniec = koniec;
  67.         lewy_watek = CreateThread( NULL, 0, merge_sort, (void*)lewy, 0, &id);
  68.         prawy_watek = CreateThread(NULL,0, merge_sort, (void*)prawy,0, &id);
  69.         WaitForSingleObject(lewy_watek, INFINITE);
  70.         WaitForSingleObject(prawy_watek, INFINITE);
  71.         int n1, n2;
  72.         n1 = (poczatek+koniec)/2 - poczatek + 1;
  73.         n2 = koniec - (poczatek+koniec)/2;
  74.         tab_lewa = new int[n1];
  75.         tab_prawa = new int[n2];
  76.         for(int i=0; i<n1; i++)
  77.             tab_lewa[i] = tablica[poczatek + i];
  78.  
  79.         for(int i=0; i<n2; i++)
  80.             tab_prawa[i]=tablica[(poczatek+koniec)/2 + 1 + i];
  81.  
  82.         //merdżujmey z tablic lewej i prawej do wlasciwej
  83.         int i,k,j;
  84.         for(k=i=j=0; k<n; k++)
  85.         {
  86.             if(i>= n1 || (j <n2 && tab_lewa[i] > tab_prawa[j]))
  87.                 tablica[k+poczatek] = tab_prawa[j++];
  88.             else
  89.                 tablica[k+poczatek] = tab_lewa[i++];
  90.         }
  91.        
  92.         free(tab_lewa);
  93.         free(tab_prawa);
  94.         free(lewy);
  95.         free(prawy);
  96.     }  
  97.     return 0;
  98. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement