Metode de sortare – sortare ordinara

Cel mai simplu algoritm de sortare (dar şi cel mai ineficient) se bazează pe următorul principiu: un şir este sortat dacă prin parcurgerea lui de la început până la sfârşit, fiecare element este mai mic decât succesorul. Dacă această condiţie nu este îndeplinită, inversăm cele 2 elemente. Sortarea se încheie în momentul în care parcurgerea şirului se face fără a fi necesară nici o inversare (fiecare element este mai mic decât succesorul său).

3 7 <=> 4 9 2 8 i=1; inversam a[1]=7 cu a[2]=4; k=1
3 4 7 9 <=> 2 8 i=3; inversam a[3]=9 cu a[4]=2; k=1
3 7 4 2 9 <=> 8 i=4; inversam a[4]=9 cu a[5]=8; k=1
3 7 <=> 4 2 8 9 k<>0 deci pornim un nou ciclu; i=1 inversam a[1]=7 cu a[2]=4; k=1
3 4 7 <=> 2 8 9 i=2; inversam a[2]=7 cu a[3]=2; k=1
3 4 <=> 2 7 8 9 k<>0 deci pornim un nou ciclu; i=1 inversam a[1]=4 cu a[2]=2; k=1
3 <=> 2 4 7 8 9 k<>0 deci pornim un nou ciclu; i=0 inversam a[0]=3 cu a[1]=2; k=1
2 3 4 7 8 9 k ramane 0 (nu facem nici o inversare) deci şirul este sortat


#include "stdio.h"
#include "conio.h"
void sortare_ordinara(int a[], int n)
{
  int i,j,k,elem;
  do
  {
    for(i=0,k=0;i < n-i;i++)
    //la fiecare început de parcurgere a şirului, k este iniţializat cu 0
    if(a[i] > a[i+1])
    //dacă elementul curent este mai mare decât succesorul este
    //necesară inversarea lor;
    //atenţie: dacă punem mai mare sau egal şi avem 2 elemente egale, vom
    //ajunge la ciclu infinit
    {
      elem=a[i];
      a[i]=a[i+1];
      a[i+1]=elem;
      k=1;
      //k diferit de o indică faptul că s-a făcut o inversare
    }
  } while(k);
  //sortarea se încheie în momentul în care k a rămas 0
  //(deci nu s-a făcut nici o inversare de elemente)
}

void main(void)
{
  int n,a[100],i;
  printf("Introdu dim şirului:");
  scanf("%d",&n);
  printf("Introdu elem sirului:\n");
  for(i=0;i < n;i++)   {     printf("a[%d]=",i);     scanf("%d",a+i);   }   sortare_ordinara(a,n);   printf("Sirul sortat este:");   for(i=0;i < n;i++) printf("%d ",a[i]);   putchar("\n");   getch(); }

Leave a Reply

Your email address will not be published. Required fields are marked *

17 − 14 =

Time limit is exhausted. Please reload CAPTCHA.