/* harjoitus 8 - tehtävä 5 */
#include <stdio.h>
#include "h8apu.h"

#define MAX_SIZE 1000

/* taulukoiden järjestämisen suorittaa sort funktio */
void sort(double data[], int size);

/* swap on apuna järjestämisessä */
void swap(double *a, double *b);

/* apufunktioita taulukoiden tulostamiseen ja lukemiseen */
int read_array(double *data, int size);
void print_array(double data[], int size);

main()
{
  double data[MAX_SIZE];
  int n;

  n = read_array(data, MAX_SIZE);
  sort(data, n);
  print_array(data, n);
}

/* SORTTAUS FUNKTIO *************************************************/

/* Algoritmin idea: Verrataan jokaista alkiota sitä edeltäneeseen
   alkioon, ja jos edellinen on suurempi kuin jälkimmäinen, alkioiden
   paikkaa vaihdetaan. Taulukko käydään toistuvasti näin läpi, kunnes
   yhdenkään alkioparin paikkaa ei ole tarvinnut vaihtaa.

   Tämä algoritmi tunnetaan nimellä 'bubble sort', koska alkiot
   nousevat paikoilleen kuin kuplat juomassa :-D. Katso exercise
   kansiosta 'bubblesort.gif' -- tiedostoon on tallennettu animaatio,
   jossa jokainen ruutu on erään sortattavan taulukon sisältö yhden
   taulukkoa järjestävän silmukan suorituksen jälkeen.
*/

void sort(double data[], int size)
{
  int j, changed;

  /* Muuttuja 'changed' kertoo, onko jonkin alkioparin järjestystä
     pitänyt muuttaa. Seuraavaa taulukkoa järjestävää do-silmukkaa
     tulee toistaa niin kauan kuin 'changed' on tosi (eli 1). */

  do {
    /* Aluksi 'changed' asetetaan epätodeksi (0), muutoksia ei
       ole ainakaan vielä tehty. */
    changed = 0;

    /* Käydään taulukko läpi - Koska silmukassa verrataan kutakin
       alkiota edelliseen, aloitetaan tällä kertaa toisesta alkiosta
       (indeksi = 1) */
    for (j = 1; j < size; j++) {
      /* verrataan kahta peräkkäistä alkiota: */
      if (data[j - 1] > data[j]) {
	/* edellinen alkio on suurempi kuin sitä seuraava;
	   vaihtakaamme siis alkioiden paikkaa, ja asetetaan taulukon
	   muuttumista ilmaiseva lippu 'changed' todeksi (1) */
	swap(&data[j - 1], &data[j]);	/* swap vaihtaa alkiot */
	changed = 1;
      }
    }
  } while (changed); /* silmukkaa siis toistetaan kunnes 'changed' on
		        jäänyt epätodeksi, ts. taulukkoa ei ole
		        tarvinnut enää muuttaa */

  /* Onneksi olkoon, taulukko on nyt järjestyksessä! */
}

/* swap apufunktio vaihtaa kahden muuttujan arvot päittäin */
void swap(double *a, double *b)
{
  double temp;
  temp = *a;
  *a = *b;
  *b = temp;
}

/* APUFUNKTIOT TAULUKOIDEN LUKEMISEEN JA TULOSTAMISEEN **************/

/* read_array lukee käyttäjältä lukuja kunnes luetaan EOF merkki --
   EOF ilmaisee tiedoston päättymistä, ja näppäimistöltä sen saa
   painamall Control-Z (UNIX ympäristöissä näppäinyhdistelmä on
   Control-D). Argumentti data on taulukko, johon syöte luetaan, ja
   size on taulukon maksimi koko. Paluuarvo on luettujen lukujen
   lukumäärä. */
int read_array(double *data, int size)
{
  double x;
  int i = 0;
  while (i < size && scanf("%lf", &data[i]) != EOF) i++;
  return (i);
}

/* print_array tulostaa taulukoita ruudulle. Argumentti data on
   tulostettava taulukko ja size sen koko */
void print_array(double data[], int size)
{
  int i;
  for (i = 0; i < size; i++) printf(" %10.4lf", data[i]);
  printf("\n");
}