fork download 
  1. //
  2. //  main.cpp
  3. //  Order Statistics & Min Heap Comparison
  4. //
  5. //  Created by Himanshu on 21/11/23.
  6. //
  7.  
  8. #include <iostream>
  9. #include <algorithm>
  10. #include <ctime>
  11. #include <random>
  12. #include <vector>
  13. #include <chrono>
  14. #include <queue>
  15. #include <unordered_set>
  16. using namespace std;
  17.  
  18. random_device rd;  // Obtain a random seed from the hardware
  19. mt19937 gen(rd()); // Standard mersenne_twister_engine seeded with rd()
  20.  
  21. // Random number generator
  22. int choosePivot(int low, int high) {
  23.     uniform_int_distribution<int> distrib(low, high); // Define the range
  24.     return distrib(gen); // Generate a random number
  25. }
  26.  
  27. // Order Statistic Algorithm
  28. int partition(int arr[], int low, int high) {
  29.     int pivotIndex = choosePivot(low, high);
  30.     int pivot = arr[pivotIndex];
  31.  
  32.     swap(arr[pivotIndex], arr[high]);
  33.  
  34.     int i = low - 1;
  35.  
  36.     for (int j = low; j < high; j++) {
  37.         if (arr[j] <= pivot) {
  38.             i++;
  39.             swap(arr[i], arr[j]);
  40.         }
  41.     }
  42.  
  43.     swap(arr[i + 1], arr[high]);
  44.     return i + 1;
  45. }
  46.  
  47. int kthSmallest(int arr[], int low, int high, int k) {
  48.  
  49.     if (k > 0 && k <= high - low + 1) {
  50.         int pivot = partition(arr, low, high);
  51.  
  52.         if (pivot - low == k - 1) {
  53.             return arr[pivot];
  54.         } else if (pivot - low > k - 1) {
  55.             return kthSmallest(arr, low, pivot - 1, k);
  56.         } else {
  57.             return kthSmallest(arr, pivot + 1, high, k - pivot + low - 1);
  58.         }
  59.     }
  60.  
  61.     return -1; // Return -1 for invalid input
  62. }
  63.  
  64. // Min Heap Approach
  65. int kthSmallestUsingHeap(int arr[], int n, int k) {
  66.     priority_queue<int, vector<int>, greater<int>> minHeap(arr, arr + n);
  67.  
  68.     for (int i = 0; i < k - 1; i++) {
  69.         minHeap.pop();
  70.     }
  71.  
  72.     return minHeap.top();
  73. }
  74.  
  75.  
  76. int main() {
  77.     const int listSize = 100000; // Adjust the list size as needed
  78.     int arr[listSize];
  79.  
  80.     unordered_set<int> uniqueNumbers;
  81.  
  82.     // Generate a random list of sequential numbers
  83.     srand((unsigned int) time(NULL));
  84.     for (int i = 0; i < listSize; i++) {
  85.         int randomNumber;
  86.         do {
  87.             randomNumber = rand() % 100000; // Generate a random number between 0 and 99999
  88.         } while (!uniqueNumbers.insert(randomNumber).second); // Insert and check uniqueness
  89.  
  90.         arr[i] = randomNumber;
  91.     }
  92.  
  93.     int kValues[] = {100, 500, 1000, 5000, 10000, 50000}; // Different values of k to test
  94.  
  95.     for (int k : kValues) {
  96.  
  97.         // Measure execution time for Order Statistic algorithm
  98.         auto start = chrono::high_resolution_clock::now();
  99.         int result1 = kthSmallest(arr, 0, listSize - 1, k);
  100.         auto end = chrono::high_resolution_clock::now();
  101.         chrono::duration<double> duration1 = end - start;
  102.  
  103.         // Measure execution time for Min Heap approach
  104.         start = chrono::high_resolution_clock::now();
  105.         int result2 = kthSmallestUsingHeap(arr, listSize, k);
  106.         end = chrono::high_resolution_clock::now();
  107.         chrono::duration<double> duration2 = end - start;
  108.  
  109.         // Output result
  110.         cout<< k <<"th smallest " << "using Order Statistic algorithm: "<<result1 << endl;
  111.         cout<< k <<"th smallest " << "using Min Heap approach: "<<result2 << endl;
  112.  
  113.         // Output execution times
  114.         cout << "Time taken for k = " << k << " using Order Statistic algorithm: " << duration1.count() << " seconds\n";
  115.         cout << "Time taken for k = " << k << " using Min Heap approach: " << duration2.count() << " seconds\n\n";
  116.     }
  117.  
  118.     return 0;
  119. }
Success #stdin #stdout 0.08s 7904KB
comments (?)
stdin 
Standard input is empty
stdout 
100th smallest using Order Statistic algorithm: 99
100th smallest using Min Heap approach: 99
Time taken for k = 100 using Order Statistic algorithm: 0.000244519 seconds
Time taken for k = 100 using Min Heap approach: 0.0010945 seconds

500th smallest using Order Statistic algorithm: 499
500th smallest using Min Heap approach: 499
Time taken for k = 500 using Order Statistic algorithm: 9.0636e-05 seconds
Time taken for k = 500 using Min Heap approach: 0.00109331 seconds

1000th smallest using Order Statistic algorithm: 999
1000th smallest using Min Heap approach: 999
Time taken for k = 1000 using Order Statistic algorithm: 0.000120848 seconds
Time taken for k = 1000 using Min Heap approach: 0.00110461 seconds

5000th smallest using Order Statistic algorithm: 4999
5000th smallest using Min Heap approach: 4999
Time taken for k = 5000 using Order Statistic algorithm: 0.000496643 seconds
Time taken for k = 5000 using Min Heap approach: 0.00143438 seconds

10000th smallest using Order Statistic algorithm: 9999
10000th smallest using Min Heap approach: 9999
Time taken for k = 10000 using Order Statistic algorithm: 0.000290027 seconds
Time taken for k = 10000 using Min Heap approach: 0.00191804 seconds

50000th smallest using Order Statistic algorithm: 49999
50000th smallest using Min Heap approach: 49999
Time taken for k = 50000 using Order Statistic algorithm: 0.000480221 seconds
Time taken for k = 50000 using Min Heap approach: 0.00532426 seconds
https://ideone.com/ba5aps
language:
C++ 4.3.2 (gcc-4.3.2)
created:
1 year 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!