Lab 05

// Matthew Felix
// CSE-100
// Spring 2020
// 3.12.2020

#include <iostream>
#include <vector>
using namespace std;

void printVector(vector<int>* v1, int n) {
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < 10; j++)
        {
            cout << v1[i][j] << ";";
        }
        cout << endl;
    }
}

//used pseudocode from the slides

void countingSort(vector<int>* v1, int n, int i) {
    //create a vector v2 with n size
    //using pointers

    vector<int>* v2;
    v2 = new vector<int>[n];

    //array of length 10, all values are 0

    int* arr = new int[10];

    for (int z = 0; z < 10; z++) {
        arr[z] = 0;
    }

    //pseudocode from lecture slides
    for (int j = 0; j < n; j++) {
        arr[v1[j][i]] = arr[v1[j][i]] + 1;
    }

    for (int j = 1; j < 10; j++) {
        arr[j] = arr[j] + arr[j - 1];
    }

    for (int j = n - 1; j >= 0; j--) {
        v2[arr[v1[j][i]] - 1] = v1[j];
        arr[v1[j][i]] = arr[v1[j][i]] - 1;
    }

    for (int i = 0; i < n; i++)
    {
        v1[i] = v2[i];
    }

}

//radix sorting
void radixSort(vector<int>* v1, int n) {
    for (int i = 9; i >= 0; i--)
    {
        countingSort(v1, n, i);
    }
}

int main()
{
    // get user input
    int n;
    cin >> n;

    //pointers to set the vector size
    vector<int>* v1;
    v1 = new vector<int>[n];

    //get user inputs
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < 10; j++) {
            int values;
            cin >> values;
            v1[i].push_back(values);
        }
    }

    //radix sort
    radixSort(v1, n);

    //print the sorted vectors
    printVector(v1, n);

    return 0;
}