Beszúró rendezés bináris kereséssel

A beszúró rendezés bináris kereséssel a beszúró rendezés egy változata. Kihasználva, hogy már rendezett tömbbe szúr bele, az újabb elem helyét bináris kereséssel találja meg.

Működése

Az adattömb, amibe rendezünk, mindenkor rendezett állapotban van, és ezt a beszúró algoritmus figyelembe veszi. A beszúrás helyét bináris(logaritmikus) kereséssel határozzuk meg, majd beszúrjuk az új elemet.

Az algoritmus c++ kódja:

#include <vector>

template<class BASE>
typename std::vector<BASE>::iterator insert_sort( std::vector<BASE> &base, const BASE &element )
{
    std::vector<BASE>::size_type lower = 0, number = base.size();
    while(number >0) { // binary search the position
        std::vector<BASE>::size_type offset = (number - 1) >> 1; // half point
        if( base[lower+offset] < element ) { // go to upper half
            lower += offset+1;
            number -= offset+1;
        }
        else { // go to lower half
            number = offset;
        }
    }
    return base.insert( base.begin()+lower, element);
}

A BASE alaposztályban léteznie kell a < összehasonlító operátornak.
Példa a fenti kód alkalmazására:

std::vector<int> v;
int input[]={3,0,5,1,8,-1,7,2,6,11,-2,4,10,9,3,0,5,1};
for(int idx=0; idx<sizeof(input)/sizeof(int); idx++)
    insert_sort(v,input[idx]);

Rendezetlen adattömb rendezése esetén új adattömböt hozunk létre a régiből:

template<class BASE>
void insert_sort( std::vector<BASE> &input, std::vector<BASE> &output )
{
   output.clear();
   while( input.size() ) {
      insert_sort( output, input.back() );
      input.pop_back();
   }
}

Ha eleve rendezett adatbázist kívánunk hosszabb időn keresztül kezelni, akkor nem használhatunk tetszőleges rendezést új elem beszúrásánál. Más rendezések nem veszik figyelembe az adatbázis rendezettségét, teljes rendezést hajtanak végre, és emiatt nagyon rosszul teljesítenek, az elemcseréikkel megbontják a már meglevő rendet. Ilyenkor csak a beszúrásos rendezés használható. A lineáris végigkeresés azonban hosszadalmas, sokkal hatékonyabb a bináris keresés. Nagyobb adatbázisoknál azonban sok esetben több rendezési szempontot is figyelembe kell venni, ilyenkor nem az adatbázist rendezzük, hanem indexelt adatbázist használunk, vagyis minden rendezési szemponthoz egy-egy az adatbázis méretének megfelelő indextömböt hozunk létre, amelyben az adatbázis elemeinek indexeit helyezzük el a kívánt sorrendben.