Inversul unui cuvant in C

Inversul unui cuvant in C

   In tutorialul de astazi mi-am propus sa va explic cum ar trebui sa abordam aceasta problema, respectiv cea a intoarcerii unui cuvant, in limbajul de programare C.

Pentru inceput, ce reprezinta inversul unui cuvant? Sa luam cuvantul test, inversul lui este tset. Inversul lui craciun este nuicarc. Ei bine, cum vom duce la bun sfarsit aceasta prolema? Stim ca fiecare caracter din cuvantul pe care dorim sa-l intoarcem este stocat intr-un array, astfel puteam accesa fiecare caracter, in parte, si putem face operatii majore aupra cuvantului intreg.
O prima idee ar fi sa copiem caracter cu caracter din primul array, de la sfarsit spre inceut, intr-un alt array.

#include < stdio.h >
#include < string.h > 

int main() {
    char string1[] = "test";
    char string2[5];
    int i, j;
    int n = strlen(string1);

    for(i = 0, j = n - 1; i < n; i++, j--) {
        string2[i] = string1[j];
        //printf("%d  %d\n", i, j);
    }
    string2[i] = '\0';

    printf("%s", string2);

    return 0;
}

In codul de mai sus, parcurgem caracter cu caracter din variabila string1 de la sfarsit spre inceput si il salvam in variabila string2. Astfel, variabila string2 va contine reprezentarea inversului cuvantului pe care am dorit sa-l intoarcem.

In bucla for din codul nostru, atribuim caracterul de pe pozitia j din array-ul string1 elementului string2[i]. La primul ciclu al buclei, cand variabila i are valoarea 0 si variabila j are valoarea 3, 
elementul string2[0] va retine valoarea stocata in variabila string1[3] - deci, ultimul caracter din array-ul string1.

Programul nostru isi duce la bun sfarsit misiunea, dar nu in cel mai eficient mod - folosind si variabila string2 ocupam memorie in plus. Exista un mod mai elegant de indeplini aceasta cerinta. El se bazeaza pe faptul ca putem inversa primul caracter al unui cuvant cu ultimul, al doilea cu penultimul, al treilea cu antepenultimul. Vom continua asa pana cand nu vor mai fi caractere de inversat, atunci constatam ca am inversat cuvantul.

Exemplu:

test

Vom inversa primul caracter, t, cu ultimul caracter - coincidenta face ca acesta sa fie tot t.

test

Acum inversam al doilea caracter cu penultimul. Dupa acest pas observam ca nu mai avem ce inversa, deci ne-am indeplinit cerinta.

tset

Iata si codul:

#include < stdio.h >
#include < string.h >

int main() {
    char string[] = "test";
    char temp;
    int i, j;

    for(i = 0, j = strlen(string) - 1; i < j; i++, j--) {
        temp = string[i];
        string[i] = string[j];
        string[j] = temp;
    }

    printf("%s", string);
    
    return 0;
}

Probabil ati observat si mai sus ca folosim headerul <string.h>, prezenta acestuia in codul nostru se datoreaza folosirii functiei strlen() ce este declarata in acest header, aceasta functie returneaza lungimea stringului ce i-a fost pasat drept argument..
Variabila temp este folosita pentru a putea inversa elementele de pe pozitiile i si j - probabil vom vorbi intr-un tutorial viitor despre acest procedeu.

S-ar putea sa te intrebi de ce am pus drept conditie de oprire a buclei i < j. Pentru a raspunde la aceasta intrebare trebue a abordam problema mai abstract. Inversam caracterele aflate la o anumita distanta pana cand ajungem la mijloc, daca numarul de caractere al cuvantului este par, atunci, avem 2 mijlocuri. Dupa ce am facut inversia caracterelor din mijloc trebuie sa ne oprim pentru ca am inversat cuvantul. In cazul in care numarul de caractere ale cuvantului este impar, atunci, avem un singur mijloc. In acest caz vom inversa caracterele din cuvant pana ajungem la mijloc. Ultimele caractere inversate vor fi cele din jurul mijlocului.

Practic, asta ar trebui sa vizualizati cand inversam un cuvant cu numar par de caractere. Incercati, pur si simplu, sa invartiti cuvantul in mintea voastra.

Asta ar trebui sa vizualizati cand doriti sa inversati un cuvant cu numar impar de caractere.

Deci, daca vom continua sa inversam caractere pana cand i va fi mai mare ca j, nu vom face decat sa readucem cuvantul in forma initiala. Vom inversa inversul cuvantului, de asta ne oprim la mijloc. Daca trecem de acea bariera care este mijlocul, atunci, inversam caracterele care au fost deja inversate, deci readucem cuvantul la forma initiala. - iar noi nu vrem acest lucru.

In cazul cuvantului cu numar impar de caractere craciun, puteti observa ca vom inversa caractere pana cand ajungem la caracterul c - caracterul din mijloc, respectiv limita. Indecsi i si j nu pot trece acea limita.

Puteti observa in cazul cuvantului cu numar par de caractere test limitele pe care trebuie sa le atinga fiecare index. Daca am incalca aceasta limita, i ar deveni mai mare ca j, iar daca noi vom inversa caracterul de pe pozitia i cu cel de pe pozitia j, nu vom face decat sa aducem caracterele in forma initiala.

Shel sort - algortim de sortare

Shel sort - algortim de sortare

   Astazi mi-am propus sa vorbim despre un algoritm de sortare ceva mai special fata de cel precedent, insertion sort. Algoritmul a fost descoperit in 1959 de D. L. Shell - de aici provine si denumirea de "Shell sort". Practic, algoritmul este o generalizare a insertion sort.

Descrierea algoritmului

   In etapele de inceput se sorteaza subsiruri din cel principal, aceste subsiruri au elementele la o distanta prestabilita. In etapele de inceput numarul acestor subsiruri este mare, dar acestea contin putine elemente. Pe masura ce avansam, numarul subsirurilor se imputineaza, dar numarul elementelor acestor subsiruri creste. Intr-un final vom ramane doara cu un sir, iar de aici se aplica algortimul de insertion sort clasic.

Sa nu o mai lungim si s atrecem la un exemplu practic:

Sa luam sirul:

6, 5, 4, 3, 2, 1 

   Dupa cum spuneam, se va face sortare pe mai multe subsiruri. Cum stabilim numarul de subsirurilor de inceput? Stabilind distanta dintre elemente la fiecare cilclu. Conform autorului, la inceput acest interval va avea valoarea [n/2], n reprezinta numarul de elemente ale sirului, iar prin [ si ] reprezentam partea intrega a acelui numar. Ai uitat ce reprezinta partea intreaga?

Partea intreaga reprezinta valoarea din partea stanga a virgulei, partea intreaga a numarului 6.5 este 6, partea intreaga a numarului 8.999999 este 8.

Pe masura ce inaintam spre un alt ciclu injumatatim aceasta valoare, adica la al doilea ciclu al buclei valoarea acestui interval va fi [[n/2]/2],  adica am injumatatit valoarea intervalului de la ciclul precedent si i-am luat partea intreaga. 

   Sirul nostru contine 6 elemente, deci distanta dintre elemente va fi de [6/2] = 3. Acestea sunt intervalele: 

6, 5, 4, 3, 2, 1

6, 5, 4, 3, 2, 1

6, 5, 4, 3, 2, 1

Aplicam algortimul clasic de insertion sort pe fiecare dintre aceste 3 siruri, incepem cu primul:

6, 5, 4, 3, 2, 1

Sirul sortat contine elementul 6, il vom compara pe 3 cu fiecare element din sirul sortat pentru a stabili unde il inseram. Deoarece sirul sortat al subsirului format din 6 si 3 contine doar elementul 6 il vom compara pe 3 cu 6. Deoarece 6 este mai mare ca 3, acestea vor schimba pozitiile. Asa arata subsirul 1 acum:

3, 5, 4, 6, 2, 1 

Elementele ce compun subsirul 1, 3 si 6, sunt in ordine. Avansam la urmatorul subsir, cel format din elementele 5 si 2.

3, 5, 4, 6, 2, 1

Aplicam algorimul clasic de insertion sort pe acest subsir. 5 este mai mare ca 2? Da, deci acestea vor interschimba pozitiile. Asa arata subsirul 2 acum:

3, 2, 4, 6, 5, 1

Si cel de al doilea sir este sortat, elementele  ce compun sirul, 2 si 5, sunt in ordine. Trecem la ultimul subsir:

3, 2, 4, 6, 5, 1

4 este mai mare decat 1? Da! Deci elementele 4 si 1 vor interschimba pozitiile. Asa arata subsirul nostru acum:

3, 2, 1, 6, 5, 4

Intr-un final, puteam observa ca am sortat toate cele 3 subsiruri:

3, 2, 1, 6, 5, 4

3, 2, 1, 6, 5, 4

3, 2, 1, 6, 5, 4

Acum ca am sortat toate cele 3 sirui, vom injumatati valoarea intervalului extragand doar partea intreaga din acesta: [[6/2]/2] - dar cine este [6/2]? 3. Deci [3/2] = 1. Daca distanta dintre elemente este 1, atunci avem doar un singur subsir - intrucat distanta dintre elementele acestui subsir este 1. Deci, subsirul nostru este:

3, 2, 1, 6, 5, 4  

Dar subsirul nostru este chiar sirul principal pe care vrem sa-l sortam, de aici aplicam algortimul clasic de insertion sort. Incepem de la elementul de indice 1, deci:

3, 2, 1, 6, 5, 4

Il comparam pe 2 cu fiecare element din lista sortata, care este compusa doar din 3 la a acest moment. Deci, 3 este mai mare ca 2? Da! acestea doua vor interschimba pozitiile. Sirul nostru va arata asa:

2, 3, 1, 6, 5, 4

Trecem la urmatorul element, 1, si-l vom compara cu fiecare elemnt din lista sortata pentru a decide unde-l vom insera. 

2, 3, 1, 6, 5, 4

3 este mai mare ca 1? Da. 3 si 1 vor schimba pozitiile.

2, 1, 3, 6, 5, 4

2 est mai mare ca 1? Da. 2 si 1 vor schimba pozitiile.

1, 2, 3, 6, 5, 4

Pentru a sorta sirul in continuare trebuie doar sa continui sa aplici insertion sort - despre care am vorbit in ultimele 2 tutoriale.

Sa luam sirul format din elementele:

8, 7, 6, 5, 4, 3, 2, 1

Pentru inceput vom aveam [8/2] - deoarece sirul are 8 elemente, n=8 - deci intervalul dintre elementele primelor subsiruri va fi 4. Iata subsirurile:

8, 7, 6, 5, 4, 3, 2, 1

8, 7, 6, 5, 4, 3, 2, 1

8, 7, 6, 5, 4, 3, 2, 1

8, 7, 6, 5, 4, 3, 2, 1

Vom aplica algortimul de insertion sort pe fiecare dintre aceste subsiruri. Incepem cu primul:

8, 7, 6, 5, 4, 3, 2, 1

Tot ce avemd e facut este sa aplicam algortimul de insertion sort pe sirul ce contine elementele  8 si 4. 8 va fi primul element al sirului sortat, deci il vom compara pe 4 cu 8 pentru a decide unde-l inseram pe 4. 8 este mai mare ca 4, deci 8 si 4 vor schimba pozitiile.

4, 7, 6, 5, 8, 3, 2, 1

Primul subsir este sortat, trecem la urmatorul.

4, 7, 6, 5, 8, 3, 2, 1

Il vom compara pe 3 cu 7 - elementul ce compune sirul sortat al subsirului format din elementele 7 si 3. 7 este mai mare decat 3, deci aceste vor schimba pozitiile.

4, 3, 6, 5, 8, 7, 2, 1

Cel de al doilea subsir este sortat, trec la al treilea.

4, 3, 6, 5, 8, 7, 2, 1

6 este mai mare ca 2? Da. 2 si 6 vor schimba pozitiile.

4, 3, 2, 5, 8, 7, 6, 1

Si cel de al treilea subsir este sortat, trecem la ultimul.

4, 3, 2, 5, 8, 7, 6, 1

5 este mai mare ca 1? Da! Deci 5 si 1 vor schimba pozitiile.

4, 3, 2, 1, 8, 7, 6, 5

Am sortat toate cele 4 subsiruri, acum putem sa injumatatim valoarea intervalului. Deci, [4/2]=2. Distanta dintre elementele sirurilor ce se vor forma este de 2. Acestea sunt subsirurile:

4, 3, 2, 1, 8, 7, 6, 5

4, 3, 2, 1, 8, 7, 6, 5

Incepem cu primul subsir, cel format din elementele: 4, 2, 8, 6. Sirul sortat este format din elementul 4, vom compara fiecare element din sirul nesortat cu fiecare din sirul sortat pentru a decide unde-l inseram. 

4, 3, 2, 1, 8, 7, 6, 5

Il comparam pe 2 cu 4. 4 este mai mare ca 2, deci aceste elemente vor schimba pozitiile.

2, 3, 4, 1, 8, 7, 6, 5

Trecem la urmatorul element, 8:

2, 3, 4, 1, 8, 7, 6, 5

Nu este niciun element mai mare ca 8 in sirul sortat, deci trecem mai departe la elementul 6.

2, 3, 4, 1, 8, 7, 6, 5

8 este mai mare ca 6? Da. deci 8 si 6 ar trebuis a schimbe pozitiile.

2, 3, 4, 1, 6, 7, 8, 5

Am sortat primul subsir, mai trebuie sa-l sortam pe al doilea:

2, 3, 4, 1, 6, 7, 8, 5

Incepem cu elementul 1, il vom compara cu fiecare elemnt din sirul nesortat - compus, deocamdata, doar din 3. 3 este mai mare ca 1? Da. Deci 3 si 1 ar trebui sa schimbe pozitiile.

2, 3, 4, 1, 6, 7, 8, 5

2, 1, 4, 3, 6, 7, 8, 5

Urmeaza sa-l comparam pe 7 cu elementele din sirul sortat pentru a stabili unde-l inseram.

 2, 1, 4, 3, 6, 7, 8, 5

Deoarece niciun element nu este mai mare ca 7, acesta isi va pastra pozitia. Trecem la elementul 5.

 2, 1, 4, 3, 6, 7, 8, 5

7 este mai mare ca 5, deci 5 si 7 ar trebuis a schime pozitiile. Sirul nostru arata asa acum:

2, 1, 4, 3, 6, 5, 8, 7

Am sortat cele doua subsiruri, acum putem sa mergem mai departe injumatatind valoarea intervalului. Deci, [2/2] = 1. Cum valoarea intervalului este 1, insemana ca de aici vom avea doar un sigur subsir:

2, 1, 4, 3, 6, 5, 8, 7

Pentru a-l sorta pe acesta vom aplica algortimul e insertion sort clasic. Incepem cu elementul 1, il comparam cu restul elementelor din lista sortata pentru a decide unde-l inseram. Apoi continuam cu elementul 4, repedem procedeul si mergem mai departe cu urmatorul element pana cand sirul este sortat.

Observa ca numarul de subsirui este egal cu valoaera fiecarui interval!

Impelementatia algoritmului

for(gap = n/2; gap > 0; gap /= 2) {
        for(i = gap; i < n; i++) {
            for(j = i - gap; j >= 0 && v[j] > v[j + gap]; j -= gap) {
                temp = v[j + gap];
                v[j + gap] = v[j];
                v[j] =  temp;
            }
        }
    }

   Vom implementa algortimul in limbajul C:

Pe linia 1 avem o bulca for ce initializeaza variabila gap cu valoarea n/2 si va rula pana cand variabila gap va lua valoarea 1 - intrucat conditia ne impune ca gap sa fie strict mai mare ca 0. la fiecare etapa injumatatim valoarea lui gap. Iti este familiara aceasta variabila gap? Exact, aceasta variabila gap este acel interval despre care am discutat mai sus. Probabil te intrebi de ce nu luam partea intreaga  a valorii n/2 inainte de a o stoca in gap. Nu este nevoie, intrucat variabila gap este de tipul intreg, iar acest tip de data nu poate retine numere cu virgula(reale).

Pe linile ce urmeaza avem generalizarea algortimului e insertion sort. Astfel, poti observa ca pe aceste linii sortam elementele aflate la gap distanta. Cand gap va lua valoarea 1, atunci nu vom face decat un insertion sort clasic.

Pe  liniile 4, 5 si 6  interschimbam valoarea elementului curent cu cea a a celui precedent in interval. Aceasta secventa este metoda clasica de swap.