25 februarie 2010

Sortare prin numarare (Counting sort)

Principiul consta in determinarea numarului de elemente mai mici decat fiecare dintre elementele x date, si astfel pozitia fiecarui element in noul vector.
Avand un vector x[] de dimensiune n, cream un vector auxiliar: c[] de dimensiune k si un vector destinatie b[] de dimensiune n, ultimul reprezentand vectorul x sortat. k reprezinta valoarea maxima din vectorul x. Odata determinate numarul de elemente mai mici decat un element din x, acesta poate fi pozitionat direct pe pozitia sa in vectorul destinatie.

De exemplu, avem sirul x [] ={6, 0, 4, 7, 1, 2 }
Elementul maxim este 7, deci k=8 pozitii rezervate pentru vectorul c[], care se umplu cu 0, c [] = { 0, 0, 0, 0, 0, 0, 0, 0}
Apoi, pentru fiecare valoare a elementelor lui x, se incrementeaza valoarea de pe pozitia c[x[j]], devenind in cazul nostru c [] = {1, 1, 1, 0, 1, 0, 1, 1} (in functie de numarul de aparitii)
Apoi, in vectorul c[] se determina cate elemente sunt mai mici decat pozitia curenta, c[] = {1, 2, 3, 3, 4, 4, 5, 6}
In vectorul b[], se seteaza pentru fiecare pozitie c[x[j]-1] valoarea lui x[j], dupa care aceasta valoare se decrementeaza. b [] = { 0, 1, 2, 4, 6, 7 }

#include "stdio.h"
#include "stdlib.h"

int afla_max (int *x, int n) {

int max = x[0], i;
for(i=1; i <> max)
max=x[i];
return max;
}

int main () {

int n=7, i , j;
int *x = (int *)malloc(n*sizeof(int));
for(i=0; i < n; i++)
x[i]= rand ()%100;

int k = afla_max(x,n)+1;

int *c = (int *)malloc (k*sizeof(int));
int *b = (int *)malloc (n*sizeof(int));

for(i=0; i < k; i++)
c[i]=0;
for(j=0; j < n; j++)
c[x[j]]++;
for(i=1; i < k; i++)
c[i]+=c[i-1];
i = 0;
int prec = -1;
for(j=0; j < k; j++) {
if(c[j] != prec && c[j] > 0 )
b[i++] = j;
prec = c[j];
}

for(i=0; i < n; i++)
printf("%d ", b[i]);
return 0;
}

Sortare prin insertie (Insertion sort)

Pentru realizarea sortarii prin insertie, ideea de baza este inserarea unui anumit element in sirul deja sortat al predecesorilor sai.

De exemplu, fie un sir nesortat: 3, 14, 8, 4, 21, 16 si vrem sa-l sortam crescator.
Se pastreaza primul element 3 considerandu-se un subsir deja sortat. Apoi se trece la 14, caruia ii cautam locul in subsir, observam ca 3 mai mic decat 14, si deci subsirul este sortat (3, 14, 8, 4, 21, 16). Trecem la 8, ii cautam locul in subsir. 8 mai mare decat 3, cautam locul in continuare. 8 mai mic decat 14, si deci 8 se va afla inainte de 14. Tot ceea ce facem mai departe este sa il inseram in acea pozitie, elementele care urmeaza dupa el mutandu-se la dreapta cu o pozitie (3, 8, 14, 4, 21, 16). Procedeul se repeta pana cand intreg vectorul ajunge sortat.

Algoritmul in Python este urmatorul :

import random

n = eval(input("Enter how many numbers.. "))
arr = []
for i in range (n):
    nr = random.randint(0,100)
    arr.append(nr)

print("Initial array array: ", end=" ")
for i in range (n):
    print (arr[i], end = " ")
print()


for i in range (1,n):
    key = arr[i]
    j = i-1
    while j >= 0 and arr[j] > key:
        arr[j+1] = arr[j]
        j = j-1
    arr[j+1] = key


print("Sorted array: ", end=" ")
for i in range (n):
    print (arr[i], end = " ")
print()

Sortare Bubble

Este cea mai simpla metoda de sortare, al carei principiu suna in felul urmator: se trece in mod repetat prin lista, comparand elementele doua cate doua. In cazul in care ele nu respecta relatia de ordine sunt inversate si se trece mai departe. Iteratia se opreste cand in urma unui ciclu complet nu s-au mai facut inversari de elemente.

In C, codul este urmatorul:

#include "stdio.h"
#include "stdlib.h"

int main () {

int i, n;
scanf ("%d", &n);
int *x = (int *) malloc (n*sizeof(int));
for (i=0 ; i < n ; i++)
x[i]= rand()%100;
int sch,aux; // sch - variabila 1 daca au avut loc interschimburi, 0 altfel
do {
sch=0;
for(i=0; i < n-1; i++)
if(x[i] > x[i+1]) {
aux=x[i]; x[i]=x[i+1]; x[i+1]=aux; sch=1;}
} while (sch==1);

for (i=0; i < n; i++)
printf ("%d ", x[i]);
return 0;
}

Boomblebee

Am decis sa deschid acest blog pentru a posta cateva articole utile celor interesati in programare, calculatoare si tehnologia informatiei.
Pentru inceput voi posta rezolvarile unor laboratoare ale facultatilor de profil (Automatica in particular), chestiuni generale cu explicatii daca este cazul. Astfel, sper sa ating subiecte din cateva materii cum ar fi programare, structuri de date, limbaje de asamblare, programare orientata pe obiecte, analiza si proiectarea algoritmilor, protocoale de comunicatii si retelistica, baze de date, etc, utile atat pentru studenti cat si elevi din liceu sau alte persoane interesate.
Sper sa va simtiti bine pe blog si sa va sporiti cunostintele!