Cuprins Limbajul C

Gandirea algoritmica
Structura unui program si a unei functii in C
Constructiile de bază ale limbajului C – Notiuni generale
Constructiile de baza ale limbajului C – Tipuri de date
Constructiile de baza ale limbajului C – Operatori
Structuri de date – Lista liniara simplu inlantuita
Structuri de date – Stiva (LIFO – Last In First Out)
Structuri de date – Coada (FIFO – First In First Out)
Instructiuni ale limbajului C
Pointeri – Operatori specifici, tablouri, functii
Pointeri – Tipuri structurate de date
Functii de biblioteca
Operatii cu fisiere
Calcul Matriceal – Produsul a doua matrici
Calcul Matriceal – Inversarea unei matrici
Calcul Matricial – Metoda lui Gauss
Metode de sortare – sortare ordinara
Metode de sortare – prin selectie (Selection sort)
Metode de sortare – insertie directa (Direct Insertion Sort)
Metode de sortare – insertie binara (Binary Insertion Sort)
Metode de sortare – insertie directa folosind o santinela
Metode de sortare – metoda bulelor (Bubble Sort)
Metode de sortare – sortare rapida (Quick Sort)
Metode de sortare – prin interclasare (Merge Sort)
Recursivitate (numar factorial, algoritmul lui Euclid recursiv, sirul lui Fibonacci)
Backtracking – permutarile
Backtracking – aranjamente
Backtracking – combinari
Backtracking – problema reginelor
Backtracking – problema labirintului
Backtracking – problema calului
Backtracking – problema mingii
Metoda Divide et Impera – Suma elementelor unui sir
Metoda Divide et Impera – Problema Turnurilor din Hanoi
Metoda Divide et Impera – Elementul maxim intr-un sir
Metoda Divide et Impera – Problema cautarii binare
Grafuri neorientate – parcurgerea in latime
Grafuri neorientate – parcurgerea in adancime
Grafuri neorientate – Drumuri intr-un graf
Grafuri neorientate – ponderate
Grafuri neorientate – hamiltonian
Grafuri neorientate – euleriene
Grafuri neorientate – implementarea unui graf utilizand matricea de adiacenta
Grafuri neorientate – implementarea unui graf utilizand pointeri
Grafuri neorientate – drumul optim intr-un graf

Metode de sortare – insertie binara (Binary Insertion Sort)

Se deosebeşte de inserţia directă doar prin modul de căutare a poziţiei de inserare. Presupunem că căutăm poziţia de inserare a elementului cu valoarea 20 în secvenţa:
1 4 7 9 10 12 15 18 21 23 26 28 33

0 1 2 3 4 5 6 7 8 9 10 11 12
1 4 7 9 10 12 15 18 21 23 26 28 33
S=0 M=6 D=12

Se calculeaza M=(Standa+Dreapta)/2=(0+12)/2=6

1 4 7 9 10 12 15 18 21 23 26 28 33
S=0 M=6 D=12

a[M]=a[6]=15, 20>15 deci cautam in dreapta, noul interval este S=7, D=12

1 4 7 9 10 12 15 18 21 23 26 28 33
S=7 M=9 D=12

M=(7+12)/2=9, a[9]=23, 20<23 deci cautam in stanga, noul interval este S=6 D=8

1 4 7 9 10 12 15 18 21 23 26 28 33
S=6 M=7 D=8

M=(6+8)/2=7 a[7]=18, 20>18 deci cautam in dreapta, noul interval este S=8, D=8

1 4 7 9 10 12 15 18 21 23 26 28 33
S=M=D=8

M=(8+8)/2=8, a[8]=21, 20<21 deci cautam in stanga, noul interval este S=8, D=7

1 4 7 9 10 12 15 18 21 23 26 28 33

Conform algoritmului ne oprim cand S>D iar pozitia de inserat este S=8; inainte de inserare, elementele a[12] -> a[8] se declara spre dreapta cu o pozitie


#include "stdio.h"
#include "conio.h"
//functie care intoarce pozitie in care trebuie inserat
//a[i] in secventa a[1]...a[i-1]
int insertie_binara(int a[], int i)
Continue reading