How do I implement a library sort algorithm using STL containers?

Question

I'm trying to implement this sorting algorithm: http://en.wikipedia.org/wiki/Library_sort. I have some functions grupBul for finding suitable group, grupSirala for sort every group. I have to leave some gaps and contain them in a vector another data structure.

How can I perform this? So far I have this code:

#include "librarySort.h"
#include <iostream>
#include <vector>
#include <math.h>
#include "sort.h"
using namespace std;

#define EPSILON 10 //Epsilon sabiti
#define GRUPDEFBOYUT 20 //Gruplarin baslangiç boyutu

//gruplar[grupno][degerler] grupboyutu->[0] minimumeleman->[1] maksimumeleman->[2]
vector<vector<int> > gruplar;

int grupBul(vector<int*> &dizi,int sayi){
    for(int i=0;i<gruplar.size();i++){
        if(*dizi[gruplar[i][1]]<sayi && *dizi[gruplar[i][2]]>sayi){
            return gruplar[i][2];
        }
    }

    for(int i=gruplar.size()-1;i>=0;i--){
        if (*dizi[gruplar[i][2]]<sayi){
            return gruplar[i][2];
        }
    }
    if(*dizi[gruplar[0][1]]>=sayi){
        return gruplar[0][2];
    }
}

int maxBul(vector<int*> &dizi,int baslangic,int son){
    int max=*dizi[baslangic];
    int index=baslangic;
    for(int i=baslangic+1;i<son;i++){
        if(*dizi[i]>max){
            max=*dizi[i];
            index=i;
        }
    }

    return index;
}

int minBul(vector<int*> &dizi,int baslangic,int son){
    int min=*dizi[baslangic];
    int index=baslangic;
    for(int i=baslangic+1;i<son;i++){
        if(*dizi[i]<min){
            min=*dizi[i];
            index=i;
        }
    }

    return index;
}

void ilkGruplariOlustur(vector<int*> &dizi,int son){
    int grupboyut=0;
    int grupno=0;
    for(int i=0;i<5;i++){
        vector<int> grup;

        grup.push_back(GRUPDEFBOYUT);
        grup.push_back(minBul(dizi,grupboyut,GRUPDEFBOYUT+grupboyut));
        grup.push_back(maxBul(dizi,grupboyut,GRUPDEFBOYUT+grupboyut));

        gruplar.push_back(grup);

        /*for(int j=0;j<EPSILON;j++)
            dizi.push_back(NULL);*/
        grupboyut+=GRUPDEFBOYUT;
        grupno++;
    }
}

void grupSirala(vector<int*> &dizi,int baslangic,int son){
    int j = 0;
    int mover;

    for ( int i = baslangic + 1 ; i < son ; i++ ) {
        mover = *dizi[i];
        j = i-1;

        while ( ( j >= 0 ) && ( *dizi[j] > mover) ){
            *dizi[j+1] = *dizi[j];
            j--;
        }
        *dizi[j+1] = mover;
    }
}

void bosluklariOlustur(vector<int*> &dizi){
}

int librarySort( int *data , unsigned int size) {
    int kok_n=(int)sqrt((double)size);
    int boyut=size;

    vector<int*> sirali_dizi;

    for(int i=0;i<kok_n;i++){
        sirali_dizi.push_back(new int(*(data+i)));
    }

    ilkGruplariOlustur(sirali_dizi,0);
    for(int i=0;i<sirali_dizi.size();i++)
        cout << *sirali_dizi.at(i)<< " ";

    for(int a = 0;a<10;a++)
        sirali_dizi.push_back(NULL);
    grupSirala(sirali_dizi,0,kok_n);

    for(int i=0;i<5;i++){
        for(int j=0;j<3;j++)
            cout << gruplar[i][j] << " ";
    }
    /*
    cout<<endl<<"Sirali dizi"+i<<endl;
    for(int t=0;t<20*(i+1)+EPSILON;t++)
        cout << *sirali_dizi.at(t)<< " ";
    cout<<endl;
    }
    cout<<endl;
    cout<<endl;
    cout<<endl;

    grupSirala(sirali_dizi,0,sirali_dizi.size());*/
    for(int i=0;i<sirali_dizi.size();i++)
        cout << *sirali_dizi.at(i)<< " ";

    return 0;
}

Answer 1

Well, vector has a resize method that will allow you to basically preset the vector's size before inserting data. Then from there you'll be able to use the operator[] to insert data at the appropriate spaces.

As a side note, I personally would not use STL if I'm working on this project/homework.