fork download
copy 
  1. #include<bits/stdc++.h> // to include all the library functions 
  2. using namespace std; // to avoid writing the std:: repeatadly 
  3.  
  4. struct card // using structure so that we can take the int and char at the same time
  5. {
  6.     char suit; // for the character input
  7.     int num; // for the number inpput
  8.     int id; // to store original position for stability checking
  9. };
  10.  
  11. int Partition(card A[],int p, int r) //  partition function will be returning the required index to break the arrays into two parts
  12. {
  13.     int x = A[r].num; // taking x as the pivot= last element of the array
  14.     int i = p-1; // following the given pseudocode
  15.  
  16.  
  17.     for(int j = p; j<=r-1;j++) // running the loop according to the pseudocode
  18.     {
  19.         if(A[j].num<= x) // comparing the integer values
  20.         {
  21.             i++; // increment
  22.             swap(A[i],A[j]); // exchanging the values of the array
  23.  
  24.         }
  25.     }
  26.     swap(A[i+1],A[r]); // exchange the values , this will take the (x) to its required position 
  27.     return i+1; // returning the value so that based on that we can do partition 
  28. }
  29.  
  30. /*Quicksort(A, p, r) --> copied it from the question so that i can stay at codeblocks and focus on writing the code
  31. 1 if p < r
  32. 2    then q = Partition(A, p, r)
  33. 3        run Quicksort(A, p, q-1)
  34. 4        run Quicksort(A, q+1, r) */
  35.  
  36. void Quicksort(card A[],int p, int r) // here is the main function that will do all the recursive stuffs
  37. {
  38.     if(p<r) // initial condition to perform [similar to ( left<right) ]
  39.     {
  40.         int q = Partition(A,p,r); // collecting the index so that we can perform Quicksort on the two arrays
  41.  
  42.         Quicksort(A,p,q-1); // recursive calling for  the left sub-array
  43.         Quicksort(A,q+1,r); // recursive call for the right sub-array 
  44.     }
  45. }
  46.  
  47. int main() // main function -- > the code starts from here
  48. {
  49.     int n; // declaring n as the size
  50.      cin >> n; // taking n from the user
  51.  
  52.     card A[100005]; // main array (safe size for VJudge)
  53.  
  54.     for(int i= 0; i<n;i++) // traversing the array using for loop
  55.     {
  56.         cin >> A[i].suit; // taking the character part input
  57.         cin >> A[i].num; // input the number part
  58.         A[i].id = i; // storing original position
  59.     }
  60.  
  61.     Quicksort(A,0,n-1); // calling the function to do the operation [ here p = 0 & r = n-1 --> according to the question ]
  62.  
  63.     bool stable = true; // to check the stability 
  64.  
  65.     for(int i = 1; i < n; i++) // checking stability properly
  66.     {
  67.         if(A[i].num == A[i-1].num) // only compare equal numbers
  68.         {
  69.             if(A[i].id < A[i-1].id) // order changed
  70.             {
  71.                 stable = false; // if the condition is true then stable == false
  72.                 break; // no need to check further if it is already false
  73.             }
  74.         }
  75.     }
  76.  
  77.     if(stable) // just checking the conditions 
  78.         cout << "Stable" << endl; // printing the ans
  79.     else // if not stable
  80.         cout << "Not stable" << endl; // printing the ans
  81.  
  82.     for(int i = 0;i<n;i++) // loop to show the output 
  83.     {
  84.         cout << A[i].suit << " " << A[i].num << endl; // showing the outputs 
  85.     }
  86.  
  87.     return 0; // end of the code
  88. }
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Stable
https://ideone.com/O5SaF3
language:
C++ (gcc 8.3)
created:
14 hours ago
visibility:
public

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!