spider68

all sorting implementation

Jul 24th, 2021
855
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<iostream>
  2. using namespace std;
  3. void heapify(int arr[],int i,int n){
  4.     int largest=i;
  5.     if((2*i+1)<n && arr[2*i+1]>arr[largest]){
  6.         largest=2*i+1;
  7.     }
  8.     if((2*i+2)<n && arr[2*i+2]>arr[largest]){
  9.         largest=2*i+2;
  10.     }
  11.     if(largest!=i){
  12.         swap(arr[largest],arr[i]);
  13.         heapify(arr,largest,n);
  14.     }
  15. }
  16. void heapsort(int arr[],int n){
  17.     for(int i=n/2;i>=0;i--){
  18.         heapify(arr,i,n);
  19.     }
  20.     for(int i=n-1;i>=0;i--){
  21.         swap(arr[0],arr[i]);
  22.         heapify(arr,0,i);
  23.     }
  24. }
  25.  
  26. int pivot(int arr[],int lo,int hi){
  27.     int pivot=lo;
  28.     lo++;
  29.     while(lo<=hi){
  30.         while(lo<=hi && arr[lo]<=arr[pivot])lo++;
  31.         while(hi>=lo && arr[hi]>arr[pivot])hi--;
  32.         if(lo<=hi)swap(arr[lo],arr[hi]);
  33.     }
  34.     swap(arr[pivot],arr[hi]);
  35.     return hi;
  36. }
  37.  
  38. void quicksort(int arr[],int lo,int hi){
  39.     if(lo<hi){
  40.         int idx=pivot(arr,lo,hi);
  41.         quicksort(arr,lo,idx-1);
  42.         quicksort(arr,idx+1,hi);
  43.     }
  44. }
  45.  
  46. void merge(int arr[],int lo,int mid,int hi){
  47.     int sortarray[hi-lo+1];
  48.     int i=lo,j=mid+1,k=0;
  49.     while(i<=mid && j<=hi){
  50.         if(arr[i]<=arr[j])sortarray[k++]=arr[i++];
  51.         else sortarray[k++]=arr[j++];
  52.     }
  53.     while(i<=mid)sortarray[k++]=arr[i++];
  54.     while(j<=hi)sortarray[k++]=arr[j++];
  55.  
  56.     for(i=0;i<k;i++){
  57.         arr[lo+i]=sortarray[i];
  58.     }
  59. }
  60.  
  61. void mergesort(int arr[],int lo,int hi){
  62.     if(lo<hi){
  63.         int mid=(lo+hi)/2;
  64.         mergesort(arr,lo,mid);
  65.         mergesort(arr,mid+1,hi);
  66.         merge(arr,lo,mid,hi);
  67.     }
  68. }
  69.  
  70. void bubblesort(int arr[],int n){
  71.     for(int i=0;i<n-1;i++){
  72.         for(int j=1;j<n;j++){
  73.             if(arr[j]<arr[j-1])swap(arr[j-1],arr[j]);
  74.         }
  75.     }
  76. }
  77.  
  78. void selectionsort(int arr[],int n){
  79.     for(int i=0;i<n-1;i++){
  80.         int minval=i;
  81.         for(int j=i+1;j<n;j++){
  82.             if(arr[j]<arr[minval])minval=j;
  83.         }
  84.         swap(arr[minval],arr[i]);
  85.     }
  86. }
  87. void insertionsort(int arr[],int n){
  88.     for(int i=1;i<n;i++){
  89.         int val=arr[i],j=i-1;
  90.         while(j>=0 && arr[j]>val){
  91.             arr[j+1]=arr[j];
  92.             j--;
  93.         }
  94.         arr[j+1]=val;
  95.     }
  96. }
  97. int main(){
  98.     int n;
  99.     cin>>n;
  100.     int arr[n];
  101.     for(int i=0;i<n;i++)cin>>arr[i];
  102.     heapsort(arr,n);
  103.     quicksort(arr,0,n-1);
  104.     mergesort(arr,0,n-1);
  105.     bubblesort(arr,n);
  106.     selectionsort(arr,n);
  107.     insertionsort(arr,n);
  108.     for(int i=0;i<n;i++)cout<<arr[i]<<" ";
  109. }
  110.  
RAW Paste Data