/* *********************************************************
KUPLA.CPP
  Järjestää taulukon kuplalajittelulla.
********************************************************* */

#include <iostream.h>

#define KOKO 10

/* Alkioiden vertailufunktio. Palauttaa
   -1, jos a:n pitäisi olla ennen b:tä,
    0, jos a ja b ovat samanarvoiset,
   +1, jos a:n pitäisi olla b:n jälkeen. */
int vertaa(int a, int b)
{
  return (a - b);
}

/* Alkioiden vaihtofunktio. */
void vaihda(int &a, int &b)
{
  int apu;

  apu = a;
  a = b;
  b = apu;
}

/* Siirtää taulukon "painavimman" alkion viimeiseen paikkaan. */
void siirra_painavin(int taulukko[], int koko)
{
  int i, vertailu;

  /* käydään läpi koko taulukko ja verrataan peräkkäisiä alkioita */
  for (i=0; i<koko-1; i++) {
    /* alkion i pitäisi olla ennen alkiota i+1;
       jos väärässä järjestyksessä, vaihdetaan */
    vertailu = vertaa(taulukko[i], taulukko[i+1]);
    if (vertailu > 0)
      vaihda(taulukko[i], taulukko[i+1]);
  }
  /* nyt kaikkein painavin alkio on paikassa koko-1 */
}

/* Kuplalajittelu kokonaislukutaulukolle. */
void jarjesta(int taulukko[], int koko)
{
  int pituus; // taulukon käsiteltävän osan pituus

  /* taulukon käsiteltävä osa lyhenee yhdellä joka kierroksella */
  for (pituus=koko; pituus>1; pituus--)
    siirra_painavin(taulukko, pituus); // käsitellään osataulukko
}

void tulosta(int taulukko[], int koko)
{
  int i;

  for (i=0; i<koko; i++)
    cout << "  " << taulukko[i];
  cout << endl;
}

int main(void)
{
  int taulu[KOKO] = {4, 7, 1, 9, 3, 0, 2, 5, 8, 6};

  cout << "Alkuperäinen:";
  tulosta(taulu, KOKO);

  jarjesta(taulu, KOKO);

  cout << "Järjestetty :";
  tulosta(taulu, KOKO);

  return 0;
}