mardi 30 janvier 2018

Comparisons in Multiple Sorting Algorithms

Currently this program will generate 10 random numbers and either sort (from least to greatest), reverse sort, or shuffle them. However, when trying to list the number of comparisons made, the number of comparisons printed out are completely incorrect. For example, it prints that there were 44 comparisons with bubble sort (this is the one that varies every time but is usually around 40), 45 with selection sort, and 9 with insertion sort. For now I'm only running the program with numbersSorted() just to make sure the comparisons work. How can I print the correct number of comparisons made with each sorting method?

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int count1 = 0; //bubble
int count2 = 0; //selection
int count3 = 0; //insertion

vector<int> numbersSorted(int n);
vector<int> numbersReversed(int n);
vector<int> numbersShuffled(int n);

int main() {
srand(time(0));



    numbersSorted(10);
  //numbersReversed(10);
  //numbersShuffled(10);


return 0;
}

vector<int> numbersSorted(int n)
{

vector <int> v(n);

for (auto &x : v)
    x = rand() % 100;

cout << "Original list to be sorted: ";
for (auto x : v)
    cout  << x << " ";
cout << "\n\n";

// bubble sort
bool swapped = true;
for (int pass = 0; pass <= n - 2 && swapped; ++pass)
{
    swapped = false;
    for (int i = 0; i <= n - pass - 2; ++i)
    {
        ++count1;
        if (v.at(i) > v.at(i + 1))
        {
            swap(v[i], v[i + 1]);
            swapped = true;
        }
    }
}
cout << "Bubble sort sorted: ";
for (auto x : v)
    cout << x << " ";
cout << "\n";
cout << "There were " << count1 << " comparisons with bubble sort.\n" << 
endl;

// selection sort
for (int pass = 0; pass <= n - 2; ++pass)
{
    // Find least element remaining in the list starting at index pass
    int minIndex = pass;
    // i = minIndex + 1, minIndex + 1, ..., n - 1
    for (int i = minIndex + 1; i < n; i++)
    {
        ++count2;

        if (v[i] < v[minIndex])
        {
            minIndex = i;

        }
            // The element at index i is smaller than what I thought was the 
min
    }

    swap(v[pass], v[minIndex]);
}
cout << "Selection sort sorted: ";
for (auto x : v)
    cout << x << " ";
cout << "\n";
cout << "There were " << count2 << " comparisons with selection sort.\n" << 
endl;


//insertion sort
for (int pass = 0; pass <= n - 2; ++pass) {
    // Take the element at pass+1 and move it to the left until it's in the
    // right spot (i.e., as long as it's in the wrong spot).

    // for i = pass, pass-1, ..., 0 while L[i] > L[i+1]
    ++count3;
    for (int i = pass; i >= 0 && v[i] > v[i + 1]; --i) {
        swap(v[i], v[i + 1]);
    }
}
cout << "Insertion sort sorted: ";
for (auto x : v)
    cout << x << " ";
cout << "\n";
cout << "There were " << count3 << " comparisons with insertion sort.\n" << 
endl;
//return v;
}
vector<int> numbersReversed(int n)
{
vector <int> v(n);

for (auto &x : v)
    x = rand() % 100;

cout << "Original list to be reversed: ";
for (auto x : v)
    cout << x << " ";
cout << "\n\n";


// bubble sort
bool swapped = true;
for (int pass = 0; pass <= n - 2 && swapped; ++pass)
{
    swapped = false;
    for (int i = 0; i <= n - pass - 2; ++i)
    {
        ++count1;
        if (v.at(i) > v.at(i + 1))
        {
            swap(v[i], v[i + 1]);
            swapped = true;
        }
    }
}

//reverse the content of the vector
reverse(v.begin(),v.end());

cout << "Bubble sort reversed: ";
for (auto x : v)
    cout << x << " ";
cout << "\n";
cout << "There were " << count1 << " comparisons with bubble sort.\n" << 
endl;


// selection sort
for (int pass = 0; pass <= n - 2; ++pass)
{
    // Find least element remaining in the list starting at index pass
    int minIndex = pass;
    // i = minIndex + 1, minIndex + 1, ..., n - 1
    for (int i = minIndex + 1; i < n; i++)
    {
        ++count2;
        if (v[i] < v[minIndex])
            // The element at index i is smaller than what I thought was the 
min
            minIndex = i;
    }

    swap(v[pass], v[minIndex]);
}

reverse(v.begin(),v.end());

cout << "Selection sort reversed: ";
for (auto x : v)
    cout << x << " ";
cout << "\n";
cout << "There were " << count2 << " comparisons with selection sort.\n" << 
endl;



// insertion sort
for (int pass = 0; pass <= n - 2; ++pass) {
    // Take the element at pass+1 and move it to the left until it's in the
    // right spot (i.e., as long as it's in the wrong spot).

    // for i = pass, pass-1, ..., 0 while L[i] > L[i+1]
    ++count3;
    for (int i = pass; i >= 0 && v[i] > v[i + 1]; --i) {
        swap(v[i], v[i + 1]);
    }
}

reverse(v.begin(),v.end());
cout << "Insertion sort reversed: ";
for (auto x : v)
    cout << x << " ";
cout << "\n";
cout << "There were " << count3 << " comparisons with insertion sort.\n" << 
endl;

}

vector<int> numbersShuffled(int n)
{
vector<int> v(n);

for (auto &x : v)
{
    x = rand() % 100;
    ++count1;
}


cout << "Numbers Shuffled: ";
for (auto x : v)
    cout << x << " ";
cout << "\n";
cout << "There were " << count1 << " comparisons made. " << endl;
}




Aucun commentaire:

Enregistrer un commentaire