Metode de sortare – prin selectie (Selection sort)

Principiul acestei metode este următorul: şirul este împărţit în 2 părţi: o “Parte stânga” sortată şi o “Parte dreapta” nesortată. Iniţial “Partea stângă” este vidă iar “Partea dreapta” conţine tot şirul. Se caută minimul din “Partea dreapta” şi se adaugă la sfârşitul “Părţii stânga”. Algoritmul se încheie în momentul în care “Partea dreaptă” mai conţine un singur element. Acest ultim element este maximul din şir deci, în final, “Partea stânga” va conţine toate elementele şirului sortate, iar “Partea dreapta” devine vidă.

| = pozitia la care suntem
| 3 7 4 9 2 8 (alegem 3 si 2) Minimul este 2; acesta este adus pe poziţia 0
2 | 7 4 9 3 8 (alegem 3 si 7) Minimul este 3; acesta este adus pe poziţia 1
2 3 | 4 9 7 8 (alegem 4) Minimul este 4; acesta ramane pe poziţia 2
2 3 4 | 9 7 8 (alegem 9 si 7) Minimul este 7; acesta este adus pe poziţia 3
2 3 4 7 | 9 8 (alegem 9 si 8) Minimul este 8; acesta este adus pe poziţia 4
2 3 4 7 8 | 9 Partea dreapta conţine un singur element; algoritmul se opreşte
2 3 4 7 8 9 | Sirul este sortat


#include "stdio.h"
#include "conio.h"
void selectie(int a[], int n)
{
  int i,j,k,min;
  for(i=0;i < n-1;i++)
  //pentru toate elementele de la primul la penultimul
  {
    k=i;min=a[i];
    //alegem a[i] drept minim iniţial
    for(j=i+1;j < n; j++)       if(a[j] < min) k=j,min=a[j];     //dacă găsim un element mai mic, acesta va fi noul minim     a[k]=a[i];     a[i]=min;     //înlocuim elementul de pe poziţia i cu minimul găsit   } } void main(void) {   int n,a[100],i,j,k,min;   printf("Introdu dim şirului:");   scanf("%d",&n);   printf("Introdu elem şirului:\n");   for(i=0;i < n;i++)   {     printf("a[%d]= ",i);     scanf("%d",a+i);   }   selectie(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 *

seventeen + 20 =

Time limit is exhausted. Please reload CAPTCHA.