fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4.  
  5. void quick(int *, int, int);
  6.  
  7. #define N 10
  8.  
  9.  
  10. int  main(void){
  11. 	int a[N] = {0};
  12. 	int k = 0;
  13.  
  14. 	for (k = 0; k < N ; k++) {
  15. 		printf("Input a number: ");
  16. 		scanf("%d", &a[k]);
  17. 	}
  18.  
  19. 	printf("before: ");
  20. 	for (k = 0; k < N; k++) {
  21. 		printf("%4d", a[k]);
  22. 	}
  23. 	printf("\n");
  24.  
  25. 	quick(a, 0, N - 1);
  26.  
  27. 	printf("after:  ");
  28. 	for (k = 0; k < N; k++) {
  29. 		printf("%4d", a[k]);
  30. 	}
  31. 	printf("\n");
  32. }
  33.  
  34. void check(int a[], int left, int right, int p, int center) {
  35. 	int i = 0;
  36. 	printf("(%d, %d) pivot: %d, center: %d\n", left, right, p, center);
  37. 	for (i = 0; i < N; i++) {
  38. 		printf("%4d", a[i]);
  39. 	}
  40. 	printf("\n");
  41. }
  42.  
  43. int pivot(int a[], int left, int right) {
  44. 	return left;
  45. }
  46.  
  47. int swap(int *x, int *y) {
  48. 	int t = *x;
  49. 	*x = *y;
  50. 	*y = t;
  51. }
  52.  
  53. int partition(int a[], int left, int right, int p) {
  54.  
  55. int i=left,j=right; 
  56.  
  57.     while(i<=j){
  58.       while(i<=right && a[i]<p)  i++;
  59.  
  60.       while(j>=left && a[j]>p) j--;
  61.  
  62.       if(i<=j){
  63.       swap(&a[i],&a[j]);
  64.       	i++;
  65.       	j--;
  66.     }
  67.   }
  68.  
  69. return i;
  70. }
  71.  
  72.  
  73.  
  74.  
  75. void quick(int a[], int left, int right) {
  76.  
  77. if(left>=right) return;
  78.  
  79. int p = pivot(a, left, right);
  80.  
  81.  
  82. int center = partition(a, left, right, a[p]);
  83. 	check(a, left, right, p, center);
  84. 	quick(a, left, center-1);
  85. 	quick(a, center, right);
  86.  
  87. }
  88.  
  89.  
Runtime error #stdin #stdout 0.01s 1724KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Input a number: Input a number: Input a number: Input a number: Input a number: Input a number: Input a number: Input a number: Input a number: Input a number: before:    0   0   0   0   0   0   0   0   0   0
(0, 9) pivot: 0, center: 5
   0   0   0   0   0   0   0   0   0   0
(0, 4) pivot: 0, center: 3
   0   0   0   0   0   0   0   0   0   0
(0, 2) pivot: 0, center: 2
   0   0   0   0   0   0   0   0   0   0
(0, 1) pivot: 0, center: 1
   0   0   0   0   0   0   0   0   0   0
(3, 4) pivot: 3, center: 4
   0   0   0   0   0   0   0   0   0   0
(5, 9) pivot: 5, center: 8
   0   0   0   0   0   0   0   0   0   0
(5, 7) pivot: 5, center: 7
   0   0   0   0   0   0   0   0   0   0
(5, 6) pivot: 5, center: 6
   0   0   0   0   0   0   0   0   0   0
(8, 9) pivot: 8, center: 9
   0   0   0   0   0   0   0   0   0   0
after:     0   0   0   0   0   0   0   0   0   0
https://ideone.com/OsVQt
language:
C (gcc 8.3)
created:
12 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!