Keskustelu: Koodit: C++: Shell-lajittelu algoritmi

Tässä on esimerkki shell-lajittelu algoritmista, joka tässä tapauksessa lajittelee taulukossa olevat numerot suuruus järjestykseen. Mutta perusidea on se, että kahta jonkin matkan päässä olevaa alkiota verrataan toisiinsa. Alussa välimatka on puolet alkioiden määrästä, ja joka kerta kun vertailu kierros on menty loppuun niin puolitetaan välimatka. lopulta vertailtavien alkioiden välimatka enää yksi, mutta tehtävien vaihtojen määrä on pienin mahdollinen joten algoritmikin on suhteellisen tehokas.

Algoritmin on kehittänyt Donald Shell v.1959

#include <iostream>
#include <conio.h>

using namespace std;

int luvut[6];
int maara;

void lue(int luvut[])
{
  int i;
  cout << "Anna alkioiden arvot\n";
  for(i=0;i<6;i++)
	{
          cout << "Anna luettelon "<< i <<". alkio\n";
          cin >> luvut[i];
	}
}

void vaihda(int* a,int* b)
{
  int temp;
  temp=*a;
  *a=*b;
  *b=temp;
}

void tulosta(int luvut[])
{
  int i;
  cout << "Luettelon alkiot:\n";
  for(i=0;i<6;i++)
  cout << "luettelon "<< i <<". alkio on: "<< luvut[i] << "\n";
}

void shell(int luvut[], int maara)
{
  int k, valimatka, vaihto=1;
  valimatka=(maara/2);
  do
  {
    do
    {
      vaihto=0;
      for(k=0;k<(maara-valimatka);k++)
      if(luvut[k] > luvut[k+valimatka])
      {
       vaihda(&(luvut[k]),&(luvut[k+valimatka]));
       vaihto=1;
      }
    }while (vaihto);
  }while((valimatka /= 2) > 0);
}


int main()
{
  lue(luvut);
  shell(luvut,6);
  tulosta(luvut);
  getch();
}

Shell-lajittelu on aika näppärä, kuitenkin paljon nopeampi kuin BubbleSort.

Varsin mojova.. tuota on vähän hankala laajentaa omiin tarkoitusperiin.. no, itse algoritmi on helppo, vain etsiä ja koodata, ja sen voisi paketoida nopiasti yhteen läjään..

Templaatit käyttöön (std::sort-tyyliin), swap-funktio käyttöön, conio.h pois, sitten voidaan palata asiaan. Kun C++ sisältää valmiiksi tehokkaan lajittelufunktion, koodivinkin pitäisi olla erityisen hyvin toteutettu ja selostettu, jotta sitä kestäisi katsella.