fork(8) download 
  1. #include <stdio.h>
  2.  
  3. /*
  4. inputs...
  5. *A: pointer to array
  6. n: size of array
  7. k: the item in question
  8. */
  9. //Swaps
  10. void swap(int *a, int *b){
  11.     int temp = *a;
  12.     *a = *b;
  13.     *b = temp;
  14. }
  15.  
  16.  
  17. int partition(int *A, int left, int right){
  18.  
  19.     int pivot = A[right], i = left, x;
  20.  
  21.     for (x = left; x < right; x++){
  22.         if (A[x] <= pivot){
  23.             swap(&A[i], &A[x]);
  24.             i++;
  25.         }
  26.     }
  27.  
  28.     swap(&A[i], &A[right]);
  29.     return i;
  30. }
  31.  
  32.  
  33. int quickselect(int *A, int left, int right, int k){
  34.  
  35.     //p is position of pivot in the partitioned array
  36.     int p = partition(A, left, right);
  37.  
  38.     //k equals pivot got lucky
  39.     if (p == k-1){
  40.         return A[p];
  41.     }
  42.     //k less than pivot
  43.     else if (k - 1 < p){
  44.         return quickselect(A, left, p - 1, k);
  45.     }
  46.     //k greater than pivot
  47.     else{
  48.         return quickselect(A, p + 1, right, k);
  49.     }
  50. }
  51.  
  52. int ksmallest(int *A, int n, int k){
  53.  
  54.     int left = 0; 
  55.     int right = n - 1; 
  56.  
  57.     return quickselect(A, left, right, k);
  58. }
  59.  
  60. int main()
  61. {
  62. 	int A[7] = {1,3,8,2,4,9,7};
  63. 	int k;
  64. 	scanf("%d", &k);
  65. 	printf("%d\n", ksmallest(A, 7, k));
  66. 	return 0;
  67. }
Success #stdin #stdout 0s 2164KB
comments (?)
stdin 
6
stdout 
8
https://ideone.com/Bkaglb
language:
C (gcc 8.3)
created:
8 years 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!