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:
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ă!