Hello! Below is my attempt at a quicksort. Sorters are really interesting code because they can be done in so many different ways, which can make such a difference in the speed an array is sorted. Here (No longer online :(, here’s another) is a visual example from my old professor Adam Smith. From this visual guide, you’re able to see when quicksort is most and least effective. Here’s some output:
//
// Quicksort2.cpp
//
// Sorter which will sort array of random values in the "quicksort" style.
//
// Created by Aidan Takami on 2/1/18.
// Copyright © 2018 Aidan Takami. All rights reserved.
//
/*
Must include iostream, cstdlib, and ctime. Site keeps deleting
these libraries thinking they are HTML tags
/*
#include
#include
#include
using namespace std;
void printArray(int r[]);
void switchValues(int r[], int, int);
void randmoArray(int r[]);
void quickSort(int r[], int, int);
//Declares the array to be sorted, as well as the const to represent the size of the array
int r[100];
const int SIZE = (sizeof(r)/4);
//Method to print out values of the array
void printArray(int r[])
{
int i=0;
while(i<SIZE){
cout<<r[i]<<",";
i++;
}
}
//Method to swap the values at the locations of the 2 int args, within the array provided
void switchValues(int r[],int leftSide, int rightSide){
int temp = r[leftSide];
r[leftSide] = r[rightSide];
r[rightSide] = temp;
}
//Method which will randomize an array of the size of the const int SIZE
void randomArray(int r[]){
for(int rep = 0; rep < SIZE; rep++){
r[rep] = int (rand()%100);
}
}
//Quicksort method
void quicksort(int r[], int leftSide, int rightSide){
int leftTemp = leftSide;
int rightTemp = rightSide;
int pivot = r[(leftSide+rightSide)/2];
while(leftSidepivot)
rightTemp--;
if(leftTemp<=rightTemp){
switchValues(r, leftTemp, rightTemp);
leftTemp++;
rightTemp--;
}
else{
if(leftSide<rightTemp)
quicksort(r, leftSide, rightTemp);
if(leftTemp<rightSide)
quicksort(r,leftTemp,rightSide);
return;
}
}
}
//Main method for testing the quicksort
int main() {
cout << "Generating random array!" << endl;
randomArray(r);
cout << "The unsorted array: ";
printArray(r);
cout << endl << endl;
cout << "Sorting in progress..." << endl;
const clock_t beginTime = clock();
quicksort(r, 0, SIZE);
float totalTime = ( clock () - beginTime ) / CLOCKS_PER_SEC;
cout << "The sorted array: ";
printArray(r);
cout << endl;
cout << "The sort took " << totalTime << " milliseconds!" << endl;
return 0;
}
Aidan Takami Game Development 