Prevođenje u C program

Prevedimo sada program iz paskalolikog jezika (za koji smo dokazali totalnu korektnost), u C program vodeći računa da pri tome ne narušimo invarijante petlji i korektnost programa.

Primetimo da u dosadašnjem opisu algoritma i dokazu njegove korektnosti nije bilo reči o tipu elemenata niza već je samo pretpostavljano da se oni mogu porediti. U nastavku navedimo implementaciju algoritma prilagođenu nizovima celih brojeva:

main()
{   
    int X[]={2, 5, 1, 6};   
    unsigned int n = sizeof(X)/sizeof(int);
    unsigned int i, j;
    int pom;

    for(i=0; i <= n-2; i++)
       for(j=i+1; j<= n-1; j++)
          if(X[i] > X[j])
          {
             pom = X[i];
             X[i] = X[j];
             X[j] = pom; 
          }
}

Obezbedimo unos niza sa ulaza i ispis rezultata na izlaz:

#include<stdio.h>
#define MAX_DIM 100

main()
{
    unsigned int n;
    unsigned int i, j;
    int pom;
    int X[MAX_DIM];

    printf("Unesite dimenziju niza koji zelite da sortirate:\n");   
    scanf("%d", &n);
    while(n>MAX_DIM)
    {
      printf("Uneli ste preveliku dimenziju. Pokusajte ponovo:\n");
      scanf("%d", &n);    
    }
    for(i=0; i<n; i++)
    {
      printf("Unesite %d-ti element niza:\n", i);
      scanf("%d", &X[i]);
    }

    for(i=0; i <= n-2; i++)
       for(j=i+1; j <= n-1; j++)
          if(X[i] > X[j])
          {
             pom = X[i];
             X[i] = X[j];
             X[j] = pom;   
          }
    printf("Niz sortiran u rastucem redosledu je:\n");
    for(i=0; i<n; i++)
    {
      printf("%d ", X[i]);      
    }
}

Na ovaj način smo došli do programa koji sortira niz celih brojeva. Pri tome, znamo da se on uvek zaustavlja i da je korektan za sve moguće ulaze.

Navedeni algoritam i odgovarajuća implementacija može se jednostavno unaprediti. Umesto da se zamena elemenata vrši kao što je opisano, dovoljno je odrediti indeks najmanjeg elementa u tekućem podnizu i zatim izvršiti zamenu sa prvim elementom tog podniza. Time će biti smanjen broj izvršenih zamena u odnosu na osnovni algoritam.

Naredna: Korisni linkovi i materijali Gore: Selection sort Prethodna: Dokaz zaustavljanja programa   Sadržaj