fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define MAX 1000
  5.  
  6. void swap(int* a, int* b) {
  7.     int t = *a;
  8.     *a = *b;
  9.     *b = t;
  10. }
  11.  
  12. int partition(int arr[], int low, int high) {
  13.     int pivot = arr[high];
  14.     int i = low;
  15.  
  16.     for (int j = low; j < high; j++) {
  17.         if (arr[j] <= pivot) {
  18.             swap(&arr[i], &arr[j]);
  19.             i++;
  20.         }
  21.     }
  22.     swap(&arr[i], &arr[high]);
  23.     return i;
  24. }
  25.  
  26. int quickSelect(int arr[], int low, int high, int k) {
  27.     if (low <= high) {
  28.         int pi = partition(arr, low, high);
  29.  
  30.         if (pi == k)
  31.             return arr[pi];
  32.         else if (pi > k)
  33.             return quickSelect(arr, low, pi - 1, k);
  34.         else
  35.             return quickSelect(arr, pi + 1, high, k);
  36.     }
  37.     return -1;
  38. }
  39.  
  40. int main() {
  41.     int n, k;
  42.     scanf("%d", &n);
  43.  
  44.     if (n <= 0) return 0;
  45.  
  46.     int arr[MAX];
  47.     for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
  48.  
  49.     scanf("%d", &k);
  50.  
  51.     if (k <= 0 || k > n) {
  52.         printf("Invalid K\n");
  53.         return 0;
  54.     }
  55.  
  56.     printf("%d\n", quickSelect(arr, 0, n - 1, k - 1));
  57.     return 0;
  58. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
6
7 10 4 3 20 15
3
stdout
copy 
7
https://ideone.com/o5Sx6F
language:
C (gcc 8.3)
created:
1 day 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!