The problem asks us to find the number of swaps an insertion sorts does, which in a way is a measure of efficiency of the sort.
The basic logic is answer is the sum of ( for each element the number of elements greater than itself occuring before it .)
One way to implement it is Employ merge sort on it and during each merge operations if you are copying an element from the right array (swaps +=no. of elements in the left array) .
A novice mistake which I made what that I dynamically allocating and de-allocating a temporary array during each merge operation, BEWARE this is a very costly operation and should not be used. Allocate memory once and pass that array .
The basic logic is answer is the sum of ( for each element the number of elements greater than itself occuring before it .)
One way to implement it is Employ merge sort on it and during each merge operations if you are copying an element from the right array (swaps +=no. of elements in the left array) .
A novice mistake which I made what that I dynamically allocating and de-allocating a temporary array during each merge operation, BEWARE this is a very costly operation and should not be used. Allocate memory once and pass that array .
No comments:
Post a Comment