snippetcppMinor
Implementing the merge sort with only arrays, out of place
Viewed 0 times
thearraysmergewithplacesortimplementingonlyout
Problem
This has been asked a few times here, but I was wondering what I could do to improve the efficiency and readability of my code. My programming skill has gotten rusty, so I would like to elicit all constructive criticism that can make me write code better.
init:
merge()
merge_sort()
main()
init:
#include
using namespace std;merge()
//The merge function
void merge(int a[], int startIndex, int endIndex)
{
int size = (endIndex - startIndex) + 1;
int *b = new int [size]();
int i = startIndex;
int mid = (startIndex + endIndex)/2;
int k = 0;
int j = mid + 1;
while (k < size)
{
if((i<=mid) && (a[i] < a[j]))
{
b[k++] = a[i++];
}
else
{
b[k++] = a[j++];
}
}
for(k=0; k < size; k++)
{
a[startIndex+k] = b[k];
}
delete []b;
}merge_sort()
//The recursive merge sort function
void merge_sort(int iArray[], int startIndex, int endIndex)
{
int midIndex;
//Check for base case
if (startIndex >= endIndex)
{
return;
}
//First, divide in half
midIndex = (startIndex + endIndex)/2;
//First recursive call
merge_sort(iArray, startIndex, midIndex);
//Second recursive call
merge_sort(iArray, midIndex+1, endIndex);
//The merge function
merge(iArray, startIndex, endIndex);
}main()
//The main function
int main(int argc, char *argv[])
{
int iArray[10] = {2,5,6,4,7,2,8,3,9,10};
merge_sort(iArray, 0, 9);
//Print the sorted array
for(int i=0; i < 10; i++)
{
cout << iArray[i] << endl;
}
return 0;
}Solution
-
Try not to use
-
Code within a function should be indented as well. You already do this with other code blocks, and the same applies to functions.
-
Just avoid Hungarian notation:
We already know it's an
-
Prefer not to pass C arrays to functions in C++. This causes them to decay to a pointer; it does not actually pass the array itself.
Instead, pass in a storage container, such as an
If you have C++11, initialize the vector using list initialization:
If you don't have C++11, declare it and call
Pass it to a function with such parameters:
As its implementation is that of an array, you can still access its elements with
Storage containers do the memory allocation for you, so you will not need
Try not to use
using namespace std.-
Code within a function should be indented as well. You already do this with other code blocks, and the same applies to functions.
-
Just avoid Hungarian notation:
int iArray;We already know it's an
int array.-
Prefer not to pass C arrays to functions in C++. This causes them to decay to a pointer; it does not actually pass the array itself.
Instead, pass in a storage container, such as an
std::vector. Storage containers will not decay to a pointer, and they're more idiomatic C++.If you have C++11, initialize the vector using list initialization:
std::vector values { 2, 5, 6, 4, 7, 2, 8, 3, 9, 10 };If you don't have C++11, declare it and call
push_back() for each value:std::vector values;
values.push_back(2);
values.push_back(5);
// ...Pass it to a function with such parameters:
void merge_sort(std::vector values, int startIndex, int endIndex) {}As its implementation is that of an array, you can still access its elements with
[]. You can also use its iterators (more preferred).Storage containers do the memory allocation for you, so you will not need
new/delete. It's best to do as little manual memory allocation as possible in C++.Code Snippets
int iArray;std::vector<int> values { 2, 5, 6, 4, 7, 2, 8, 3, 9, 10 };std::vector<int> values;
values.push_back(2);
values.push_back(5);
// ...void merge_sort(std::vector<int> values, int startIndex, int endIndex) {}Context
StackExchange Code Review Q#48828, answer score: 4
Revisions (0)
No revisions yet.