Advertisement
Guest User

Untitled

a guest
Nov 25th, 2015
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.26 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. int *array;
  5.  
  6. int compare(int i, int j)
  7. {
  8. if (array[i] == array[j]) return 0;
  9. return array[i] < array[j] ? -1 : 1;
  10. }
  11.  
  12. void swap(int i, int j)
  13. {
  14. int t = array[i];
  15. array[i] = array[j];
  16. array[j] = t;
  17. }
  18.  
  19. void selectSort(int l, int r)
  20. {
  21. int i,j,k;
  22. for (j = r; j > l; j--) {
  23. k = j;
  24. i = j - 1;
  25. while (i >= l) {
  26. if (compare(k,i) < 0)
  27. k = i;
  28. i = i - 1;
  29. }
  30. swap(j,k);
  31. }
  32. }
  33.  
  34. int partition(int left, int right)
  35. {
  36. int i,j;
  37. i = left;
  38. j = left;
  39. while (j < right) {
  40. if (compare(j,right) < 0) {
  41. swap(i,j);
  42. i++;
  43. }
  44. j++;
  45. }
  46. swap(i,right);
  47. return i;
  48. }
  49.  
  50. void quicksort(int m, int left, int right)
  51. {
  52. int b;
  53. while ((left < right) && ((right - left + 1) >= m)){
  54. b = partition(left,right);
  55. quicksort(m,left,b - 1);
  56. left = b + 1;
  57. }
  58. selectSort(left,right);
  59. }
  60.  
  61. int main()
  62. {
  63. int i, n, m;
  64. scanf("%d %d", &n,&m);
  65. array = (int*)calloc(n,sizeof(int));
  66. for (i = 0; i < n; i++) scanf("%d", array + i);
  67. quicksort(m, 0, n - 1);
  68. for (i = 0; i < n; i++) printf("%d ", array[i]);
  69. free(array);
  70. return 0;
  71. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement