fork download
copy 
  1. //
  2. //  main.cpp
  3. //  Quicksort and Mergesort
  4. //
  5. //  Created by Himanshu on 29/08/21.
  6. //
  7.  
  8. #include <iostream>
  9. #include <limits.h>
  10. using namespace std;
  11. const int n = 5;
  12.  
  13. void printArray (int arr[]) {
  14.     for (int i=0; i<n; i++) {
  15.         cout<<arr[i]<<" ";
  16.     }
  17.     cout<<endl;
  18. }
  19.  
  20. int partition (int A[], int p, int r) {
  21.     int x = A[r];
  22.     int i = p-1;
  23.     for (int j=p; j<r; j++) {
  24.         if (A[j] <= x) {
  25.             i++;
  26.             swap(A[i], A[j]);
  27.         }
  28.     }
  29.     swap(A[r], A[i+1]);
  30.     return (i+1);
  31. }
  32.  
  33. void quicksort (int A[], int p, int r) {
  34.     if (p < r) {
  35.         int q  = partition(A, p, r);
  36.         cout<<"Pivot: "<<A[q]<<endl;
  37.         cout<<"New array after partition"<<endl;
  38.         printArray(A);
  39.         quicksort(A, p, q-1);
  40.         quicksort(A, q+1, r);
  41.     }
  42. }
  43.  
  44. void merge (int A[], int p, int q, int r) {
  45.     int n1 = q - p + 1;
  46.     int n2 = r - q;
  47.     int L[n1 + 1], R[n2 + 1];
  48.  
  49.     //Adding element from 0 to q, to L array
  50.     for (int i=0; i<n1; i++) {
  51.         L[i] = A[p+i];
  52.     }
  53.  
  54.     //Adding element from q+1 to r, to R array
  55.     for (int j=0; j<n2; j++) {
  56.         R[j] = A[q+j+1];
  57.     }
  58.  
  59.     L[n1] = INT_MAX;
  60.     R[n2] = INT_MAX;
  61.  
  62.     int i=0, j=0;
  63.  
  64.     for (int k=p; k<=r; k++) {
  65.         if (L[i] <= R[j]) {
  66.             A[k] = L[i];
  67.             i = i+1;
  68.         } else {
  69.             A[k] = R[j];
  70.             j = j+1;
  71.         }
  72.     }
  73. }
  74.  
  75. void mergesort (int A[], int p, int r) {
  76.     if (p < r) {
  77.         int q  = (p+r)/2;
  78.         mergesort(A, p, q);
  79.         mergesort(A, q+1, r);
  80.         merge(A, p, q, r);
  81.         cout<<"New array after merge"<<endl;
  82.         printArray(A);
  83.     }
  84. }
  85.  
  86. int main() {
  87.     int A[n] = {11, 2, 90, 57, 13};
  88.     int B[n] = {11, 2, 90, 57, 13};
  89.  
  90.     cout<<"Initial Array:"<<endl<<endl;
  91.     printArray(A);
  92.     cout<<endl;
  93.     cout<<"-------Quicksort-------"<<endl<<endl;
  94.     quicksort(A, 0, n-1);
  95.     cout<<"-----------------------"<<endl;
  96.     cout<<"Initial Array:"<<endl<<endl;
  97.     printArray(B);
  98.     cout<<endl;
  99.     cout<<"-------Mergesort-------"<<endl<<endl;
  100.     mergesort(B, 0, n-1);
  101.     return 0;
  102. }
  103.  
  104.  
Success #stdin #stdout 0s 5392KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Initial Array:

11 2 90 57 13 

-------Quicksort-------

Pivot: 13
New array after partition
11 2 13 57 90 
Pivot: 2
New array after partition
2 11 13 57 90 
Pivot: 90
New array after partition
2 11 13 57 90 
-----------------------
Initial Array:

11 2 90 57 13 

-------Mergesort-------

New array after merge
2 11 90 57 13 
New array after merge
2 11 90 57 13 
New array after merge
2 11 90 13 57 
New array after merge
2 11 13 57 90
https://ideone.com/E4X7Qi
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!