Tag: C++

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;
}