The text below is selected, press Ctrl+C to copy to your clipboard. (⌘+C on Mac) No line numbers will be copied.
Guest
Merge sort
By Guest on 18th January 2023 08:54:19 AM | Syntax: TEXT | Views: 13


New paste | Download | Show/Hide line no. | Copy text to clipboard
  1. #include<iostream>
  2. #include <math.h>
  3. #include <stdlib.h>
  4. #include <ctime>
  5. using namespace std;
  6. class sorta
  7. {
  8.     int *arr;
  9.     int n,low,mid ,count;
  10.     public:
  11.     void input();
  12.     void mergeSort(int arr[],int low,int high);
  13.     void merge(int arr[],int low,int high,int mid);
  14.     void display();
  15. };
  16. void sort::input()
  17. {
  18.         cout<<"ENTER NUMBER OF ELEMENTS YOU WANT IN YOUR ARRAY: ";
  19.         cin>>n;
  20.         arr=new int[n];
  21.     // srand(time(NULL));
  22.         cout<<"ENTER ELEMENTS"<<endl;
  23.         for(int i=0;i<n;i++)
  24.         {
  25.                 cin>>arr[i];
  26.         /*
  27.          int value = rand() % 100;
  28.         arr[i]=value;
  29.         */
  30.         }
  31.     count=0;
  32.     mergeSort(arr,0,n-1);
  33. }
  34. void sort::mergeSort(int arr[],int low,int high)
  35. {
  36.    int mid;
  37.    if(low<high)
  38.    {
  39.      mid=(low+high)/2;
  40.      mergeSort(arr,low,mid);
  41.      mergeSort(arr,mid+1,high);
  42.      merge(arr,low,high,mid);  
  43.    }
  44. }
  45. void sort::merge(int arr[],int low,int high,int mid)
  46. {
  47.     int i,j,k,c[n];
  48.     i=low;
  49.     k=low;
  50.     j=mid+1;
  51.     while(i<=mid && j<=high)
  52.     {
  53.         count++;
  54.         if(arr[i]<arr[j])
  55.         {
  56.             c[k]=arr[i];
  57.             i++;
  58.             k++;
  59.         }
  60.         else
  61.         {
  62.             c[k]=arr[j];
  63.             k++;
  64.             j++;
  65.         }
  66.     }
  67.     while(i<=mid)
  68.     {
  69.         c[k]=arr[i];
  70.         i++;
  71.         k++;
  72.     }
  73.     while(j<=high)
  74.     {
  75.         c[k]=arr[j];
  76.         k++;
  77.         j++;
  78.     }
  79.     for(i=low;i<k;i++)
  80.     {
  81.         arr[i]=c[i];
  82.     }
  83. }
  84. void sort::display()
  85. {
  86.     cout<<endl;
  87.     cout<<"Sorted Array"<<endl;
  88.     for(int i=0;i<n;i++)
  89.     {
  90.         cout<<arr[i]<<"\t";
  91.  
  92.     }
  93.     cout<<endl<<"No. of comparisons: "<<count<<endl;
  94. }
  95. int main()
  96. {
  97.     sort obj;
  98.     obj.input();
  99.    obj.display();
  100.    return 0;
  101. }



  • Recent Pastes
  • Questions
    14 hours 43 mins 41 secs ago
  • Adrs
    14 hours 48 mins 51 secs ago
  • Docs
    14 hours 49 mins 35 secs ago
  • Servs
    14 hours 50 mins 18 secs ago
  • Srvs
    14 hours 55 mins 7 secs ago