/* インクルード宣言 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h> // 所要時間計測に必要
/* 定数宣言 */
#define SIZE 2000000 // 単語数
#define LEN 30 // 単語文字数
/* プロトタイプ宣言 */
void m_sort(char** list, int start, int end, int mode); // ソート部
int comp(char *w1, char* w2, int mode); // 用途別比較関数
long gettimeofday_micro(void); // 所要時間計測用関数
/* 変数宣言(マージ用)*/
char* m_space[SIZE];
int comp(char* s1, char* s2){
if(strlen(s1) != strlen(s2))
return strlen(s2) - strlen(s1);
else
return strcmp(s1, s2);
}
void q_sort(char** list, int start, int end){
char pivot[LEN];
int i, j;
char *tmp;
if(end - start < 1)return;
strcpy(pivot, list[(start + end) / 2]);
i = start; j = end;
while(1){
while(comp(list[i], pivot) < 0) i++;
while(comp(list[j], pivot) > 0) j--;
if(i >= j) break;
tmp = list[i];
list[i] = list[j];
list[j] = tmp;
i++; j--;
}
q_sort(list, start, i - 1);
q_sort(list, j + 1, end);
}
/* メイン関数 */
int main(int argc, char *argv[]){
/* 変数宣言 */
FILE* fp = NULL; // ファイルポインタ
char line[LEN]; // 文字列読み込み用
char** strs = (char**)malloc(sizeof(char*) * SIZE); // 文字列格納用
int count = 0; // 単語数格納用
long time1, time2; // 時刻(単位マイクロセカンド)格納変数
int i; // カウンタ変数
// ファイル読み込み
fp = fopen("wordlist.txt", "r");
while(fscanf(fp, "%s", line) != EOF){
strs[count] = (char*)malloc(sizeof(char) * LEN);
sprintf(strs[count], "%s", line);
count++;
}
fclose(fp);
// マージソート
time1 = gettimeofday_micro();
m_sort(strs, 0, count - 1, 0); // アルファベット順でソート
m_sort(strs, 0, count - 1, 1); // 長さでソート
time2 = gettimeofday_micro();
printf("マージソート:\t%6.3f 秒\n", (time2 - time1) / 1000000.0);
// ソート結果出力
fp = fopen("wordlist_m.txt", "w");
for(i = 0 ; i < count ; i++){
fprintf(fp, "%s\n", strs[i]);
}
fclose(fp);
return 0;
}
/* ソート部 */
void m_sort(char** list, int start, int end, int mode){
int i, j, k, m;
// 要素数が2未満ならソート不要
if(end - start < 1){
return;
}
// 分割操作
m = (start + end) / 2;
m_sort(list, start, m, mode);
m_sort(list, m + 1, end, mode);
for(i = start ; i <= m ; i++){
m_space[i] = list[i];
}
for(j = m + 1 ; j <= end ; j++){
m_space[j] = list[j];
}
// マージ操作
i = start;
j = m + 1;
for(k = start ; k <= end ; k++){
if(i > m)
list[k] = m_space[j++];
else if(j > end)
list[k] = m_space[i++];
else{
if(comp(m_space[i], m_space[j], mode) > 0){
list[k] = m_space[i++];
}
else{
list[k] = m_space[j++];
}
}
}
}
/* 用途別比較関数 */
int comp(char *w1, char* w2, int mode){
switch(mode)
{
case 0:
return strcmp(w1, w2);
case 1:
return strlen(w1) - strlen(w2);
}
return 0;
}
/* 所要時間計測用関数 */
long gettimeofday_micro(void){
struct timeval _tv;
gettimeofday(&_tv, NULL);
return _tv.tv_sec * 1000000 + _tv.tv_usec;
}
文字列データを読み込み,クイックソートでソートしてその結果をwordlist_q.txtに出力するプログラムを作成せよ.
ただし,(1) ソート結果は文字数の長い順で且つ同じ文字数同士はアルファベット順になるようにし,(2) ソートの所要時間を標準出力する機能を実装すること.また,(3) 添付のマージソート版より高速であること.
qsort関数などの既存の関数は利用せず,自分でクイックソートのコードを書くこと.
という課題でプログラムを書いてみましたがうまくいきません。どこが問題なのでしょうか?よければ教えてください。環境はLinaxです。