1

Assume I have an array of N numbers unsorted. To sort the array I use the following code:

for (int i = 1; i < n; i = i + 1)
{
 int j = i; 
 while (j > 0 && a[j] < a[j - 1])
   {
    swap(a[j], a[j - 1]);
    j = j - 1;
   }
}

which is known as bubble sort as far as i know. To decrease the number of the inversions/call of swap function, i can pre-swap any two elements, say they have indexes i and j, then I perform the actual sort function. What is the most efficient algorithm to find such number of pairs(i,j) such that the number of inversions becomes minimum? Actually this a Codeforces problem and i also went through the tutorial and lots of accepted codes. But still I'm having difficulties in understanding the logic behind them. Since I'm a novice programmer could anyone please explain me the process starting from scratch? Thanks in advance :)

2
  • I recall bubble sort as not a very efficient method, so why try to improve this code? Since you say you are a novice programmer, I'd like to suggest to use linear search for sorting, which is also generally not very efficient, but it is very simple to implement, and, as Knuth wrote, it is still more efficient than other methods provided the list of numbers is not too big, say up to a few hunderd items.
    – Roland
    Feb 24, 2015 at 15:57
  • Thanks for trying to help me :) but i know how bubble sort works as well as some sorting algorithm such as insertion sort, merge sort etc. But what i got from the tutorial, the solution i'm trying to find probably involves some kind of divide-and-conquer technique and I'm having real difficulties in deciphering the logic :( I can provide the problem link if it helps [codeforces.com/contest/362/problem/C]
    – Faiza
    Feb 24, 2015 at 16:08

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.