Herowaree

QuickSort com String

Dec 5th, 2014
217
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.30 KB | None | 0 0
  1. #include <string.h>
  2. #include <stdio.h>
  3.  
  4. void swap_str_ptrs(char const **arg1, char const **arg2)
  5. {
  6. const char *tmp = *arg1;
  7. *arg1 = *arg2;
  8. *arg2 = tmp;
  9. }
  10.  
  11. void quicksort_strs(char const *args[], unsigned int len);
  12.  
  13. void print_list(char const *args[], unsigned len)
  14. {
  15. unsigned i=0;
  16. for (;i<len;++i)
  17. puts(args[i]);
  18. }
  19.  
  20. int main()
  21. {
  22. char const *args[] =
  23. {
  24. "this", "is", "a", "test", "of", "quicksort", "with", "strings"
  25. };
  26.  
  27. srand((unsigned)time(NULL));
  28. quicksort_strs(args, sizeof(args)/sizeof(*args));
  29. print_list(args, sizeof(args)/sizeof(*args));
  30. return 0;
  31. }
  32.  
  33. void quicksort_strs(char const *args[], unsigned int len)
  34. {
  35. unsigned int i, pvt=0;
  36.  
  37. if (len <= 1)
  38. return;
  39.  
  40. // swap a randomly selected value to the last node
  41. swap_str_ptrs(args+((unsigned int)rand() % len), args+len-1);
  42.  
  43. // reset the pivot index to zero, then scan
  44. for (i=0;i<len-1;++i)
  45. {
  46. if (strcmp(args[i], args[len-1]) < 0)
  47. swap_str_ptrs(args+i, args+pvt++);
  48. }
  49.  
  50. // move the pivot value into its place
  51. swap_str_ptrs(args+pvt, args+len-1);
  52.  
  53. // and invoke on the subsequences. does NOT include the pivot-slot
  54. quicksort_strs(args, pvt++);
  55. quicksort_strs(args+pvt, len - pvt);
  56. }
Advertisement
Add Comment
Please, Sign In to add comment