Need algorithm help #include <iostream> #include <stdlib.h> #include <string> us

Question

Need algorithm help

#include <iostream>
#include <stdlib.h>
#include <string>

using namespace std;

void MyFunc ( int *array ) {
// ...
}

int main(int argc,char **argv) {

int *Sequence;
int arraySize;

// Get the size of the sequence
cin >> arraySize;

// Allocate enough memory to store "arraySize" integers
Sequence = new int[arraySize];
  
// Read in the sequence
for ( int i=0; i<arraySize; i++ )
cin >> Sequence[i];

// Run your algorithms to manipulate the elements in Sequence
MyFunc(Sequence);
  
// Output the result
for(int i=0; i<arraySize; i++)
cout << Sequence[i] << endl;
  
// Free allocated space
delete[] Sequence;
}

Input structure You are going to apply Radix-Sort to sort vectors. The input starts with an integer number which indicates the number of vectors to be sorted. Then vectors follow, one vector per line. Each vector consists of 10 digits where each digit has a value in 0...9. Entries of a vector are separated by a space. Output structure Output the sorted sequence of vectors, one per line. Vector i must appear before vector j in your output if and only if for some d {1,2,... , 101, vector i is smaller than or equal to vector j on the dth entry, and the two vectors are equal for any of the first d -.1 entries Examples of input and output Input 3 3 3 3 3 2 2 2 2 2 2 3 2 2 2 2 2 2 2 2 1 300 210000 1 3002 2 000 0 2 3 2 1 2 2 2 2 2 2 Output 1;3;0;0;2;1;0;0;0;0; 1;3;0;0;2;2;0;0;0;0; 2;3;2;1;2;2;2;2;2;2;

Explanation / Answer

#include <iostream>
#include <vector>
#include <algorithm> // Required
#include <iterator> // Required
#include <queue> // Required
using namespace std;
// Radix Sort using base-10 radix
template <typename InputIterator, typename OutputIterator> void radixSort(InputIterator start, InputIterator end, OutputIterator output){
    const int BASE = 10; // Base
    std::queue< typename std::iterator_traits<OutputIterator>::value_type > bucket[BASE]; // An array of buckets based on the base
    
    unsigned size = end - start;
    // Get the maximum number
    typename std::iterator_traits<InputIterator>::value_type max = *std::max_element(start, end); // O(n)
    
    // Copy from input to output
    std::copy(start, end, output); // O(n)
    
    // Iterative Radix Sort - if k is log BASE (max), then the complexity is O( k * n)
    for (unsigned power = 1; max != 0; max /= BASE, power*=BASE){ // If BASE was 2, can use shift. Although compiler should be smart enough to optimise this.
        
        // Assign to buckets
        for (OutputIterator it = output; it != output+size; it++){
            unsigned bucketNumber = (unsigned) ( (*it/power) % BASE );
            bucket[bucketNumber].push(*it); // O(1)
        }
        
        // Re-assemble
        OutputIterator it = output;
        for (int i = 0; i < BASE; i++){
            int bucketSize = bucket[i].size();
            for (int j = 0; j < bucketSize; j++){
                *it = bucket[i].front();
                bucket[i].pop();
                it++;
            }
        }
    }
}

int main(){
    // This is C++11 syntax
    // Input must be unsigned
    vector<unsigned> input = {5,

3,3,3,3,3,2,2,2,2,2

,2,3,2,2,2,2,2,2,2,2

,1,3,0,0,2,1,0,0,0,0

1,3,0,0,2,2,0,0,0,0

,2,3,2,1,2,2,2,2,2,2};
    vector<unsigned> output(input.size());
    radixSort(input.begin(), input.end(), output.begin());
    
    // C++11 ranged based for loops
    // http://www.cprogramming.com/c++11/c++11-ranged-for-loop.html
    for (unsigned it : output){
        cout << it << endl;
    }
    return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.