Определение количества смен, выполняемых при сортировке вставки?

Question

Я пытаюсь решить этот вопрос http://www.mycodeschool.com/work-outs/sorting/7 Вопрос заключается в том, чтобы найти нет сдвигов в сортировке вставки.

Я написал код, но не мог понять, где я неправильно в логике

http://ideone.com/GGjZjw

#include<iostream> 
#include<cstdio> 
#include<cmath> 
// Include headers as needed 

using namespace std; 

int main() 
{ 
// Write your code here 
int T,count,n,*a; 
// int imin; 
cin >> T; 
int value,hole; 

while(T--) 
{ 
    cin >> n; 
    count=0; 
    a=new int[n]; 
    //reading the input array 
    for(int i=0;i<n;i++) 
    { 
     cin >> a[i]; 
    } 

    // considering the 0th element to be already sorted and 
    // remaining list unsorted 
    for(int i=1;i<n;i++) 
    { 
     value=a[i]; 
     hole=i; 
     // shifting 
     while(hole>0&&a[hole-1]>value) 
     { 
      // 
      a[hole]=a[hole-1]; 
      hole=hole-1; 
      count++; 
     } 
     a[hole]=value; 
    } 
    // cout << count<<endl; 
} 
// Return 0 to indicate normal termination 
return 0; 
} 

Answer 1

Количество свопы, сделанных в вставки рода равно числу inversions в массиве (количество пар элементов, которые не соответствуют порядку). Существует well-known divide-and-conquer algorithm для подсчета числа инверсий в массиве, который выполняется во времени O (n log n). Это основано на слегка измененной версии mergesort, и я думаю, что вам не нужно слишком много проблем кодировать ее.

Answer 2

Проблема с вашим подходом заключается в том, что вы не правильно внедряете сортировку вставки, то, что вы достигли, это обратная сортировка пузырьков.

для немного менее сложной (но с худшей сложностью: P), чем решение O(n log n) @templatetypedef, которое вы можете решить в той же сложности сортировки O(n^2), применяя правильную реализацию.

Вы должны реализовать функцию для swap(int* array, int index_a, int index_b), чем считать, сколько раз эту функцию вызывали.

это Link к википедии имеет хороший псевдо-код для вас