Advertisement
alsiva

Untitled

Mar 28th, 2022
14
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.61 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <fstream>
  5. using namespace std;
  6.  
  7. bool compare(string a, string b) {
  8.  
  9. for (int i = 0; i < a.length() && i < b.length(); i++) {
  10. if (a[i] > b[i]) return true;
  11. if (a[i] < b[i]) return false;
  12. }
  13.  
  14. if (a.length() < b.length()) return compare(a, b.substr(a.length()));
  15. if (a.length() > b.length()) return compare(a.substr(b.length()), b);
  16.  
  17. return true;
  18. }
  19.  
  20. vector<string> quickSort(vector<string> numbers) {
  21.  
  22. int middle = (numbers.size()-1) / 2;
  23. vector<string> left, right, mergedNums, midNums;
  24. if (numbers.size() < 1) {
  25. return numbers;
  26. }
  27.  
  28. for (int i = 0; i < numbers.size(); i++) {
  29. if (compare(numbers[i], numbers[middle]) && i != middle) {
  30. left.push_back(numbers[i]);
  31. } else if (i == middle) {
  32. midNums.push_back(numbers[i]);
  33. } else if ((compare(numbers[middle], numbers[i]) && i != middle)) {
  34. right.push_back(numbers[i]);
  35. }
  36. }
  37.  
  38. left = quickSort(left);
  39. right = quickSort(right);
  40.  
  41. for (int i = 0; i < left.size(); i++) {
  42. mergedNums.push_back(left[i]);
  43. }
  44.  
  45. mergedNums.push_back(midNums[0]);
  46.  
  47. for (int i = 0; i < right.size(); i++) {
  48. mergedNums.push_back(right[i]);
  49. }
  50.  
  51. return mergedNums;
  52. }
  53.  
  54. int main() {
  55. vector<string> numbers;
  56. vector<string> sorted;
  57. string s;
  58.  
  59.  
  60. while (cin >> s) {
  61. numbers.push_back(s);
  62. }
  63.  
  64. sorted = quickSort(numbers);
  65.  
  66. for (auto & i : sorted) {
  67. cout << i;
  68. }
  69.  
  70.  
  71. }
  72.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement