ccmny

merge sort natalii

Jan 3rd, 2012
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.26 KB | None | 0 0
  1. #include <iostream>
  2. #define LEN 10
  3.  
  4. using namespace std;
  5.  
  6. void fill_array(int t[])
  7. {
  8.     srand(time(0));
  9.     for(int i = 0; i < LEN; i++)
  10.         t[i]  =  rand() % 101;
  11. }
  12.  
  13. void print_array(int t[])
  14. {
  15.     for(int i = 0; i < LEN; i++)
  16.         cout << t[i] << " ";
  17.     cout << endl;
  18. }
  19.  
  20. void merge(int array[], int start, int middle, int end)
  21. {
  22.     int* temp = new int[end - start];
  23.     int i = start;
  24.     int j = middle + 1;
  25.     int k = 0;
  26.  
  27.     while ((i <= middle) && (j <= end))
  28.     {
  29.         if(array[j] < array[i])
  30.         {
  31.             temp[k] = array[j];
  32.             j++;
  33.         }
  34.         else
  35.         {
  36.             temp[k] = array[i];
  37.             i++;
  38.         }
  39.         k++;       
  40.     }
  41.  
  42.     if (i <= middle)
  43.     {
  44.         while(i <= middle)
  45.         {
  46.             temp[k] = array[i];
  47.             i++;
  48.             k++;
  49.         }
  50.     }
  51.     else
  52.     {
  53.         while(j <= end)
  54.         {
  55.             temp[k] = array[j];
  56.             j++;
  57.             k++;
  58.         }
  59.     }
  60.     for(i = 0; i <= end - start; i++)
  61.     {
  62.         array[start + i] = temp[i];
  63.     }
  64. }
  65.  
  66. void merge_sort(int array[], int start, int end)
  67. {
  68.     if (start != end)
  69.     {
  70.         int middle = (end + start) / 2;
  71.         merge_sort(array, start, middle);
  72.         merge_sort(array, middle + 1, end);
  73.         merge(array, start, middle, end);
  74.     }
  75. }
  76.  
  77. int main(int argc, char ** argv)
  78. {
  79.     int array[LEN];
  80.     fill_array(array);
  81.     print_array(array);
  82.     merge_sort(array, 0, LEN);
  83.     cout<<endl<<endl;
  84.     print_array(array);
  85.     return 0;
  86. }
Advertisement
Add Comment
Please, Sign In to add comment