Advertisement
Guest User

Untitled

a guest
Oct 31st, 2014
157
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.03 KB | None | 0 0
  1. static inline
  2. int* choose_pivot(int *left, int *right) {
  3. /* FIX ME */
  4. }
  5.  
  6. /*
  7. * partition(left, right, pivot): push value less than *pivot on the left
  8. * return the new pivot.
  9. */
  10. int* partition(int *left, int *right, int *pivot) {
  11. /* FIX ME */
  12. }
  13.  
  14. /*
  15. * quick_sort(left, right)
  16. */
  17. void quick_sort(int *left, int *right) {
  18. /* FIX ME */
  19. }
  20.  
  21. static inline
  22. int* choose_pivot(int *left, int *right) {
  23. return &left[(right - left)/2];
  24. }
  25.  
  26. void swap(int *a, int *b)
  27. {
  28. int c = *a;
  29. *a = *b;
  30. *b = c;
  31. }
  32. int* partition(int *left, int *right, int *pivot) {
  33. int *i, *q;
  34. q = right;
  35. i = left ;
  36. while ( q > pivot )
  37. {
  38. while ( pivot < i )
  39. pivot++;
  40. while ( q > i )
  41. q--;
  42. if ( *q > *pivot )
  43. {
  44. swap(pivot,q);
  45. }
  46. }
  47. swap(left, q);
  48. return q ;
  49. }
  50. void quick_sort(int *left, int *right) {
  51. if(left >= right)
  52. return;
  53.  
  54. int *pivot = partition(left, right, choose_pivot(left, right));
  55. quick_sort(left, pivot-1);
  56. quick_sort(pivot + 1, right);
  57. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement