selection [Algoritmi si Tehnici de Programare] Sortare Prin Selectie

[NEFERPITOU]

** Ce reprezinta si importanta procedeului de sortare **

Sortarea , a unei colectii , reprezinta procedeul prin care accesam si modificam POZITIA elementelor asociate acesteia , pe baza unui criteriu . De exemplu , putem ordona de la mic la mare (intr-o colectie de numere), de la A la Z (intr-o colectie de siruri de caractere)  etc.  

Sortarea se poate efectua sub mai multe procedee , unul mai optim decat altu din punct de vedere , a timpului de executie si a resurselor alocate .  

Nota ** :  Definim colectie orice entitate care contine o multime de elemente (array,lista,arbore etc.) ; 

** In ce Consta Sortarea Prin Selectie **

Sortarea Prin Selectie se bazeaza pe doua bucle , una care acceseaza toate elementele colectiei  iar cealalta , in interiorul acesteia , care compara repetitiv un element cu restul . Daca in comparatie, se gaseste un element mai mic acesta , se va efectua o interschimbare intre acestia. 

** Exemplu Selectie prin Sortare **

Sa presupunem ca avem 6 numere naturale intr o colectie 

        [44 , 22, 67, 23 , 21, 11]  --> NUMERE NATURALE 
        [0  , 1 , 2 , 3  , 4 , 5 ]  --> INDECSI 
        
EFECTUAM O SORTARE A COLECTIEI DE LA MARE LA MIC : 

Prima Iteratie : i = 0 ; 

   1. 44 > 22 --> 44 mai mare decat 22 --> nu efectuam nimc --> continuam ; 
   2. 44 < 67 --> 44 mai mic  decat 67 --> efectuam interschimbarea -->  [67 , 22 , 44 , 23 , 21 , 11] ;
   3. 67 > 23 --> 67 mai mare decat 23 --> nu efectuam nimc --> continuam ; 
   4. 67 > 21 --> 67 mai mare decat 21 --> nu efectuam nimic --> continuam ;
   5. 67 > 11 --> 67 mai mare decat 11 --> nu efectuam nimic --> continuam .
   
A doua iteratie : i = 1 ;

   1. 22 < 44 --> 22 mai mic  decat 44 --> efectuam interschimbarea -->  [67 , 44 , 22 , 23 , 21 , 11] ;
   2. 44 > 23 --> 44 mai mare decat 23 --> nu efectuam nimc --> continuam ;
   3. 44 > 21 --> 44 mai mare decat 21 --> nu efectuam nimc --> continuam ;
   4. 44 > 11 --> 44 mai mare decat 11 --> nu efectuam nimc --> continuam .
   
A treia iteratie : i = 2 ; 
  
   1. 22 < 23 --> 22 mai mic decat 23 --> efectuam interschimbarea -->  [67, 44 , 23 , 22 , 21 , 11] ;
   2. 23 > 21 --> 23 mai mare decat 21 --> nu efectuam nimc --> continuam ;
   3. 23 > 11 --> 23 mai mare decat 11 --> nu efectuam nimc --> continuam .
   
 A patra iteratie : i = 3 ; 
  
   1. 22 > 21 --> 23 mai mare decat 21 --> nu efectuam nimc --> continuam ; 
   2. 22 > 11 --> 22 mai mare decat 11 --> nu efectuam nimic --> continuam .
   
 A cincea iteratie : i = 4 ; 
  
   1. 21 > 11 --> 21 mai mare decat 11 --> nu efectuam nimic --> continuam .
   
 FINAL ALGORITM  
 
 Algoritmul sortat de la mare la mic : [67, 44 , 23 , 22 , 21 , 11]
 
 NOTA ** : Pentru la mic la mare , doar inversam comparatia !!! Procedeul e acelasi !! 
 
   

** Algoritm in C ** 

#include <stdio.h>
#include <stdlib.h> // Pentru malloc & free


void selectionSorting(int** arr , int arrayBuffer)
{

	for (int i = 0; i < arrayBuffer - 1; i++) // Traversam toata colectia mai putin ultinmul element 
	{
		for (int j = i + 1; j < arrayBuffer; j++)
		{
			if ((*arr)[i] < (*arr)[j])  // "<" PENTRU NUMERE DESCRESCATOARE IAR ">" PENTRU NUMERE CRESCATOARE
			{
				// Efectuam Algoritmul de Inteschimbare 
				int temp = (*arr)[i];
				(*arr)[i] = (*arr)[j];
				(*arr)[j] = temp;
			}
			// Daca nu , continuam 
		}
		
	}
	
}

int main()
{
	int arrayBuffer;

	printf("Cate numere doresti sa aiba colectia : ");
	
	scanf_s("%d", &arrayBuffer);

	int* a = (int*)malloc(arrayBuffer * sizeof(int)); // ALOCAM UN ARRAY IN FUNCTIE DE CATE NUMERE VREA UTILIZATORUL SA INTRODUCA
	
	printf("Insereaza %d numere la intamplare : \n",arrayBuffer);


	for (int i = 0; i < arrayBuffer; i++)
	{
		printf("colectie[%d] = ", i);
		scanf_s("%d", &a[i]);  // Inseram numerele de la tastatura 

	}

	selectionSorting(&a,arrayBuffer);  // Transferam colectia prin adresa 


	/// Printam Colectia 

	printf("Printam colectia ordonata : \n");

	for (int i = 0; i < arrayBuffer; i++)
	{
		printf("v[%d]=%d\n", i, a[i]);
	}


		// Eliberam Memoria Ocupata de Array (Sa prevenim Memory Leak)

		free(a);  // Eliberam Colectia in sine 
		a = NULL; // Setam NULL Pointer 


	return 0;
}

NOTA 1 **   :  E USOR DE IMPLENTAT SI INTELES , IDEAL UNDE SE LUCREAZA CU LISTE MICI SI  SIMPLITATEA E NECESARA !! 

NOTA 2 ** :  CU CAT LISTA ESTE MAI MARE , CU ATAT VOM AVEA O COMPLEXITATE TIMP MAI MARE (MAI INEFICIENT) !!