Sorting-Algorithms

Implementation of 12 Sorting Algorithms in C++

This is my project in the Data Structures and Algorithms course. In this project, I had to implement 12 Sorting Algorithms and write a report about it. You can read the paper written in Vietnamese here.

Implementations

You can find the implementation of Selection Sort, Insertion Sort, Binary-Insertion Sort, Bubble Sort, Shaker Sort, Shell Sort, Heap Sort, Merge Sort, Quick Sort, Counting Sort, Radix Sort, and Flash Sort in the sorting-methods folder.

There are comments about complexity and notes about my implementations in each file.

How to run

You will need g++ to compile the main.cpp file with the flag -std=c++17. My command is: g++ main.cpp -std=c++17 -o main.exe

After that, you can run the file main.exe. It will run and measure the running time of all algorithms and print it to output.csv file.

Because I need to measure the running time of all algorithms but some runs very fast, I have to use the boost/chrono library to measure the running time in nanoseconds. If you don't have boost library, you can rename the file std-time.h to timer.h, both file be in the helper folder

Note

Let n be the length of the array a, while a[i] is the i-th element of the array.

• All arrays are 0-indexed.

• All elements are non-negative integers.

• I tested all implementations with n not greater than 300 000 and a[i] not greater than 300 000. The test data is generated by DataGenerator provided by my teacher, don't blame me about the bad coding style of that file.

• Almost all algorithms work well if you increase n and a[i], but please take a look at Flash Sort and Counting Sort if you want to do that.

  • Please change the size of the array __L in Flash Sort and __cnt array in Counting Sort. You can use a dynamic array if needed.
  • The reason I don't want to use a dynamic array is that it increases the run time of the algorithm.

• Some notes about the implementation details:

  • Radix Sort: Most Significant Digit, base 2.
  • Quick Sort: Random Pivot
  • Merge Sort: I used std::inplace_merge instead of writing my own merge function.
  • Binary Insertion Sort: I use std::upper_bound instead of writing own binary search function

Credit

You are free to use my code to do whatever you want unless you want to use it for your report in Data Structures and Algorithms course in HCMUS, you have to credit me.