Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
An implementation of Quick Sort algorithm with median.
#include <sstream>
#include <iostream>
#include <cstdlib>
#include <time.h>
#include <math.h>
using namespace std;
int divide(int* a, int bottom, int top);
void switchAt(int* a, int bottom, int top);
void quickSort(int* a, int bottom, int top)
{
if(top < bottom) {
return;
}
int j = divide(a, bottom, top);
quickSort(a, bottom, j - 1);
quickSort(a, j + 1, top);
}
void quickSort(int* a, int size)
{
quickSort(a, 0, size - 1);
}
int divide(int* a, int bottom, int top)
{
int mediana = (bottom + top) / 2;
switchAt(a, bottom, mediana);
int pivot = a[bottom]; // comparing element
int left = bottom; // left index
int right = top; // right index
while(right>left) {
// indexes have not yet crossed
// move the left index to the right, until you get to a number that is bigger than pivot
while(left<top && a[left] <= pivot) {
++left;
}
// move the right index to the left, until you get to a number that is smaller than pivot
while(right>bottom && a[right] >= pivot) {
--right;
}
if(right>left) {
// indexes have not crossed
switchAt(a, left, right);
}
}
switchAt(a, bottom, right);
return right;
}
void switchAt(int* a, int i1, int i2)
{
int z = a[i1];
a[i1] = a[i2];
a[i2] = z;
}
// Checks if a portion of the sequence is correctly sorted.
bool check(int* a, int bottom, int top)
{
for(int i = bottom; i<top; ++i) {
if(a[i + 1] < a[i]) {
return false;
}
}
return true;
}
// Checks if the sequence is correctly sorted.
bool check(int* a, int size)
{
return check(a, 0, size - 1);
}
void generateRandomSequence(int* a, int size);
void generateAscendinglySortedSequence(int* a, int size);
void generateDescendinglySortedSequence(int* a, int size);
void output(int* a, int size);
int showMenu();
int getIntBetween(string prompt, int bottom, int top);
int getInt(string prompt);
int main()
{
srand(time(NULL));
const int M = 10000000;
int* a = new int[M];
int size = -1;
while(true) {
switch(showMenu()) {
case 1: // Generate random sequence
{
size = getIntBetween("Size of the sequence: ", 1, M);
generateRandomSequence(a, size);
break;
}
case 2: // Generate ascendingly sorted sequence
{
size = getIntBetween("Size of the sequence: ", 1, M);
generateAscendinglySortedSequence(a, size);
break;
}
case 3: // Generate descendingly sorted sequence
{
size = getIntBetween("Size of the sequence: ", 1, M);
generateDescendinglySortedSequence(a, size);
break;
}
case 4: // Output sequence
{
if(size < 1) {
cout << "No sequence has been generated yet!" << endl;
break;
}
cout << "Sequence:" << endl;
output(a, size);
cout << endl;
break;
}
case 5: // Sort with Quick Sort algorithm
{
if(size < 1) {
cout << "No sequence has been generated yet!" << endl;
break;
}
clock_t start, finish;
double duration;
start = clock();
quickSort(a, size);
finish = clock();
duration = ((double)(finish - start)) / CLOCKS_PER_SEC;
cout << "Time: " << duration << " s" << endl;
break;
}
case 6: // Check if the sequence is sorted
{
if(size < 1) {
cout << "No sequence has been generated yet!" << endl;
break;
}
if(check(a, 0, size - 1)) {
cout << "Sequence is correctly sorted!" << endl;
} else {
cout << "Sequence is not sorted!" << endl;
}
break;
}
case 7: // Exit
{
delete a;
return 0;
}
}
}
}
int showMenu()
{
cout << endl;
cout << "Quick Sort - menu:" << endl;
cout << endl;
cout << "1) Generate random sequence" << endl;
cout << "2) Generate ascendingly sorted sequence" << endl;
cout << "3) Generate descendingly sorted sequence" << endl;
cout << "4) Output sequence" << endl;
cout << "5) Sort with Quick Sort algorithm" << endl;
cout << "6) Check if the sequence is sorted" << endl;
cout << "7) Exit" << endl;
cout << endl;
int option;
do {
option = getIntBetween("Choose: ", 1, 7);
} while(option < 1 || option > 7);
cout << endl;
return option;
}
void generateRandomSequence(int* a, int size)
{
for(int i = size-1; i>=0; --i) {
a[i] = rand();
}
}
void generateAscendinglySortedSequence(int* a, int size)
{
for(int i = 0; i<size; ++i) {
a[i] = i + 1;
}
}
void generateDescendinglySortedSequence(int* a, int size)
{
for(int i = size - 1; i >= 0; --i) {
a[i] = i + 1;
}
}
void output(int* a, int size)
{
for(int i = 0; i<size; ++i) {
cout << a[i] << " ";
}
}
int getIntBetween(string prompt, int bottom, int top)
{
int n;
do {
n = getInt(prompt);
} while(n<bottom || n>top);
return n;
}
int getInt(string prompt)
{
int output;
string input;
while(true) {
cout << prompt;
getline(cin, input);
stringstream ss(input);
if(ss >> output && !(ss >> input)) {
return output;
}
cin.clear();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.