Facebook
From Anikkkk, 7 Months ago, written in Plain Text.
Embed
Download Paste or View Raw
Hits: 401
  1. #include<iostream>
  2. using namespace std;
  3.  
  4. void insertion(int a[], int n)
  5. {
  6.     for(int i=1; i<n; i++)
  7.     {
  8.         int ele= a[i];
  9.         int j=i-1;
  10.         while(a[j]>ele && j>=0)
  11.         {
  12.             a[j+1]=a[j];
  13.             --j;
  14.         }
  15.         a[j+1]= ele;
  16.     }
  17. }
  18.  
  19. void selection(int a[], int n)
  20. {
  21.     for(int i=0; i<n-1; i++)
  22.     {
  23.         int min= i;
  24.         for(int j=i+1; j<n; j++)
  25.         {
  26.             if(a[j]<a[min])
  27.             {
  28.                 min=j;
  29.             }
  30.         }
  31.         swap(a[min], a[i]);
  32.     }
  33. }
  34.  
  35.  
  36. void merge(int a[], int left, int mid, int right)
  37. {
  38.     int a1= mid-left+1, a2= right-mid;
  39.  
  40.     int templeft[a1], tempright[a2];
  41.  
  42.     for(int i=0; i<a1; i++)
  43.     {
  44.         templeft[i]= a[i+left];
  45.     }
  46.  
  47.     for(int i=0; i<a2; i++)
  48.     {
  49.         tempright[i]= a[mid+1+i];
  50.     }
  51.  
  52.     int idxleft=0, idxright=0, idxarr= left;
  53.  
  54.     while(idxleft<a2)
  55.     {
  56.         if(templeft[idxleft]<tempright[idxright])
  57.         {
  58.             a[idxarr]= templeft[idxleft];
  59.             idxleft++;
  60.         }
  61.         else
  62.         {
  63.             a[idxarr]= tempright[idxright];
  64.             idxright++;
  65.         }
  66.         idxarr++;
  67.     }
  68.  
  69.     while(idxleft<a1)
  70.     {
  71.         a[idxarr]= templeft[idxleft];
  72.         idxleft++, idxarr++;
  73.     }
  74.  
  75.     while(idxright<a2)
  76.     {
  77.         a[idxarr]= tempright[idxright];
  78.         idxright++, idxarr++;
  79.     }
  80. }
  81.  
  82.  
  83. void mergesort(int a[], int left, int right)
  84. {
  85.     if(left>=right)
  86.     {
  87.         return;
  88.     }
  89.     int mid= (left+right)/2;
  90.     mergesort(a, left, mid);
  91.     mergesort(a, mid+1, right);
  92.     merge(a, left, mid, right);
  93. }
  94.  
  95.  
  96. int partition(int a[], int low, int high)
  97. {
  98.     int pivot= a[high];
  99.     int i= low-1;
  100.     for(int x= low; x<high; x++)
  101.     {
  102.         if(a[x]<pivot)
  103.         {
  104.             i++;
  105.             swap(a[i], a[x]);
  106.         }
  107.     }
  108.     swap(a[i+1], a[high]);
  109.     return i+1;
  110. }
  111.  
  112.  
  113. void quicksort(int a[], int low, int high)
  114. {
  115.     if(low>=high)
  116.     return;
  117.  
  118.     int pi= partition(a, low, high);
  119.     quicksort(a, low, pi-1);
  120.     quicksort(a, pi+1, high);
  121.  
  122. }
  123.  
  124.  
  125. void heapify(int a[], int n, int i)
  126. {
  127.     int largest=i;
  128.     int l= 2*i+1;
  129.     int r= 2*i+2;
  130.     if(l>a[largest])
  131.     {
  132.         largest=l;
  133.     }
  134.     if(r>a[largest])
  135.     {
  136.         largest=r;
  137.     }
  138.     if(largest != i)
  139.     {
  140.         swap(a[largest], a[i]);
  141.         heapify(a, n, largest);
  142.     }
  143.    
  144. }
  145.  
  146.  
  147. void heapsort(int a[], int n)
  148. {
  149.     for(int i=n/2-1; i>=0; i--)
  150.     {
  151.         heapify(a, n, i);
  152.     }
  153.  
  154.     for(int i= n-1; i>0; i--)
  155.     {
  156.         swap(a[0], a[i]);
  157.         heapify(a, i, 0);
  158.     }
  159. }
  160.  
  161.  
  162. int main()
  163. {
  164.     int n;
  165.     cin>>n;
  166.     int a[n];
  167.     for(int i=0; i<n; i++)
  168.     {
  169.         cin>>a[i];
  170.     }
  171.     heapsort(a, n);
  172.     for(int x=0; x<n; x++)
  173.     {
  174.         cout<<a[x]<<" ";
  175.     }
  176. }