Thoughts of an Angel
 
I have finally implemented the QuickSort algorithm.  I feel like I've made some progress!  I did have to "borrow" some code from www.dreamincode.net, so all credit given to whom all it is due.  I did at the very least take some very thorough notes about what the code was doing.  You can find this here:

#include "stdafx.h"
#include <iostream>
using namespace std;

/* Note to self: Self, the syntax is not to say "public: class."  This is not Java.*/
class sortOut { 

/*
Intake is responsible for accepting values into an array
The "*" notation is a pointer, allows for passing by reference to memory rather than the value itself.  
This notation is recommended for memory allocation devices (i.e. arrays, vectors, etc). There's not much 
of another way for the main() method to know what values to pass on to other methods being called.
*/
public : void intake(int *store) 
{
int number = 0;
cout << "Please give me 10 numbers: ";
for(int i = 0; i < 10; i++)
{

cin >> number;
store[i] = number;

}//end for

}//end intake function

/*
Exchange tells the arrays in the subsequent methods how to swap numbers.  
It puts int a into a temporary variable to be assigned to b, which will in 
turn equal a.  
*/

public : void exchange(int &a, int &b)
{
int temp;
temp = a;
a=b;
b=temp;
}

/*
sort() is in charge of sorting out the numbers (DUH!).  It accepts the store array passed by reference, 
the int representing the first element in the array, and the int representing the last element in the
array as arguments. 

The pivot point is set to the first element in the store array.
It will check to see if the last element is greater than the first element in the array.
If so, the int dividePoint is assigned to the function split().  split() is called for value assignment.
The pivot point is then assigned as the point of array division.
As recursion works, the sort function is the recalled until the the array is fully sorted.
*/
public : void sort(int* store, int firstElement, int lastElement)
{
int pivot = store[firstElement];
int dividePoint;
if(lastElement > firstElement)
{
dividePoint = split(store, pivot, firstElement, lastElement);
store[dividePoint] = pivot;
sort(store, firstElement, dividePoint-1);
sort(store, dividePoint+1, lastElement);
}

}// end sort

/*
split() is the function that divides the array.  Essentially, the array splits itself in half, sorts those halves, 
then those halves split in halves where those are sorted, and so on.  The process restarts itself until the array
is fully sorted.

The firstElement is assigned to be the leftmost element.  The last element is assigned to be the rightmost element.
While the leftmost is less than the rightmost elements in the array, and the pivot point is less than the rightmost element and
the rightmost element is greater than the leftmst, the rightmost moves to the value left of it (from 9 to 8, etc) and tests to see if that element
is greater or less than the pivot value.
exchange() is called to swap values found unsorted in each round in the loop.

The process is much the same for the while loop testing to see if the leftmost value is less than the value of the pivot.  
As it finds values that are in their proper place, it moves on to the value to the right (from 0 to 1, etc) to test values some more.
It is to return the leftmost value in order to begin the splitting and sorting process all over again until the array is fully sorted.
*/
public : int split(int* store, int pivot, int firstElement, int lastElement)
{
int left = firstElement;
int right = lastElement;

while(left < right)
{
while(pivot < store[right] && right > left)
{
right--;

}
exchange(store[left], store[right]);
while(pivot >= store[left] && left < right)
{
left++;
}
exchange(store[right], store[left]);
}
return left;
}
};

/*
main() is self-explanatory.  Remember to initialize values in the functions that are called.  In most sorting algorithms
involving a pivot point, the pivot is going to equal 0.  The leftmost and rightmost array values are assigned to the
elements that they represent.  Remember also to create an instance of the class you're callling functions for.

exchange() and split() were already called in/by the sort() function, so there is no need to call them in the main() method.

It is best to have the output in the main method so that you know that all methods were implemented properly.
*/
int main()
{

sortOut s; // Need to create an instance of the class
int storage[10];
int left = 0, right = 9;
int pivot = 0;

s.intake(storage); // Small o -> O
s.sort(storage, left, right);

for(int i = 0; i < 10; i++)
{
cout << storage[i] << " ";
}



return 0;
}

 


Comments




Leave a Reply