Skip to main content
Code Review

Return to Question

broken code fixed
Source Link
user104759
user104759

Here is my merge sort c++ implementation. Looking for code improvement and optimization opinion. Just one question which is better *k++ = *i++; or, *k = *i; ++k; ++i;.

/*
 * Merge Sort
 */
#include <iostream>
#include <vector>
void mergeSort(std::vector<int> &v, std::vector<int>::iterator p, std::vector<int>::iterator r);
void merge(std::vector<int> &v, std::vector<int>::iterator p, std::vector<int>::iterator q, std::vector<int>::iterator r);
void print(const std::vector<int> &v);
int main()
{
 std::ios_base::sync_with_stdio(false);
 std::vector<int> vv;
 {10, 9, 8, 7,int 6,temp 5,= 4,0;
 3, 2, 1};
 while (std::cin >> //temp) Print{
 the vector before sorting.
 print(v.push_back(temp);
 }

 // Sort
 mergeSort(v, v.begin(), v.end() - 1);
 // Print the vector after sorting.
 print(v);
 return 0;
}
void mergeSort(std::vector<int> &v, std::vector<int>::iterator p, std::vector<int>::iterator r) {
 // Base case: if (p >= r) then return
 if (p < r) {
 auto q = p + (r - p) / 2;
 mergeSort(v, p, q);
 mergeSort(v, q+1, r);
 merge(v, p, q, r);
 }
}
void merge(std::vector<int> &v, std::vector<int>::iterator p, std::vector<int>::iterator q, std::vector<int>::iterator r) {
 std::vector<int>::size_type leftVectorSize = q - p + 1;
 std::vector<int>::size_type rightVectorSize = r - q;
 std::vector<int> vLeft(leftVectorSize);
 std::vector<int> vRight(rightVectorSize);
 // Copy elements p to q
 auto it = p;
 for (auto &i : vLeft) {
 i = *it++;
 }
 // Copy elements q + 1 to r
 for (auto &i : vRight) {
 i = *it++;
 }
 auto i = vLeft.cbegin(), j = vRight.cbegin();
 auto k = p;
 // Compare and merge
 while (i != vLeft.end() && j != vRight.end()) {
 if (*i <= *j) {
 *k++ = *i++;
 } else {
 *k++ = *j++;
 }
 }
 // Copy rest of the elements if any
 while (i != vLeft.end()) {
 *k++ = *i++;
 }
 // Copy rest of the elements if any
 while (j != vRight.end()) {
 *k++ = *j++;
 }
}
void print(const std::vector<int> &v) {
 for (const auto &i : v) {
 std::cout << i << " ";"\n";
 }
 std::cout << "\n";
}

Here is my merge sort c++ implementation. Looking for code improvement and optimization opinion.

/*
 * Merge Sort
 */
#include <iostream>
#include <vector>
void mergeSort(std::vector<int> &v, std::vector<int>::iterator p, std::vector<int>::iterator r);
void merge(std::vector<int> &v, std::vector<int>::iterator p, std::vector<int>::iterator q, std::vector<int>::iterator r);
void print(const std::vector<int> &v);
int main()
{
 std::ios_base::sync_with_stdio(false);
 std::vector<int> v {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
 // Print the vector before sorting.
 print(v);
 // Sort
 mergeSort(v, v.begin(), v.end());
 // Print the vector after sorting.
 print(v);
 return 0;
}
void mergeSort(std::vector<int> &v, std::vector<int>::iterator p, std::vector<int>::iterator r) {
 // Base case: if (p >= r) then return
 if (p < r) {
 auto q = p + (r - p) / 2;
 mergeSort(v, p, q);
 mergeSort(v, q+1, r);
 merge(v, p, q, r);
 }
}
void merge(std::vector<int> &v, std::vector<int>::iterator p, std::vector<int>::iterator q, std::vector<int>::iterator r) {
 std::vector<int>::size_type leftVectorSize = q - p + 1;
 std::vector<int>::size_type rightVectorSize = r - q;
 std::vector<int> vLeft(leftVectorSize);
 std::vector<int> vRight(rightVectorSize);
 // Copy elements p to q
 auto it = p;
 for (auto &i : vLeft) {
 i = *it++;
 }
 // Copy elements q + 1 to r
 for (auto &i : vRight) {
 i = *it++;
 }
 auto i = vLeft.cbegin(), j = vRight.cbegin();
 auto k = p;
 // Compare and merge
 while (i != vLeft.end() && j != vRight.end()) {
 if (*i <= *j) {
 *k++ = *i++;
 } else {
 *k++ = *j++;
 }
 }
 // Copy rest of the elements if any
 while (i != vLeft.end()) {
 *k++ = *i++;
 }
 // Copy rest of the elements if any
 while (j != vRight.end()) {
 *k++ = *j++;
 }
}
void print(const std::vector<int> &v) {
 for (const auto &i : v) {
 std::cout << i << " ";
 }
 std::cout << "\n";
}

Here is my merge sort c++ implementation. Looking for code improvement and optimization opinion. Just one question which is better *k++ = *i++; or, *k = *i; ++k; ++i;.

/*
 * Merge Sort
 */
#include <iostream>
#include <vector>
void mergeSort(std::vector<int> &v, std::vector<int>::iterator p, std::vector<int>::iterator r);
void merge(std::vector<int> &v, std::vector<int>::iterator p, std::vector<int>::iterator q, std::vector<int>::iterator r);
void print(const std::vector<int> &v);
int main()
{
 std::ios_base::sync_with_stdio(false);
 std::vector<int> v;
 int temp = 0;
 while (std::cin >> temp) {
 v.push_back(temp);
 }

 // Sort
 mergeSort(v, v.begin(), v.end() - 1);
 // Print the vector after sorting.
 print(v);
 return 0;
}
void mergeSort(std::vector<int> &v, std::vector<int>::iterator p, std::vector<int>::iterator r) {
 // Base case: if (p >= r) then return
 if (p < r) {
 auto q = p + (r - p) / 2;
 mergeSort(v, p, q);
 mergeSort(v, q+1, r);
 merge(v, p, q, r);
 }
}
void merge(std::vector<int> &v, std::vector<int>::iterator p, std::vector<int>::iterator q, std::vector<int>::iterator r) {
 std::vector<int>::size_type leftVectorSize = q - p + 1;
 std::vector<int>::size_type rightVectorSize = r - q;
 std::vector<int> vLeft(leftVectorSize);
 std::vector<int> vRight(rightVectorSize);
 // Copy elements p to q
 auto it = p;
 for (auto &i : vLeft) {
 i = *it++;
 }
 // Copy elements q + 1 to r
 for (auto &i : vRight) {
 i = *it++;
 }
 auto i = vLeft.cbegin(), j = vRight.cbegin();
 auto k = p;
 // Compare and merge
 while (i != vLeft.end() && j != vRight.end()) {
 if (*i <= *j) {
 *k++ = *i++;
 } else {
 *k++ = *j++;
 }
 }
 // Copy rest of the elements if any
 while (i != vLeft.end()) {
 *k++ = *i++;
 }
 // Copy rest of the elements if any
 while (j != vRight.end()) {
 *k++ = *j++;
 }
}
void print(const std::vector<int> &v) {
 for (const auto &i : v) {
 std::cout << i << "\n";
 }
}
Post Undeleted by Community Bot
Post Deleted by Community Bot
Source Link
user104759
user104759

Merge sort C++14 implementation

Here is my merge sort c++ implementation. Looking for code improvement and optimization opinion.

/*
 * Merge Sort
 */
#include <iostream>
#include <vector>
void mergeSort(std::vector<int> &v, std::vector<int>::iterator p, std::vector<int>::iterator r);
void merge(std::vector<int> &v, std::vector<int>::iterator p, std::vector<int>::iterator q, std::vector<int>::iterator r);
void print(const std::vector<int> &v);
int main()
{
 std::ios_base::sync_with_stdio(false);
 std::vector<int> v {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
 // Print the vector before sorting.
 print(v);
 // Sort
 mergeSort(v, v.begin(), v.end());
 // Print the vector after sorting.
 print(v);
 return 0;
}
void mergeSort(std::vector<int> &v, std::vector<int>::iterator p, std::vector<int>::iterator r) {
 // Base case: if (p >= r) then return
 if (p < r) {
 auto q = p + (r - p) / 2;
 mergeSort(v, p, q);
 mergeSort(v, q+1, r);
 merge(v, p, q, r);
 }
}
void merge(std::vector<int> &v, std::vector<int>::iterator p, std::vector<int>::iterator q, std::vector<int>::iterator r) {
 std::vector<int>::size_type leftVectorSize = q - p + 1;
 std::vector<int>::size_type rightVectorSize = r - q;
 std::vector<int> vLeft(leftVectorSize);
 std::vector<int> vRight(rightVectorSize);
 // Copy elements p to q
 auto it = p;
 for (auto &i : vLeft) {
 i = *it++;
 }
 // Copy elements q + 1 to r
 for (auto &i : vRight) {
 i = *it++;
 }
 auto i = vLeft.cbegin(), j = vRight.cbegin();
 auto k = p;
 // Compare and merge
 while (i != vLeft.end() && j != vRight.end()) {
 if (*i <= *j) {
 *k++ = *i++;
 } else {
 *k++ = *j++;
 }
 }
 // Copy rest of the elements if any
 while (i != vLeft.end()) {
 *k++ = *i++;
 }
 // Copy rest of the elements if any
 while (j != vRight.end()) {
 *k++ = *j++;
 }
}
void print(const std::vector<int> &v) {
 for (const auto &i : v) {
 std::cout << i << " ";
 }
 std::cout << "\n";
}
lang-cpp

AltStyle によって変換されたページ (->オリジナル) /