1. Insertion Sort 2. Selection Sort 3. Merge Sort 4. Quick Sort This assignment
ID: 3675114 • Letter: 1
Question
1. Insertion Sort
2. Selection Sort
3. Merge Sort
4. Quick Sort
This assignment requires you to complete the following tasks:
1. Create several text files (you can simply download any word files, or take one of your writing assignments), copy the content, and paste it to a Word document. Eliminate any non-text tokens such as punctuation marks, paragraph numbers, images, etc. Verify that the words remaining in your file appear to be in random order (i.e., your words should NOT be sorted, or approximately sorted, in any way). Then save the resulting document as a text-only (.txt) file consisting of at least 5000 words.
2. Write Java program that creates an ARRAY of 5000 String objects that will store each word from the text file. Your program will read in each word from the file, and stores the first 5000 words values in the array. (Do not eliminate duplicate words.)
3. Add a method that displays all Strings in the array, and use it to display the original (unsorted) list.
4. Add a method to your program that will copy the original String array to a second array. Verify that this method works correctly by calling your display method to new the second array.
5. Add the Insertion Sort method to your program. Call Insertion Sort to sort the words of the second array in alphabetical order. Your Insertion Sort method should count the number of comparisons executed to sort the array and the total number the array element swaps. Display both counts on the command line. Then call your display method to verify that the Insertion Sort method works correctly.
6. Call Insertion Sort again with the second array, which is now in sorted order. Verify that a sorted list allows Insertion Sort to exhibit best-case behavior for both comparisons and swaps by interactively displaying both totals.
7. Add a Selection Sort method to your program, and add code that counts the total number of comparisons and the total number of swaps. Copy the original unsorted array to the second array and call Selection Sort. Display the total number of comparisons and swaps. Verify that your Selection Sort implementation works correctly.
8. Call your Selection Sort again with the (now sorted) array, and verify that the equal number of comparisons and swaps are made even when the list is already in sorted order.
9. Add a Merge Sort method to your program, and add code that counts the total number of comparisons and the total number of swaps. Copy the first (unsorted) array to the second array, call Merge Sort, and display the total number of comparisons and the total number of swaps. Call your display method to verify that the words are sorted.
10. To verify that the best-case behavior of Merge Sort occurs with a list that is already sorted, call Merge Sort again with the (now sorted) second array. Display the total number of comparisons and swaps and verify that the list remains sorted after Merge Sort has completed.
11. Finally, add the QuickSort method to your program, and again add code that counts the total number of comparisons and the total number of swaps of array elements. First, call Quick Sort with the unsorted array, and then with the sorted array, display the two totals after each call, and display the sorted lists.
Explanation / Answer
main.cpp
#include <stdlib.h>
#include <fstream>
#include <string>
#include <algorithm>
#include <cstring>
#include <sstream>
#include <iostream>
#include <ctype.h>
#include "Algorithms.hpp"
#include "Utils.hpp"
// We need to initialize two static counters for recording the work
// done by the recursive sort algorithms.
int Algorithms::staticCompCounter = 0;
int Algorithms::staticSwapCounter = 0;
int main()
{
// Read in our dirty input text for cleaning
std::ifstream inputText("input.txt");
std::stringstream buffer;
buffer << inputText.rdbuf();
std::string buffString = buffer.str();
// Define the characters we want to strip, mostly non-letter punctuation
// Remember to escape quotation mark
char chars[] = ""-,.!;:{}_()? ";
// Loop over entire text for each unwanted character
for (unsigned int i = 0; i < strlen(chars); ++i)
{
// Iterate over every character in the text
for(unsigned int j = 0; j < buffString.length(); j++ )
{
// Check whether each character is an instance of
// the currently considered undesirable character
// Replace it with whitespace if it matches
if(buffString.at(j) == chars[i])
{
buffString.replace(j, 1, " ");
}
// If it doesn't match, try to convert it to lowercase
// Will do nothing if the operation is invalid
else if(buffString.at(j) != chars[i])
{
buffString.replace(j, 1, std::string(1, tolower(buffString.at(j))));
}
}
}
// Declare our array of valuable words
std::string unsortedWords[5000];
// Declare a string token for storing in our Words array
// Define the delimiter to split words by (" ")
// Define our initial start and end positions and a loop counter
// to stop us when we reach 5000 stored words
std::string token;
std::string delimiter = " ";
int startPos = 0;
unsigned int endPos = buffString.find(delimiter);
int i = 0;
// store 5000 words
while(endPos != std::string::npos && i < 5000) {
// Take a substring spanning from the previous endPosition to the next occurrence
// of the delimiter which endPos should already be set to, the second parameter is the
// the number of characters long the substring will be
token = buffString.substr(startPos, (endPos-startPos));
if(token.size() != 0 && token != "'")
{
// Store the word in our unsorted array
unsortedWords[i] = token;
// This counter stops the loop when we have 5000 words
i++;
}
// Set our next start position as directly after the end point found
// previously plus the length of the delimiter.
startPos = endPos + delimiter.length();
// Set the next end point to be the next occurrence of whitespace
endPos = buffString.find(delimiter, startPos);
}
Algorithms algs;
std::cout << "Running Insertion Sort on an unsorted array" << std::endl;
std::string * insertionArray = copyArray(unsortedWords, 5000);
algs.insertionSort(insertionArray, 5000);
algs.printReport(0,100);
std::cout << std::endl;
std::cout << "Running Insertion Sort on an already sorted array" << std::endl;
algs.insertionSort(insertionArray, 5000);
algs.printReport(0,100);
std::cout << std::endl;
std::cout << "Running Selection Sort on an unsorted array" << std::endl;
std::string * selectionArray = copyArray(unsortedWords, 5000);
std::string * selectSorted = algs.selectionSort(selectionArray, 5000);
algs.printReport(1,100);
std::cout << std::endl;
std::cout << "Running Selection Sort on an already sorted array" << std::endl;
algs.selectionSort(selectSorted, 5000);
algs.printReport(1,100);
std::cout << std::endl;
Algorithms::staticCompCounter = 0;
Algorithms::staticSwapCounter = 0;
std::cout << "Running Merge Sort on an unsorted array" << std::endl;
std::string * mergeArray = copyArray(unsortedWords, 5000);
mergeArray = algs.mergeSort(mergeArray, 5000);
algs.printReport(2, 100);
std::cout << std::endl;
//reset our static counters that monitor the recursive algorithms
// between successive runnings of the algs
Algorithms::staticCompCounter = 0;
Algorithms::staticSwapCounter = 0;
std::cout << "Running Merge Sort on an already sorted array" << std::endl;
mergeArray = algs.mergeSort(mergeArray, 5000);
algs.printReport(2, 100);
std::cout << std::endl;
Algorithms::staticCompCounter = 0;
Algorithms::staticSwapCounter = 0;
std::string * quickArray = copyArray(unsortedWords, 5000);
//printArray(quickArray, 5000);
std::cout << "Running Quick Sort on an unsorted array" << std::endl;
quickArray = algs.quickSort(quickArray, 0, 4999);
algs.printReport(3,100);
std::cout << std::endl;
Algorithms::staticCompCounter = 0;
Algorithms::staticSwapCounter = 0;
//printArray(quickArray, 5000);
std::cout << "Running Quick Sort on an already sorted array" << std::endl;
quickArray = algs.quickSort(quickArray, 0, 4999);
algs.printReport(3,100);
std::cout << std::endl;
std::string * unsortedWords5000 = copyArray(unsortedWords, 5000);
std::string * unsortedWords1000 = copyArray(unsortedWords, 1000);
std::string * unsortedWords100 = copyArray(unsortedWords, 100);
std::string * unsortedWords50 = copyArray(unsortedWords, 50);
std::string * unsortedWords10 = copyArray(unsortedWords, 10);
// 0pc Sorted Lists, size 5000 1000 100 50 10
int * unsorted5000longResults = runAllAlgs(unsortedWords5000, 5000);
int * unsorted1000longResults = runAllAlgs(unsortedWords1000, 1000);
int * unsorted100longResults = runAllAlgs(unsortedWords100, 100);
int * unsorted50longResults = runAllAlgs(unsortedWords50, 50);
int * unsorted10longResults = runAllAlgs(unsortedWords10, 10);
// 25pc Sorted Lists, size 5000 1000 100 50 10
std::string * semi25pc5000long = generate25pcSortedLists(unsortedWords5000, 5000);
std::string * semi25pc1000long = generate25pcSortedLists(unsortedWords1000, 1000);
std::string * semi25pc100long = generate25pcSortedLists(unsortedWords100, 100);
std::string * semi25pc50long = generate25pcSortedLists(unsortedWords50, 50);
std::string * semi25pc10long = generate25pcSortedLists(unsortedWords10, 10);
int * semi25pc5000longResults = runAllAlgs(semi25pc5000long, 5000);
int * semi25pc1000longResults = runAllAlgs(semi25pc1000long, 1000);
int * semi25pc100longResults = runAllAlgs(semi25pc100long, 100);
int * semi25pc50longResults = runAllAlgs(semi25pc50long, 50);
int * semi25pc10longResults = runAllAlgs(semi25pc10long, 10);
// 50pc Sorted Lists, size 5000 1000 100 50 10
std::string * semi50pc5000long = generate50pcSortedLists(unsortedWords5000, 5000);
std::string * semi50pc1000long = generate50pcSortedLists(unsortedWords1000, 1000);
std::string * semi50pc100long = generate50pcSortedLists(unsortedWords100, 100);
std::string * semi50pc50long = generate50pcSortedLists(unsortedWords50, 50);
std::string * semi50pc10long = generate50pcSortedLists(unsortedWords10, 10);
int * semi50pc5000longResults = runAllAlgs(semi50pc5000long, 5000);
int * semi50pc1000longResults = runAllAlgs(semi50pc1000long, 1000);
int * semi50pc100longResults = runAllAlgs(semi50pc100long, 100);
int * semi50pc10longResults = runAllAlgs(semi50pc10long, 10);
int * semi50pc50longResults = runAllAlgs(semi50pc50long, 50);
// 75pc Sorted Lists, size 5000 1000 100 50 10
std::string * semi75pc5000long = generate75pcSortedLists(unsortedWords5000, 5000);
std::string * semi75pc1000long = generate75pcSortedLists(unsortedWords1000, 1000);
std::string * semi75pc100long = generate75pcSortedLists(unsortedWords100, 100);
std::string * semi75pc50long = generate75pcSortedLists(unsortedWords50, 50);
std::string * semi75pc10long = generate75pcSortedLists(unsortedWords10, 10);
int * semi75pc5000longResults = runAllAlgs(semi75pc5000long, 5000);
int * semi75pc1000longResults = runAllAlgs(semi75pc1000long, 1000);
int * semi75pc100longResults = runAllAlgs(semi75pc100long, 100);
int * semi75pc50longResults = runAllAlgs(semi75pc50long, 50);
int * semi75pc10longResults = runAllAlgs(semi75pc10long, 10);
std::cout << "Results" << std::endl;
std::cout << std::setw(30) << "Insertion Sort" << std::setw(30) << "Selection Sort" <<std::setw(30) << "Merge Sort" <<std::setw(30) << "Quick Sort" << std::endl;
printArrayLine(unsorted5000longResults, 8);
printArrayLine(unsorted1000longResults, 8);
printArrayLine(unsorted100longResults, 8);
printArrayLine(unsorted50longResults, 8);
printArrayLine(unsorted10longResults, 8);
printArrayLine(semi25pc5000longResults, 8);
printArrayLine(semi25pc1000longResults, 8);
printArrayLine(semi25pc100longResults, 8);
printArrayLine(semi25pc50longResults, 8);
printArrayLine(semi25pc10longResults, 8);
printArrayLine(semi50pc5000longResults, 8);
printArrayLine(semi50pc1000longResults, 8);
printArrayLine(semi50pc100longResults, 8);
printArrayLine(semi50pc50longResults, 8);
printArrayLine(semi50pc10longResults, 8);
printArrayLine(semi75pc5000longResults, 8);
printArrayLine(semi75pc1000longResults, 8);
printArrayLine(semi75pc100longResults, 8);
printArrayLine(semi75pc50longResults, 8);
printArrayLine(semi75pc10longResults, 8);
delete[] unsortedWords5000;
delete[] unsortedWords1000;
delete[] unsortedWords100;
delete[] unsortedWords50;
delete[] unsortedWords10;
std::cout << "Finished" << std::endl;
}
Algorithms.hpp
#include <string>
#include <stdlib.h>
class Algorithms
{
private:
std::string * swapStrings (std::string * wordArray, int firstIndex, int secondIndex);
std::string * merge(std::string * left, std::string * right, int leftLength, int rightLength);
int partition(std::string * unsortedWords, int startIndex, int endIndex);
int pivot;
public:
void printReport (int algUsed, int percent);
std::string * insertionSort ( std::string * unsortedWords, int LengthArray);
std::string * selectionSort ( std::string * unsortedWords, int lengthArray);
std::string * mergeSort ( std::string * unsortedWords, int lengthArray);
std::string * quickSort ( std::string * unsortedWords, int startIndex, int endIndex);
int comparisonCounter;
int swapCounter;
static int staticCompCounter;
static int staticSwapCounter;
};
std::string * Algorithms::swapStrings(std::string * wordArray, int firstIndex, int secondIndex)
{
std::string temp;
temp = wordArray[firstIndex];
wordArray[firstIndex] = wordArray[secondIndex];
wordArray[secondIndex] = temp;
return wordArray;
}
void Algorithms::printReport( int algUsed, int percentUsed )
{
std::string alg;
switch(algUsed)
{
case 0: alg = " insertion";
std::cout << comparisonCounter << " comparisons made for a " << percentUsed << "% " << alg << " sort" << std::endl;
std::cout << swapCounter << " array element swaps made for a " << percentUsed << "% " << alg << " sort" << std::endl;
break;
case 1: alg= "selection";
std::cout << comparisonCounter << " comparisons made for a " << percentUsed << "% " << alg << " sort" << std::endl;
std::cout << swapCounter << " array element swaps made for a " << percentUsed << "% " << alg << " sort" << std::endl;
break;
case 2: alg = "merge";
std::cout << staticCompCounter << " comparisons made for a " << percentUsed << "% " << alg << " sort" << std::endl;
std::cout << staticSwapCounter << " array element swaps made for a " << percentUsed << "% " << alg << " sort" << std::endl;
break;
case 3: alg = "quick";
std::cout << staticCompCounter << " comparisons made for a " << percentUsed << "% " << alg << " sort" << std::endl;
std::cout << staticSwapCounter << " array element swaps made for a " << percentUsed << "% " << alg << " sort" << std::endl;
break;
}
}
std::string * Algorithms::insertionSort ( std::string * unsortedWords, int lengthArray)
{
comparisonCounter = 0;
swapCounter = 0;
int j;
for(int i = 1; i < lengthArray; i++)
{
j = i;
while( j > 0 && unsortedWords[ j - 1 ] > unsortedWords[j])
{
swapStrings(unsortedWords, j, j-1);
swapCounter++;
j--;
}
comparisonCounter++;
}
return unsortedWords;
}
std::string * Algorithms::selectionSort(std::string * unsortedWords, int lengthArray)
{
comparisonCounter = 0;
swapCounter = 0;
int i;
int j;
int jMin;
for(i = 0 ; i < lengthArray - 1; i++)
{
jMin = i;
for(j = i+1; j < lengthArray; j++)
{
if(unsortedWords[j] < unsortedWords[jMin])
{
jMin = j;
}
comparisonCounter++;
}
if(jMin != j)
{
swapStrings(unsortedWords, i, jMin);
swapCounter++;
}
//comparisonCounter++;
}
return unsortedWords;
}
std::string * Algorithms::mergeSort(std::string * unsortedWords, int lengthArray)
{
if(lengthArray <= 1)
{
return unsortedWords;
}
int leftLength = lengthArray/2;
std::string * left = new std::string[leftLength];
int rightLength = lengthArray - leftLength;
std::string * right = new std::string[rightLength];
int middle = leftLength;
for(int i = 0; i < middle; i++)
{
left[i] = unsortedWords[i];
}
for(int j = middle; j < lengthArray; j++)
{
right[j - middle] = unsortedWords[j];
}
left = mergeSort(left, middle);
right = mergeSort(right, lengthArray - middle);
return merge(left, right, leftLength, rightLength);
}
std::string * Algorithms::merge(std::string * left, std::string * right, int leftLength, int rightLength)
{
std::string * resultList = new std::string[leftLength + rightLength];
int l = 0;
int r = 0;
while(l < leftLength && r < rightLength)
{
if(left[l] <= right[r])
{
resultList[l+r] = left[l];
l++;
}
else
{
resultList[l+r] = right[r];
r++;
}
staticCompCounter++;
staticSwapCounter++;
}
while(l < leftLength)
{
resultList[l+r] = left[l];
l++;
staticSwapCounter++;
}
while(r < rightLength)
{
resultList[l+r] = right[r];
r++;
staticSwapCounter++;
}
return resultList;
}
std::string * Algorithms::quickSort(std::string * unsortedWords, int startIndex, int endIndex)
{
if(startIndex < endIndex)
{
pivot = partition(unsortedWords, startIndex, endIndex);
quickSort(unsortedWords, startIndex, pivot - 1);
quickSort(unsortedWords, pivot + 1, endIndex);
}
return unsortedWords;
}
int Algorithms::partition(std::string * unsortedWords, int startIndex, int endIndex)
{
// Halfway between startIndex and endIndex assuming binary splitting
int pivotIndex = (endIndex+startIndex)/2;
// Remember the string at the pivot we chose
std::string pivotValue = unsortedWords[pivotIndex];
// Swap the pivot with the end string
swapStrings(unsortedWords, pivotIndex, endIndex);
staticSwapCounter++;
int storeIndex = startIndex;
for(int i = startIndex; i < endIndex - 1; i++)
{
if(unsortedWords[i] < pivotValue)
{
swapStrings(unsortedWords, i, storeIndex);
storeIndex++;
staticSwapCounter++;
}
staticCompCounter++;
}
swapStrings(unsortedWords, storeIndex, endIndex);
staticSwapCounter++;
return storeIndex;
}
Utils.hpp
#include <iomanip>
void printArrayLine(int * intArray, int lengthArray)
{
for(int i = 0; i <lengthArray; i++)
{
std::cout << std::setw(15)<< intArray[i];
}
std::cout << std::endl;
}
void printArray(std::string * wordArray, int lengthArray)
{
for(int i = 0; i < lengthArray; i++)
{
std::cout << i << " : " << wordArray[i] << std::endl;
}
}
std::string * copyArray(std::string * wordArray, int lengthArray)
{
// We allocate the copied array on heap because we may not have enough room
// in this stack frame.
std::string * copyOfArray = new std::string[lengthArray];
//Straight copy from original array to the next
for(int x = 0; x < lengthArray; x++)
{
copyOfArray[x] = wordArray[x];
}
return copyOfArray;
}
std::string * generate75pcSortedLists(std::string * unsortedArray, int lengthArray)
{
Algorithms algs;
std::string * semisorted75pcWords = copyArray(unsortedArray, lengthArray);
semisorted75pcWords = algs.insertionSort(unsortedArray, (lengthArray * .75));
return semisorted75pcWords;
}
std::string * generate50pcSortedLists(std::string * unsortedArray, int lengthArray)
{
Algorithms algs;
std::string * semisorted50pcWords = copyArray(unsortedArray, lengthArray);
semisorted50pcWords = algs.insertionSort(unsortedArray, (lengthArray * .50));
return semisorted50pcWords;
}
std::string * generate25pcSortedLists(std::string * unsortedArray, int lengthArray)
{
Algorithms algs;
std::string * semisorted25pcWords = copyArray(unsortedArray, lengthArray);
semisorted25pcWords = algs.insertionSort(semisorted25pcWords, (lengthArray * .25));
return semisorted25pcWords;
}
int * runAllAlgs(std::string * inputArray, int lengthArray)
{
std::string * newArray = copyArray(inputArray, lengthArray);
Algorithms algs;
int * counterValues = new int[8];
algs.staticCompCounter = 0;
algs.staticSwapCounter = 0;
algs.comparisonCounter = 0;
algs.swapCounter = 0;
algs.insertionSort(newArray, lengthArray);
counterValues[0] = algs.comparisonCounter;
counterValues[1] = algs.swapCounter;
algs.comparisonCounter = 0;
algs.swapCounter = 0;
algs.selectionSort(newArray, lengthArray);
counterValues[2] = algs.comparisonCounter;
counterValues[3] = algs.swapCounter;
algs.comparisonCounter = 0;
algs.swapCounter = 0;
algs.staticCompCounter = 0;
algs.staticSwapCounter = 0;
algs.mergeSort(newArray, lengthArray);
counterValues[4] = algs.staticCompCounter;
counterValues[5] = algs.staticSwapCounter;
algs.staticCompCounter = 0;
algs.staticSwapCounter = 0;
algs.staticCompCounter = 0;
algs.staticSwapCounter = 0;
algs.quickSort(newArray, 0, (lengthArray -1));
counterValues[6] = algs.staticCompCounter;
counterValues[7] = algs.staticSwapCounter;
delete[] newArray;
return counterValues;
}
input.txt
And whereas the other so-called virtues of the soul seem to be akin to
bodily qualities, for even when they are not originally innate they can
be implanted later by habit and exercise, the virtue of wisdom more than
anything else contains a divine element which always remains, and by
this conversion is rendered useful and profitable; or, on the other
hand, hurtful and useless. Did you never observe the narrow intelligence
flashing from the keen eye of a clever rogue--how eager he is, how
clearly his paltry soul sees the way to his end; he is the reverse of
blind, but his keen eye-sight is forced into the service of evil, and he
is mischievous in proportion to his cleverness?
Very true, he said.
But what if there had been a circumcision of such natures in the days
of their youth; and they had been severed from those sensual pleasures,
such as eating and drinking, which, like leaden weights, were attached
to them at their birth, and which drag them down and turn the vision
of their souls upon the things that are below--if, I say, they had been
released from these impediments and turned in the opposite direction,
the very same faculty in them would have seen the truth as keenly as
they see what their eyes are turned to now.
output
Running Insertion Sort on an unsorted array
4999 comparisons made for a 100% insertion sort
6132124 array element swaps made for a 100% insertion sort
Running Insertion Sort on an already sorted array
4999 comparisons made for a 100% insertion sort
0 array element swaps made for a 100% insertion sort
Running Selection Sort on an unsorted array
12497500 comparisons made for a 100% selection sort
4999 array element swaps made for a 100% selection sort
Running Selection Sort on an already sorted array
12497500 comparisons made for a 100% selection sort
4999 array element swaps made for a 100% selection sort
Running Merge Sort on an unsorted array
55346 comparisons made for a 100% merge sort
61808 array element swaps made for a 100% merge sort
Running Merge Sort on an already sorted array
29804 comparisons made for a 100% merge sort
61808 array element swaps made for a 100% merge sort
Running Quick Sort on an unsorted array
231180 comparisons made for a 100% quick sort
31859 array element swaps made for a 100% quick sort
Running Quick Sort on an already sorted array
233412 comparisons made for a 100% quick sort
25796 array element swaps made for a 100% quick sort
Results
Insertion Sort Selection Sort Merge Sort Quick Sort
4999 6132124 12497500 4999 29804 61808 239331 25503
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.