2009-08-10

Counting sort буюу Тоолж жагсаах алгоритм

Энэ адилтгах програмыг харж байгаад Тоолж жагсаах алгоритмыг бичлээ.
#include 

using namespace std;

void countingsort(int *from, int *to, int size) {

    int bound;

    //calculate the bound
    bound = from[0];
    for(int i=1; i < size; i++) {
        if(bound < from[i]) bound = from[i];
    }
    bound = bound+1;

    // counting elements to temporary array
    // of bound length
    int *tmp = new int[bound];
    for (int i=0; i < bound; i++) {
        tmp[i] = 0;
    }
    for (int i=0; i < size; i++) {
        tmp[from[i]]++;
    }

    // processing temporary array
    for (int i=1; i < bound; i++) {
        tmp[i] += tmp[i-1];
    }

    // moving elements to final array
    for (int i=0; i < size; i++) {
        tmp[from[i]]--;
        to[tmp[from[i]]] = from[i];
    }

    delete tmp;
}

int main() {
    int from[8] = {0,4,5,0,3,4,9,4};
    int to[8] = {0};

    cout << "The initial array is: " << endl;
    for(int i=0; i < 8; i++) {
        cout << from[i] << " ";
    }
    cout << endl;

    countingsort(from, to, 8);

    cout << "The final array is: " << endl;
    for(int i=0; i < 8; i++) {
        cout << to[i] << " ";
    }
    cout << endl;

    system("PAUSE");
    return 0;
}

No comments:

Post a Comment