クイックソートの比較回数について

質問

中央値をピボットとするクイックソートで、入力データ数が１０２４で昇順データの場合はＯ(nlogn)の関係より10240回の比較回数が得られる、というのは合っているでしょうか？
ご回答お願い致します。

回答No.3

asuncion · ベストアンサー

Ｏ(nlogn)は、「正確に」nlognであるわけではなく、
そのオーダーであるということを言っているだけですので、
10240回でなくてもいっこうに差し支えないのではないでしょうか。

お礼

そうだったのですか！
私はてっきりオーダーは回数が関係あるものかと思ってました。
ご回答ありがとうございます！

回答No.2

asuncion

＞クイックソートのプログラムを作成し、比較回数を調べてみた

そのソースコードを見せていただくことは可能ですか？

お礼

以下が作成したものです。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_DATA 1024

void Quick(int x[], int left , int right);
void koukan(int x[],int i , int j);
void showData(int x[],int n);
int main(void);

int k = 0;
int h = 0;

void Quick(int x[],int left,int right){
int i,j;
int pivot;

i = left;
j = right;

pivot = x[(left + right) / 2];

while (1) {

while (x[i] < pivot){
h++;
i++;
}

while(pivot < x[j]){
h++;
j--;
}

if(i >= j)
break;

koukan(x,i,j);
k++;
}

if(left < i - 1){
Quick(x,left,i - 1);
}
if(j + 1 < right){
Quick(x,j+1,right);
}
}

void koukan(int x[],int i,int j)
{
int temp;

temp = x[i];
x[i] = x[j];
x[j] = temp;
}

void showData(int x[],int n)
{
int i;

for (i = 0; i < n;i++)
printf("%d ",x[i]);
printf("\n");
}

int main(void){
int i;
int x[MAX_DATA];
int n = MAX_DATA;

for(i = 0;i < MAX_DATA;i++){
x[i] = i;
}

printf("ソート前:\n");
showData(x,n);

printf("ソート中：\n");
Quick(x,0,n - 1);

printf("ソート後：\n");
showData(x,n);

printf("交換回数%d\n",k);
printf("比較回数%d\n",h);
return 0;
}

回答No.1

asuncion

比較回数を数えるためのサンプル・プログラムを書いてみてはいかがでしょうか。

お礼

お答えありがとうございます。
実はクイックソートのプログラムを作成し、比較回数を調べてみたのですが、出てきた回数は８０２４回だったので不安になり質問した次第です。