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:
Any bad practices? I carry everything from Java, and anything that is different (e.g.
System.nanoTime()
andstd::chrono::high_resolution_clock
) I get off SO.Algorithm criticism?
Anything that can be done more efficiently and/or with less code?