≪逆順序ペア｜Inverse Pair｜oem_src≫:挿入ソートから集計ソートへ
9250 ワード
A[1..n]をN個の非負の整数を含む配列とする.iA[j]がある場合、(i,j)はAの逆シーケンス対(inversion)と呼ばれる.a)配列[2,3,8,6,1]の5つの逆順をリストする.
b)配列の要素が集合{1,2,...,n},では,どのような配列が最も多くの逆順序対を含んでいるのか.逆順ペアは何個含まれていますか?
c)挿入ソートの実行時間と入力配列における逆シーケンスペアの数との間にはどのような関係があるか.あなたの理由を説明します.
d)O(nlogn)の最悪の場合の実行時間を用いて、n個の要素の任意の配列における逆順序対の数を決定するアルゴリズムを与える(ヒント:集計順序を修正する)——『アルゴリズム導論』、思考問題2-4
逆順対の応用はとても多くて、例えば各種OJの中の逆順対テーマ:http://www.cppblog.com/ickchen2/articles/62422.html、更に《プログラミングの美》1.7光影切断問題解法2の交点の個数を求めます.上の思考問題から逆順対アルゴリズムを理解するのは簡単で、これもタイトルに示された構想過程である.本稿では,O(nlogn)解法をほとんど接触していない読者や理解していない読者に対して,これまで逆順がうるさいように見えた.
問題a)直接定義に基づいて<2,1>,<3,1>,<8,6>,<8,1>,<6,1>を得ることができる.
問題b)逆順対が最も多くなるためには、いずれかの数をそれよりも小さい数の前にして、可能なすべての逆順、すなわち[n,n−1,...,1]を構成し、これにより、(n−1)+(n−2)+...+1=n(n-1)/2個です.
問題c)は、挿入ソートが行われると、配列がソートされた部分とソートされる部分の2つに分けられる.ソートされる部分の最初の要素をソートされた部分に挿入するたびに、挿入された位置を特定し、その後のソートされた要素を順番に後ろに移動する必要があります.また、1つの要素について、挿入中に後方に移動する要素の数は、元の配列の前の逆シーケンスペアの数である.これは,逆順対定義によってO(n 2)の検出方式を書くことができ,両者は同じであるからである.
実は問題cに対して、本意は読者に挿入ソートを使って逆順序ペアを探すことを教えるのではありません:同じO(n 2)のアルゴリズムで、このようにして何の改善もありません;問題d)に対する解答を啓発することにある.
1.集計ソートでは、同じ配列を2つのセグメントに分けて処理します.この2つのセグメントを処理する場合、右のセグメント要素と左のセグメント要素の逆順序関係には影響しません.集計時にのみ変更されます.
2.集計時の変更方法と挿入順序は類似している:右セグメントから要素を取り出して左セグメントの残りのすべての要素の前に置くと、左セグメント全体の後に移動することに相当し、後に移動する要素数はこの逆シーケンス数である.
3.集計ソートは分割法を用いているため、集計ごとの逆順数を加算し、最終的には総逆順数となる.また,集計ソートの時間的複雑さはO(nlogn)であり,挿入ソートよりも優れている.
以上の検討によれば,集計並べ替えを少し修正すると,時間的複雑度O(nlogn)の逆順対総数を探すアルゴリズムが得られ,以下に簡単な例を示す.
b)配列の要素が集合{1,2,...,n},では,どのような配列が最も多くの逆順序対を含んでいるのか.逆順ペアは何個含まれていますか?
c)挿入ソートの実行時間と入力配列における逆シーケンスペアの数との間にはどのような関係があるか.あなたの理由を説明します.
d)O(nlogn)の最悪の場合の実行時間を用いて、n個の要素の任意の配列における逆順序対の数を決定するアルゴリズムを与える(ヒント:集計順序を修正する)——『アルゴリズム導論』、思考問題2-4
逆順対の応用はとても多くて、例えば各種OJの中の逆順対テーマ:http://www.cppblog.com/ickchen2/articles/62422.html、更に《プログラミングの美》1.7光影切断問題解法2の交点の個数を求めます.上の思考問題から逆順対アルゴリズムを理解するのは簡単で、これもタイトルに示された構想過程である.本稿では,O(nlogn)解法をほとんど接触していない読者や理解していない読者に対して,これまで逆順がうるさいように見えた.
問題a)直接定義に基づいて<2,1>,<3,1>,<8,6>,<8,1>,<6,1>を得ることができる.
問題b)逆順対が最も多くなるためには、いずれかの数をそれよりも小さい数の前にして、可能なすべての逆順、すなわち[n,n−1,...,1]を構成し、これにより、(n−1)+(n−2)+...+1=n(n-1)/2個です.
問題c)は、挿入ソートが行われると、配列がソートされた部分とソートされる部分の2つに分けられる.ソートされる部分の最初の要素をソートされた部分に挿入するたびに、挿入された位置を特定し、その後のソートされた要素を順番に後ろに移動する必要があります.また、1つの要素について、挿入中に後方に移動する要素の数は、元の配列の前の逆シーケンスペアの数である.これは,逆順対定義によってO(n 2)の検出方式を書くことができ,両者は同じであるからである.
for(i=0;j<n;j++)
for(i=0;i<j;i++)
if(A[i]>A[j])
count++;実は問題cに対して、本意は読者に挿入ソートを使って逆順序ペアを探すことを教えるのではありません:同じO(n 2)のアルゴリズムで、このようにして何の改善もありません;問題d)に対する解答を啓発することにある.
1.集計ソートでは、同じ配列を2つのセグメントに分けて処理します.この2つのセグメントを処理する場合、右のセグメント要素と左のセグメント要素の逆順序関係には影響しません.集計時にのみ変更されます.
2.集計時の変更方法と挿入順序は類似している:右セグメントから要素を取り出して左セグメントの残りのすべての要素の前に置くと、左セグメント全体の後に移動することに相当し、後に移動する要素数はこの逆シーケンス数である.
3.集計ソートは分割法を用いているため、集計ごとの逆順数を加算し、最終的には総逆順数となる.また,集計ソートの時間的複雑さはO(nlogn)であり,挿入ソートよりも優れている.
以上の検討によれば,集計並べ替えを少し修正すると,時間的複雑度O(nlogn)の逆順対総数を探すアルゴリズムが得られ,以下に簡単な例を示す.
#include <stdio.h>
#include <stdlib.h>
#define MAXNUM 65535
#define length 8
static int data[length] ={5,2,4,7,1,3,2,6};
//#define length 5
//static int data[length] ={2,3,8,6,1};
int show_out(int *array,int n);
int merge(int *array, int nBegin, int nMid, int nEnd) {
int n1,n2;
int i,j,k;
int count =0;
n1 = nMid-nBegin+1; n2= nEnd-nMid;
int *left,*right;
left = (int *)malloc((n1+1) * sizeof(int));
right = (int *)malloc ((n2+1) * sizeof(int));
for (i=0;i<n1;i++)
left[i] = array[nBegin+i];
for (j=0;j<n2;j++)
right[j] = array[nMid+j+1];
left[n1] = MAXNUM;
right[n2] = MAXNUM;
i = 0;
j = 0;
for (k = nBegin;k<=nEnd;k++) {
if (left[i] <= right[j]) {
array[k] = left[i];
i++;
// left array,
}
else {
array[k] = right[j];
j++;
count += n1-i;
//left n1-i right[j]
// n1-i
}
}
free(left);
free(right);
show_out(array,length);
return count;
}
int inversion(int *array, int nBegin, int nEnd) {
int nMid,count = 0;
if (nBegin < nEnd) {
nMid = ((nEnd - nBegin)>>1) + nBegin;//nMid = (nBegin+nEnd)/2;
count = inversion(array,nBegin,nMid) +
inversion(array,nMid+1,nEnd) +
merge(array,nBegin,nMid,nEnd);
}
return count;
}
int show_out(int *array,int n) {
int k;
for (k = 0; k<n; k++)
printf("%d ",array[k]);
printf("
");
}
int main() {
int result;
result = inversion(data,0,length-1);
printf("inversions:%d
",result);
return result;
}