diff options
author | Kohei Yoshida <kohei.yoshida@gmail.com> | 2012-07-09 19:15:49 -0400 |
---|---|---|
committer | Kohei Yoshida <kohei.yoshida@gmail.com> | 2012-07-09 19:15:49 -0400 |
commit | 6fc09cc902bcaec81d6884f61360448fd3fd3b03 (patch) | |
tree | ccee5c49fbf34d6cbc5de5a1c5bc80bc86b4251a /merge-sort.cpp | |
parent | 806f566a08e6029f1a7460017dcee305c7a450ac (diff) |
Implemented merge sort.
Diffstat (limited to 'merge-sort.cpp')
-rw-r--r-- | merge-sort.cpp | 107 |
1 files changed, 107 insertions, 0 deletions
diff --git a/merge-sort.cpp b/merge-sort.cpp new file mode 100644 index 0000000..e7647a0 --- /dev/null +++ b/merge-sort.cpp @@ -0,0 +1,107 @@ + +#include <cstdlib> +#include <cstring> +#include <iostream> +#include <deque> + +using namespace std; + +typedef std::deque<int> list_t; + +void merge(list_t& lst, list_t left, list_t right) +{ + list_t res; + while (!left.empty() || !right.empty()) + { + if (!left.empty() && !right.empty()) + { + if (left[0] <= right[0]) + { + res.push_back(left[0]); + left.pop_front(); + } + else + { + res.push_back(right[0]); + right.pop_front(); + } + } + else if (!left.empty()) + { + res.push_back(left[0]); + left.pop_front(); + } + else if (!right.empty()) + { + res.push_back(right[0]); + right.pop_front(); + } + } + + res.swap(lst); +} + +void merge_sort(list_t& lst) +{ + size_t n = lst.size(); + if (n <= 1) + return; + + list_t left, right; + size_t mpos = n / 2; + for (size_t i = 0; i < n; ++i) + { + if (i < mpos) + left.push_back(lst[i]); + else + right.push_back(lst[i]); + } + + merge_sort(left); + merge_sort(right); + merge(lst, left, right); +} + +void print_list(const list_t& lst, const char* caption) +{ + cout << caption << ": "; + for (list_t::const_iterator i = lst.begin(), ie = lst.end(); i != ie; ++i) + cout << *i << " "; + cout << endl; +} + +int main(int argc, char** argv) +{ + if (argc < 2) + { + cout << "needs at least one argument" << endl; + return EXIT_FAILURE; + } + + const char* p = argv[1]; + const char* pend = p + strlen(p); + char* endptr = NULL; + long list_size = strtol(p, &endptr, 10); + if (endptr != pend) + { + cout << "invalid number: " << p << endl; + return EXIT_FAILURE; + } + + cout << "list size: " << list_size << endl; + + list_t lst; + for (int i = 0; i < list_size; ++i) + { + double val = rand(); + val /= RAND_MAX; + val *= 50; + lst.push_back(val); + } + + print_list(lst, "original"); + merge_sort(lst); + print_list(lst, "sorted"); + + return EXIT_SUCCESS; +} |