Click here to Skip to main content
15,889,851 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
could anyone please tell me how this code sorts the array? i don't get it! and how is this code reducing the complexity of a regular insertion sort?

C#
// Function to sort an array a[] of size 'n'
void insertionSort(int a[], int n)
{
    int i, loc, j, k, selected;

    for (i = 1; i < n; ++i)
    {
        j = i - 1;
        selected = a[i];

        // find location where selected sould be inseretd
        loc = binarySearch(a, selected, 0, j);

        // Move all elements after location to create space
        while (j >= loc)
        {
            a[j+1] = a[j];
            j--;
        }
        a[j+1] = selected;
    }
}
Posted
Updated 28-Mar-15 23:37pm
v2
Comments
Alexis i 29-Mar-15 5:36am    
i got the code from " http://geeksquiz.com/binary-insertion-sort/ "
barneyman 30-Mar-15 1:42am    
it's just a bubble sort really - with the binarySearch optimising discovery of the 'bubbleto' point in the array

run it in a debugger if you can't mentally visualise what it's doing ...

1 solution

 
Share this answer
 
Comments
Alexis i 29-Mar-15 6:56am    
it doesn't contain the binary sort!
Mehdi Gholam 29-Mar-15 8:29am    
You should have enough information to understand how it works, also read this http://en.wikipedia.org/wiki/Insertion_sort

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900