Niloy007

Kth Largest element (Using QuickSort)

Apr 14th, 2021
430
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int partition(int A[], int low, int high) {
  5.     int i = low + 1;
  6.     int j = high;
  7.     int temp;
  8.  
  9.     while(1) {
  10.         while((i <= high) && (A[i] < A[low])) {
  11.             i++;
  12.         }
  13.         while((j >= (low + 1)) && (A[j] >= A[low])) {
  14.             j--;
  15.         }
  16.         if(i < j)
  17.             swap(A[i], A[j]);
  18.         else
  19.             break;
  20.     }
  21.  
  22.     swap(A[low], A[j]);
  23.     return j;
  24. }
  25.  
  26. // void quickSort(int A[], int low, int high) {
  27. //     if(low < high) {
  28. //         int p = partition(A, low, high);
  29. //         quickSort(A, low, p - 1);
  30. //         quickSort(A, p + 1, high);
  31. //     }
  32. // }
  33.  
  34. int kth_largest(int K[], int low, int high, int k) {
  35.     int q = partition(K, low, high);
  36.  
  37.     if (q == k) {
  38.         return K[k];
  39.     } else if (q > k) {
  40.         return kth_largest(K, low, q - 1, k);
  41.     }
  42.     else {
  43.         return kth_largest(K, q + 1, high, k);
  44.     }
  45.     return -1;
  46. }
  47.  
  48. int main() {
  49.     int i, n;
  50.     printf("\n Input the size");
  51.     scanf("%d", &n);
  52.     int A[n];
  53.     printf("\n Input the elements");
  54.     for (i = 0; i < n; i++) {
  55.         scanf("%d", &A[i]);
  56.     }
  57.  
  58.     // quickSort(A, 0, n);
  59.     printf("\n after sorting the element is:\n");
  60.     for (i = 0; i < n; i++) {
  61.         printf("%d ", A[i]);
  62.     }
  63.     printf("\n");
  64.  
  65.     int pos = 3;
  66.     int y = kth_largest(A, 0, n, pos);
  67.     printf("The largest element is %d.\n", y);
  68.  
  69.     return 0;
  70. }
  71.  
  72. /*
  73.     Input: 1 4 6 7 10 19 22 23 30 35 39 46 49 50 52 55 61 67 70 71
  74. */
  75.  
RAW Paste Data