Advertisement
Guest User

Untitled

a guest
Jan 22nd, 2017
121
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.86 KB | None | 0 0
  1. for (int k = start; k < end; k++)
  2. {
  3. if (L.at(x) <= R.at(y))
  4. {
  5. v.at(k) = L.at(x); // out of bounds
  6. x++;
  7. }
  8. else
  9. {
  10. v.at(k) = R.at(y); // out of bounds
  11. y++;
  12. }
  13.  
  14. }
  15.  
  16. #include <iostream>
  17. #include <fstream>
  18. #include <string>
  19. #include <vector>
  20. #include <algorithm>
  21.  
  22. using namespace std
  23.  
  24. vector<string> readFile(string fileName) {
  25. /* reads a textfile into vector. Works dandy. */ }
  26.  
  27. vector<string> merge(vector<string>& v, int start, int mid, int end)
  28. {
  29. int n1 = mid - start + 1;
  30. int n2 = end - mid;
  31.  
  32. vector<string> L;
  33. vector<string> R;
  34.  
  35. L.resize(n1 + 1); // size left vector
  36. R.resize(n2 + 1); // size right vector
  37.  
  38. for (int i = 1; i < n1; i++) {
  39. L.at(i) = v.at(start + i - 1); // populate left vector
  40. }
  41. for (int j = 1; j < n2; j++) {
  42. R.at(j) = v.at(mid + j); // populate right vector
  43. }
  44.  
  45. int x = 1;
  46. int y = 1;
  47.  
  48. for (int k = start; k < end; k++)
  49. {
  50. if (L.at(x) <= R.at(y)) {
  51. v.at(k) = L.at(x); // merge left vector into v
  52. x++;
  53. }
  54. else{
  55. v.at(k) = R.at(y); // merge right vector into v
  56. y++;
  57. }
  58.  
  59. }
  60. return v;
  61. }
  62. vector<string> mergeSort(vector<string>& v, int start, int end)
  63. {
  64. int middle;
  65. if (start < end) // base case
  66. {
  67. middle = (start + end) / 2; // find middle
  68. mergeSort(v, start, middle); // divide vectors
  69. mergeSort(v, middle + 1, end);
  70. merge(v, start, middle, end); // merge sorted vectors
  71. }
  72. return v;
  73. }
  74. int main() {
  75. vector<string> vectorReadIn;
  76. vector<string> sortedVector;
  77. int x = 0;
  78.  
  79. string fileName = "C:/Users/User/Downloads/Algorithims/Perm Words/perm15k.txt";
  80.  
  81. vectorReadIn = readFile(fileName); // reads file into vector
  82.  
  83. sortedVector = mergeSort(vectorReadIn, 1, vectorReadIn.size()); // calls mergesort
  84. cout << "Sorted file:" << endl;
  85. while (x < 8) {
  86. cout << sortedVector.at(x);
  87. x++; }
  88. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement