Jump to content

[C] Binary Insertion Sort


TLG George
 Share

Recommended Posts

  Insertion Sort este un algoritm simplu care funcționează similar cu sortarea cărților de joc în mâini. Array-ul este împărțit virtual într-o parte sortată și alta nesortată.
  Începem cu al doilea element din tablou și îl comparăm cu predecesorul, dacă este mai mic le interschimbăm și trecem mai departe. Figura de mai jos ilustrează acest algoritm:

 

Insertion Sort - GeeksforGeeks


  Putem transforma algoritmul într-unul mult mai eficient folosind căutarea binară prezentată de mine în topicul anterior (click). Astfel metoda noastră de sortare se va numi Binary Insertion Sort si va fi cea mea eficientă metodă de sortare deoarece se folosește de căutarea binară pentru a găsi locația corectă pentru a insera elementul selectat la fiecare iterație. 

 

Algoritmul este următorul:

int binarySearch(int a[], int i, int low, int high, int n)
{
    if (high <= low)
        return (i > a[low]) ? (low + 1) : low;
    int mid = (low + high) / 2;
    if (i == a[mid])
        return mid + 1;
    if (i > a[mid])
        return binarySearch(a, i, mid + 1, high, n);
    return binarySearch(a, i, low, mid - 1, n);
}



void insertionSort(int v[], int n)
{
    int locatia, k, selectat;

    for (int i = 1; i < n; i++)
    {

        int j = i -1;
        selectat = v[i];

        // cautam locatia unde selected ar putea fi inserat
        locatia = binarySearch(v, selectat, 0, j, n);

        // mutam toate elementele dupa locatie ca sa cream spatiu
        while (j >= locatia)
        {
            v[j + 1] = v[j];
            j--;
        }
        v[j + 1] = selectat;
    }
}

Vă invit să testați codul și apoi să-l scrieți singuri. Spor la treabă! :) 

Link to comment
Share on other sites

Guest
This topic is now closed to further replies.
 Share

×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.