• 1

• 9.5k
• 4
• 38
• 96

I am fairly new to C++, and to have a break from all that Java programming, I decided to do something in C++, which is sorting. The four sorting algorithms are:

• Bubble Sort
• Insertion Sort
• Quick Sort
• Merge Sort

Code:

#include <iostream>
#include <ctime>
#include <cstdlib>
#include <iterator>
#include <chrono>
#define SIZE 100
#define MAX 1000
typedef std::chrono::high_resolution_clock Clock;
void bubbleSort(int toSort[], int length);
void insertionSort(int toSort[], int length);
void quickSort(int toSort[], int length);
void mergeSort(int toSort[], int length);
void printArray(int arr[], int length)
{
 for (int i = 0; i < length; i++) {
 std::cout << arr[i] << " ";
 }
 std::cout << "\n";
}
int main()
{
 srand(time(NULL));
 int arr[SIZE];
 for (int i = 0; i < SIZE; i++) {
 arr[i] = rand() % MAX;
 }
 int arrCopy[SIZE];
 std::copy(std::begin(arr), std::end(arr), std::begin(arrCopy));
 auto start = Clock::now();
 bubbleSort(arrCopy, SIZE);
 auto end = Clock::now();
 printArray(arrCopy, SIZE);
 std::cout << "Time taken (nanoseconds): " << std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count() << std::endl;
 std::copy(std::begin(arr), std::end(arr), std::begin(arrCopy));
 start = Clock::now();
 insertionSort(arrCopy, SIZE);
 end = Clock::now();
 printArray(arrCopy, SIZE);
 std::cout << "Time taken (nanoseconds): " << std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count() << std::endl;
 std::copy(std::begin(arr), std::end(arr), std::begin(arrCopy));
 start = Clock::now();
 quickSort(arrCopy, SIZE);
 end = Clock::now();
 printArray(arrCopy, SIZE);
 std::cout << "Time taken (nanoseconds): " << std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count() << std::endl;
 std::copy(std::begin(arr), std::end(arr), std::begin(arrCopy));
 start = Clock::now();
 mergeSort(arrCopy, SIZE);
 end = Clock::now();
 printArray(arrCopy, SIZE);
 std::cout << "Time taken (nanoseconds): " << std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count() << std::endl;
 return 0;
}
void swapElements(int toSort[], int i, int j) {
 int temp = toSort[i];
 toSort[i] = toSort[j];
 toSort[j] = temp;
}
void insertionSort(int toSort[], int length)
{
 int temp;
 for (int i = 0; i < length; i++) {
 for (int j = i; j > 0; j--) {
 if (toSort[j] < toSort[j - 1]) {
 temp = toSort[j];
 toSort[j] = toSort[j - 1];
 toSort[j - 1] = temp;
 }
 }
 }
}
void bubbleSort(int toSort[], int length)
{
 int temp;
 for (int i = 0; i < length; i++) {
 for (int j = 1; j < length - i; j++) {
 if (toSort[j] < toSort[j - 1]) {
 temp = toSort[j];
 toSort[j] = toSort[j - 1];
 toSort[j - 1] = temp;
 }
 }
 }
}
int partitionElements(int toSort[], int beginPtr, int endPtr) {
 int pivot = toSort[(rand() % endPtr - beginPtr + 1) + beginPtr];
 beginPtr--;
 while (beginPtr < endPtr) {
 do {
 beginPtr++;
 } while (toSort[beginPtr] < pivot);
 do {
 endPtr--;
 } while (toSort[endPtr] > pivot);
 if (beginPtr < endPtr) {
 // Make sure they haven't crossed yet
 swapElements(toSort, beginPtr, endPtr);
 }
 }
 return beginPtr;
}
void quickSort(int toSort[], int beginPtr, int endPtr)
{
 if (endPtr - beginPtr < 2) {
 return;
 }
 if (endPtr - beginPtr == 2) {
 // Optimization: array length 2
 if (toSort[beginPtr] > toSort[endPtr - 1]) {
 swapElements(toSort, beginPtr, endPtr - 1);
 }
 return;
 }
 int splitIndex = partitionElements(toSort, beginPtr, endPtr);
 quickSort(toSort, beginPtr, splitIndex );
 quickSort(toSort, splitIndex, endPtr);
}
void quickSort(int toSort[], int length)
{
 srand(time(NULL));
 quickSort(toSort, 0, length);
}
void copyArray(int src[], int srcPos, int dest[], int destPos, int toCopyLength)
{
 for (int i = 0; i < toCopyLength; i++) {
 dest[i + destPos] = src[i + srcPos];
 }
}
void mergeParts(int toSort[], int buffer[], int beginPtr, int middle,
 int endPtr) {
 copyArray(toSort, beginPtr, buffer, beginPtr, endPtr - beginPtr);
 int index1 = beginPtr;
 int index2 = middle;
 int resultindex = beginPtr;
 while (index1 < middle && index2 < endPtr) {
 if (buffer[index1] < buffer[index2]) {
 toSort[resultindex++] = buffer[index1++];
 } else {
 toSort[resultindex++] = buffer[index2++];
 }
 }
 if (index1 < middle) {
 copyArray(buffer, index1, toSort, resultindex, middle - index1);
 }
 if (index2 < endPtr) {
 copyArray(buffer, index2, toSort, resultindex, endPtr - index2);
 }
}
void mergeSort(int toSort[], int buffer[], int beginPtr, int endPtr) {
 if (beginPtr + 1 < endPtr) {
 mergeSort(toSort, buffer, beginPtr, (beginPtr + endPtr) / 2);
 mergeSort(toSort, buffer, (beginPtr + endPtr) / 2, endPtr);
 mergeParts(toSort, buffer, beginPtr, (beginPtr + endPtr) / 2, endPtr);
 }
}
void mergeSort(int toSort[], int length)
{
 mergeSort(toSort, new int[length], 0, length);
}

Results:

...
Time taken (nanoseconds): 0
...
Time taken (nanoseconds): 0
...
Time taken (nanoseconds): 0
...
Time taken (nanoseconds): 0

NOTE: The results above do not print the correct time taken. Please ignore that fact, and review my code.

Questions:

1. Any bad practices? I carry everything from Java, and anything that is different (e.g. System.nanoTime() and std::chrono::high_resolution_clock) I get off SO.

2. Algorithm criticism?

3. Anything that can be done more efficiently and/or with less code?