Începem cu o discuţie asupra problemelor generale ale calculabilităţii şi ale algoritmilor necesari pentru rezolvarea acestora, cu problema sortării, ca exemplu introductiv. Pentru a arăta cum vom specifica algoritmii prezentaţi, vom introduce un „pseudocod”, care ar trebui să fie familiar cititorilor obişnuiţi cu programarea. Sortarea prin inserţie, un algoritm simplu de sortare, va servi ca exemplu iniţial. Vom analiza timpul de execuţie pentru sortarea prin inserţie, introducând o notaţie care să descrie modul în care creşte acest timp o dată cu numărul obiectelor aflate în operaţia de sortare. De asemenea, vom introduce în proiectarea algoritmilor metoda, pe care o vom utiliza pentru dezvoltarea unui algoritm numit sortare prin interclasare. Vom încheia cu o comparaţie între cei doi algoritmi de sortare.

Fără a fi foarte exacţi, spunem că un algoritm este orice procedură de calcul bine definită care primeşte o anumită valoare sau o mulţime de valori ca date de intrare şi produce o anumită valoare sau mulţime de valori ca date de ieşire. Astfel, un algoritm este un şir de paşicare transformă datele de intrare în date de ieşire.

Putem, de asemenea, să privim un algoritm ca pe un instrument de rezolvare a problemelor de calcul bine definite. Enunţul problemei specifică, în termeni generali, relaţia dorită intrare/ieşire. Algoritmul descrie o anumită procedură de calcul pentru a se ajunge la această legătură intrare/ieşire.

Vom începe studiul algoritmilor cu problema sortării unui şir de numere în ordine nedescrescătoare. Această problemă apare frecvent în practică şi furnizează o bază foarte utilă pentru introducerea multor metode standard pentru proiectarea şi analiza algoritmilor. Iată cum vom defini formal problema sortării:

Date de intrare: Un şir de n numere〈a₁,a₂,...,aₓ〉.

Date de ieşire: O permutare (reordonare) a şirului initial,〈a’₁,a’₂,...,a’ₓ〉astfel încât a’₁≤a’₂≤...≤a’ₓ.

Fiind dat un şir de intrare, ca, de exemplu,〈31,41,59,26,41,58〉, un algoritm de sortare returnează, la ieşire, şirul〈26,31,41,41,58,59〉. Un şir de intrare ca cel de mai sus se numeşte o instanţă a problemei de sortare. În general, prin instanţă a unei probleme se va înţelege mulţimea tuturor datelor de intrare (care satisface restricţiile impuse în definirea problemei) necesare pentru a determina o soluţie a problemei.

Sortarea este o operaţie fundamentală în informatică (multe programe o folosesc ca pas intermediar) şi, ca urmare, a fost dezvoltat un număr mare de algoritmi de sortare. Care algoritm este cel mai bun pentru o aplicaţie dată depinde de numărul de obiecte care trebuie sortate, de gradul în care aceste obiecte sunt deja sortate într-un anumit fel şi de tipul de mediu electronic care urmează să fie folosit: memorie principală, discuri sau benzi magnetice.    

Un algoritm este corect dacă, pentru orice instanţă a sa, se termină furnizând ieşirea corectă. Vom spune că un algoritm corect rezolvă problema de calcul dată. Un algoritm incorect s-ar putea să nu se termine deloc în cazul unor anumite instanţe de intrare, sau s-ar putea termina producând un alt răspuns decât cel dorit. Contrar a ceea ce s-ar putea crede, algoritmii incorecţi pot fi uneori utili dacă rata lor de eroare poate fi controlată. Vom vedea un exemplu în capitolul „Algoritmi din teoria numerelor”, când vom studia algoritmi pentru găsirea numerelor prime foarte mari. Totuşi, în general ne vom ocupa doar de algoritmi corecţi.

Concret, un algoritm poate fi specificat printr-un program pentru calculator sau chiar ca un echipament hardware. Singura condiţie este aceea ca specificaţiile să producă o descriere precisă a procedurii de calcul care urmează a fi parcursă.

Sortarea prin inserţie este un algoritm eficient pentru sortarea unui număr mic de obiecte. Sortarea prin inserţie funcţionează în acelaşi fel în care mulţi oameni sortează un pachet de cărţi de joc obişnuite. Se începe cu pachetul aşezat pe masă cu faţa în jos şi cu mâna stângă goală. Apoi, luăm câte o carte de pe masă şi o inserăm în poziţia corectă în mâna stângă. Pentru a găsi poziţia corectă pentru o carte dată, o comparăm cu fiecare dintre cărţile aflate deja în mâna stângă, de la dreapta la stânga, aşa cum este ilustrat în figura de mai jos.

Pseudocodul pentru sortarea prin inserţie este prezentat ca o procedură numită Sortează-Prin-Inserţie, care are ca parametru un vector A[1..n] conţinând un şir de lungime n care urmează a fi sortat (pe parcursul codului, numărul de elemente ale lui A este notat prin ⌊A⌋). Numerele de intrare sunt sortate pe loc, în cadrul aceluiaşi vector A; cel mult un număr constant dintre acestea sunt memorate în zone de memorie suplimentare. Când Sortează-Prin-Inserţie se termină, vectorul iniţial A va conţine elementele şirului de ieşire sortat.

Sortează-Prin-Inserţie(A)

 1:  pentru j←2, ⌊A⌋ execută

 2:               ←A[j]

 3:       ▷ Inserează A[j] în şirul sortat A[1..j−1]

 4:       i←j–1

 5:       cât timp i>0 şi A[i]>                   execută

 6:           A[i+1]←A[i]

 7:           i←i–1

 8:       A[i+1]←

Indicele j corespunde „cărţii” care urmează a fi inserată în mâna stângă. Elementele A[1…j-1] corespund mulţimii de cărţi din mână, deja sortate, iar elementele A[j+1…n] corespund pachetului de cărţi aflate încă pe masă. Indicele se deplasează de la stânga la dreapta în interiorul vectorului. La fiecare iteraţie, elementul A[j] este ales din vector (linia 2). Apoi, plecând de la poziţia j-1, elementele sunt, succesiv, deplasate o poziţie spre dreapta până când este găsită poziţia corectă pentru A[j] (liniile 4–7), moment în care acesta este inserat (linia 8).

Indentarea indică o structură de bloc. De exemplu, corpul ciclului pentru, care începe în linia 1, constă din liniile 2–8 iar corpul ciclului cât timp, care începe în linia 5, conţine liniile 6–7, dar nu şi linia 8. Stilul nostru de indentare se aplică şi structurilor de tipul dacă-atunci-altfel. Folosirea indentării în locul unor indicatori de bloc de tipul begin şi end, reduce cu mult riscul de confuzie, îmbunătăţind claritatea prezentării. În limbajele de programare reale, indentarea, ca unică metodă pentru indicarea structurilor de bloc, nu este în general recomandabilă, deoarece nivelurile de indentare se determină greoi în cazul unor coduri care se continuă pe mai multe pagini.

Ciclurile de tipul cât timp, pentru, repetă şi construcţiile condiţionale dacă, atunci şi altfel au aceeaşi interpretare ca şi structurile similare din Pascal.

Simbolul ▷ indică faptul că restul liniei este un comentariu.

O atribuire multiplă de forma i←j←e înseamnă atribuirea valorii expresiei e ambelor variabile I şi j; aceasta ar trebui tratată ca un echivalent al atribuirii j←e, urmată de atribuirea i←j.