• 締切済み

ヒープソートの問題について

分からない問題があります。 どなたかお教え下さい。よろしくお願いします。 Max-Heapify (A,i) 1. L <- 2i 2. R <- 2i+1 3. if L<= heap-size[A] かつ A[L] > A[i] 4. then largest <- L 5. else largest <- i 6. if R<= heap-size[A] かつA[R] > A[largest]) 7. then largest <-R 8. if largest !=i 9. then 値の交換A[i] <-> A[largest] 10. Max-Heapify (A,largest) Build-Max-Heap (A) 1. heap-size[A] <- length[A] 2. for i<- ⌊length[A] /2⌋ downto 1 3 do Max-Heapify (A,i) Heap-Sort (A) 1. Build-Max-Heap (A) 2. for i<- length[A] downto 2 3 do 値の交換 A[1]<->A[i] 4 heap-size[A] = heap-size [A] – 1 5 Build-Max-Heap (A) 上に示す疑似コードを参考に、以下の問いに答えなさい。ただし、length[A]、heap-size[A]は配列Aの要素数、配列Aに格納されているヒープの要素をそれぞれ示す。 a. ヒープに格納される要素数をnとし、要素の添字の範囲を求めなさい。 b. 配列A=<3,9,8,15,4,2,5,1,7,10>からBuild-Max-Heapによりmax-ヒープを生成したときの結果を示しなさい。 c. 上のHeapsortは、配列を正しくソートするか？しないなら、正しくソートするようにするにはどのように修正すればよいか？理由と共に答えなさい。 d. マージソートと比較してヒープソートの良い点を述べなさい。

  • 科学
  • 回答数1
  • ありがとう数0

みんなの回答

  • Tacosan
  • ベストアンサー率23% (3656/15482)
回答No.1

疑似コードの読み方が分からん. 「何が分からないのか」も分からん.

  1. カテゴリ
  2. 学問・教育
  3. 自然科学
  4. 科学

関連するQ&A

  • ヒープソート

    何回も申し訳ございません。ヒープソートを使用して、K番目に小さい配列の要素を見つけるプログラムを作成していますが、セグメンテーションフォルトが出力され、途方に暮れています。どなたか助けていただけないでしょうか？ #include<stdio.h> #include<stdlib.h> #include<time.h> void heap(int c,int size,int *s){ int child,p; int tmp; child=s[c]; while(1){ p=(c-1)/2;//calculate an index of their parent if(c<0) break; if(c!=0){ if (s[c]>s[c-1]) { c=c-1; } } if (s[p]<=s[c]) break; // break if a parent is smaller than a child tmp=s[p]; s[p]=s[c]; s[c]=tmp; c=p;//declare a parent node as a child node } } void heap_sort(int c,int size,int *s){ int tmp,i,j; //make the first heap for(i=size-1;i>=0;i--){ heap(i,size,s); } //exchange root s and the last s, and sort them for(i=size-1;i>=0;i--){ tmp=s[0]; s[0]=s[i]; s[i]=tmp; for(j=i;j>=0;j--){ heap(j-1,j,s); } } } main() { int num,i,k; int high; int low=0; int s[20]; struct timeval t1,t2; printf("How many elements?:"); scanf("%d",&high); printf("?n"); printf("What number?:"); scanf("%d",&k); printf("?n"); srand((unsigned)time(NULL)); for(i=0;i<high;i++){ s[i]=rand()%10; printf("%d ",s[i]); } printf("?n"); gettimeofday(&t1,0); heap_sort(high-1, high,s); gettimeofday(&t2,0); printf("Time=%dmicrosec?n", t2.tv_usec-t1.tv_usec); printf("The %dth smallest is %d?n ", k,s[k]); }

  • C++でのマージソートの実現方法について

    C++でのマージソートの実現方法について、以下のコードを書いたのですが、どうしてもうまくソートできませんでした。 marge関数がおかしいと思うのですが、自分で確かめてみても、どこがおかしいのか分かりませんでした。 どなたか、どうすればソートされた結果がメイン関数で表示されるようにできるのか教えていただけないでしょうか？ #include <iostream> #include <vector> using namespace std; class Array { private: vector<int> array; public: void insert( int value ){ array.push_back( value ); } int getSize( ){ return (int)array.size( ); } void marge_sort( ){ marge_sort( 0, (int)array.size( ) - 1 ); } void marge_sort( int left, int right ); void marge( int left, int middle, int right ); void print( ); }; // マージソートにより配列の添字 left ～ right の部分を整列する関数 void Array::marge_sort( int left, int right ){ if( left >= right ) { return; } int middle = (left + right) / 2; //中央の添字を求める marge_sort( left, middle ); //左の要素が全てバラバラになるまで marge_sort( middle + 1 , right ); //右の要素が全てバラバラになるまで marge( left, middle, right ); //バラバラの要素をソートして併合 } // 個別にソートされた2つの配列（添字 left ～ middle と添字 middle+1 ～ right）を作業用配列を使ってマージする関数 void Array::marge( int left, int middle, int right ) { int num=right-left; int *tmp=new int[num]; int t=0,l=left,r=middle; while(l<middle&&r<right){ if(array[l]<=array[r]){ tmp[t++]=array[l++]; } else { tmp[t++]=array[r++]; } } while(l<middle){ tmp[t++]=array[l++]; } while(r<right){ tmp[t++]=array[r++]; } for(int i=0;i<num;i++){ array[left+i]=tmp[i]; } delete tmp; } // 配列の内容を表示する関数 void Array::print( ) { for ( int i = 0; i < (int)array.size( ); i++ ) { cout << array[i] << " "; } cout << endl; } int main( ) { Array a1; a1.insert( 56 ); a1.insert( 34 ); a1.insert( 57 ); a1.insert( 64 ); a1.insert( 3 ); a1.insert( 87 ); a1.insert( 85 ); a1.insert( 37 ); a1.insert( 21 ); a1.insert( 4 ); a1.insert( 68 ); a1.insert( 62 ); a1.insert( 42 ); a1.insert( 55 ); a1.insert( 63 ); a1.insert( 95 ); a1.insert( 7 ); a1.insert( 32 ); a1.insert( 78 ); a1.insert( 11 ); cout << "要素数: " << a1.getSize( ) << endl; cout << "ソート前: "; a1.print( ); a1.marge_sort(); // ここで，ソートを行う関数を呼び出す cout << "ソート後: "; a1.print( ); return 0; } // 実行結果 要素数: 20 ソート前: 56 34 57 64 3 87 85 37 21 4 68 62 42 55 63 95 7 32 78 11 ソート後: 3 4 34 37 21 42 55 56 57 62 63 7 32 64 68 78 85 87 95 11 ↑のソート後の表示が、昇順にソートされるようにしたいのです。

  • ソート

    お世話になります。配列のソートなのですが、どうも思い通りの結果になりません。 配列の中から最大値と最小値を探し、最小値を配列0に、最大値を配列の最後に移動します。その2つ以外の数字の順番は変えません。 例） {4,3,2,0,1,2} 最小値は0、最大値は4なので→{0,3,2,1,2,4} {4,3,2,1}　→　{1,3,2,4} {1,3,2,4,}　→　{1,3,2,4} 流れとしては、まず最小値を求め配列0に移動させ、次に最大値を求め配列の最後に移動させようと思います。 プログラムは以下のように組みました。 public int[] sortOfSort(int[] array) { int count_min = 0; int min = array[0]; for (int i = 0; i < array.length-1; i++) { // 最小値を求める if (min > array[i + 1]) { min = array[i + 1]; count_min++; // 最小値の配列のインデックスを確保 } } for (int k = count_min; k > 0; k--) { // 最小値の移動 int temp_min = array[k - 1]; array[k - 1] = array[k]; array[k] = temp_min; } int count_max = 0; int max = array[0]; for (int j = 0; j < array.length-1; j++) { // 最大値を求める if (max < array[j + 1]) { max = array[j + 1]; count_max++; // 最大値の配列のインデックスを確保 } } for (int l = count_max; l < array.length-1; l++) { //最大値の移動 int temp_max = array[l + 1]; array[l + 1] = array[l]; array[l] = temp_max; } return array; } 間違っているところがわかりましたら宜しくお願いします。

    • ベストアンサー
    • Java
  • クイックソート

    今クイックソートのプログラム作成をしていますが、分からない箇所が幾つかあります。下は、作成した時のプログラムリストです。 class QuickSort{ static int compare = 0; 　　static int copy = 0; 　　 static int swap = 0; static void swap(int a[], int i, int j){ 　　　int tmp; tmp = a[i];copy++; a[i] = a[j];copy++; a[j] = tmp;copy++; swap++;} static void showArray(int a[], int l, int r){//配列の内容を表示するメソッドで、動作:部分配列a[l]～a[r]の要素を表示。これが分かりません。 　　　　int a[l] = {1,2,3,4,5,6,7,8,9,10}; int a[r] = {11,12,13,14,15,16,17,18,19,20};} static void initArray(int a[], int N){ int i; 　　　　a[0]=0; for(i=1;i<N;i++) a[i] = i; for(i=1;i<N;i++){ int j,k; j = (int)(java.lang.Math.random()*(N-1)) + 1; k = (int)(java.lang.Math.random()*(N-1)) + 1; swap(a,j,k);}} public static void (int a[],int l, int r) { if (r+1-l <= 1) return; int e = (l+r+1)/2; int c = 0; return a[c]; } static int partition(int a[], int l, int r, int pivot){// 配列の分割を行うメソッドです。そのあと分割に要した比較回数(=iの増加分+jの減少分)を変数compareに加算し、iの値を戻り値として返さないといけませんが、そこんとこが分かりません。 while (true) { while (a[l] < pivot) l = l + 1; while (a[r] >= pivot) r = r - 1; if (l > r) return l; swap(a, l, r); } } static void swap(int[] a, int i, int j) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp; } } int i=0; int j=0; return i; } static void quicksort(int[] a, int l, int r){//(カットオフなしで)再帰的にクイックソートを行うメソッドです。paritionメソッドを用い、a[l]～a[r]を分割値a[r]で分割するのが条件ですが、ここも全然分かりません。 if(l < r){ int i = l; int j = r; int x = a[(i+j)/2]; do{ while(a[i]<x) i++; while(a[j]>x) j--; if(i<=j) { swap(a,i,j); i++; j--; } }while(i<=j); quickort(a,l,j); quicksort(a,i,r); } } static void swap(int[] a, int s, int t){ int temp = a[s]; a[s] = a[t]; a[t] = temp; return; int i,pivot; } public static void main(String args[]){ //上で作ったメソッドを用いて、ソート過程を表示しながらクイックソートを実行 //手順は次のようになる。 　　　　1.要素を(20個もつ)整数型配列aを宣言 　　　　2.整数型変数Nに配列aの要素数を保存 　　　　3.initArrayメソッドを用いて配列aを初期化 4.showArrayメソッドを用いてソート前の配列aの内容を表示 5.変数compare,copyの値を0に初期化 6.quickSortメソッドを用いて配列aを選択ソート 　　　　7.showArrayメソッドを用いてソート後の配列aの内容を表示 8.ソートにかかった比較・コピーの回数を表示 //これも分かりません。 } 分かる人がいましたら教えて下さい。お願いします。

  • 一次元配列で表現された最小ヒープの値挿入

    問題文：ヒープに新たなデータを挿入する関数insertを作成せよ。空の配列に複数回insertを行うことで 構成したヒープがヒープ条件を満たしていることをcheck_heapを用いることで確認せよ。プロトタイプ宣言は以下とする。 void insert(int val, int a[],int *n); 質問：　 複数回はおいといてとりあえず1回insertしようと思って書いたんですが、ヒープの最後に新しいノードを 作って親より小さければ親の値と交換を繰り返してヒープを完成させようとしてるんですが、1回しか交換されません。 どうすればいいですか？check_heapは最小ヒープ条件が満たされていれば１を満たされていなければ０を返す関数です。 自分のソース #include<stdio.h> #include<stdlib.h> #include<time.h> int check_heap(int a[], int n); void insert(int val, int a[], int *n); int main(void) { int a[11] = {1,13,71,14,15,80,91,24,60,63}; int n; int i; int b,c; srandom(time(NULL)); b = random() % 100 + 1; n = 10; insert(b, a, &n); printf("%d\n", check_heap(a, 11)); for(i = 0; i < 11; i++){ printf("%3d", a[i]); } return 0; } int check_heap(int a[], int n) { int i; int m; m = (n - 1) / 2; for(i = 0; i < m; i++) { if(a[i] >= a[i * 2 + 1]) { return 0; } if(a[i] >= a[i * 2 + 2]){ return 0; } } if(n % 2 == 0){ if(a[(n - 1)/2] > a[n - 1]){ return 0; } } return 1; } void insert(int val, int a[], int *n) { int temp; a[*n] = val; while(a[(*n-1) / 2] >= a[*n]){ temp = a[(*n-1) / 2]; a[(*n-1) / 2] = a[*n]; a[*n] = temp; } }

  • Javaプログラミングについて

    ・下記のプログラミングで「//ここで配列を昇順にソートする」というプログラムがわかりません！！ わかる方がいましたらサンプルを教えてください。 public class SortNum { public static void main(String[] args){ int[] a={5,9,3,1,7,8,2,6,4}; //数列の初期化 //ここで配列を昇順にソートする //ソートされた配列を出力 for(int i = 0;i < a.length;i++){ System.out.println(a[i]); } } }

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

    クイックソートの比較交換回数を変数countで計算し、表示させようとしているのですがうまくいきません。 改善策を教えていただけないでしょうか。 /* クイックソート */ void quickSort(randomlist_t data[],int n){ /* 実質的な処理は何もせず、クイックソートを実際に行う関数を呼び出すのみ */ int count = 0; quickSort_1(data,0,n-1,count); printf("count:%d\n",count); } /* 実際にクイックソートを行う関数 */ void quickSort_1(randomlist_t data[],int l,int r,int count){ int v; if(l >= r) /* 整列する要素が1つなら、何もしないでリターンする */ return; v = partition(data,l,r,count); /* 枢軸vを基準に分割する */ quickSort_1(data,l,v-1,count); /* 左の部分の配列a[l]～a[v-1]を整列する */ quickSort_1(data,v+1,r,count); /* 右の部分の配列a[v+1]～a[r]を整列する */ } /* 配列a[l]～a[r]を分割する。枢軸の添え字を返す */ int partition(randomlist_t data[],int l,int r,int count){ int i,j,pivot; randomlist_t t; i = l - 1; j = r; /* ポインタiとjを初期化する */ pivot = data[r].no; /* 一番右端の要素を枢軸にする */ for(;;){ /* ポインタiとjとがぶつかるまで繰り返す */ while(data[++i].no < pivot) count++; /* ポインタiを右へ進める */ while(i < --j && pivot < data[j].no) count++; /* ポインタjを左へ進める */ if(i >= j) break; /* ポインタiとjがぶつかったらループを抜ける */ t = data[i]; data[i] = data[j], data[j] = t; /* iの指す要素とjの指す要素を交換する */ count++; } t = data[i]; data[i] = data[r]; data[r] = t; /* a[i]と枢軸を交換する */ count++; return i; }

  • 単純挿入ソート法の要素の比較回数についての問題

    単純挿入ソート法の要素の比較回数、移動回数についての問題 『単純挿入ソート法は、シャトルソート法とも呼ばれ、挿入とシフトを用いるソートである。 下図（添付図）はこのソート法の１ステップを示している。 配列a[0],…,a[n-1]があって、a[i]より前の部分がソートされている。 ここで、a[i]の値をwとする。 a[0],…,a[i-1]の 部分で、w が入るべき位置を探す。 この位置をj とする。配列の範囲 a[j],…,a[j-1]をa[j+1],…,a[i] ヘシフト する。最後に、wをa[j]に格納する。 このような操作を、最後まで繰り返す。 以下の問に答えよ。 問(1)～(3) 省略 問(4)単純挿入ソート法で要素の比較回数のオーダーを答えなさい。ただし、配列の要素数を n とする。 問(5)単純挿入ソート法で要素の移動回数のオーダーを答えなさい。ただし、 配列の要素数を n とする。』 問(1)～(3)は単純挿入ソート法で配列を昇順にソートするC言語で記述されたプログラムに関する問題なのですがそちらは解けました。 問(4)は比較回数のオーダーを S とすると、最悪の場合 n(n-1)/2 回 比較を行う必要があるので、S=n(n-1)/2 問(5)は移動回数のオーダーを T とすると、最悪の場合 n(n-1)/2 回 移動を行う必要があるので、T=n(n-1)/2 と考えているのですが自信がありません。 そもそもここで問われているオーダーとは回数のことをいってるのか、そうではないのかが分かりません。 どなたか説明していただけますと大変助かります。解答以外にもこの問題に関連することに対してのアドバイスなどがありましたら答えてくださると嬉しいです。 時間がなくて少し焦っています。どうか何卒よろしくお願いします。

  • クイックソートについて

    下記のソースプログラムのquick_sort_coreの部分がわかりません。 わかる方助けてください。 あとこのソースを降順にした場合の変更点も教えていただけると助かります。 #include <stdio.h> /* printf()利用のため */ #include <stdlib.h> /* rand()利用のため */ #include <time.h> /* clock()利用のため */ #define N 10 /* 整列対象要素数 */ /** * 配列の中身を表示する関数 * @param a 表示する配列 * @param n 配列の要素数 */ void print_array(const int a[], int n) { int i; for (i = 0; i < n; i++) { printf("%d ", a[i]); } printf("\n"); } /** * 整列されているかどうか確認する関数 * @param a 確認対象配列 * @param n 配列の要素数 */ void is_sorted(const int a[], int n) { int i; for (i = 0; i < n - 1; i++) { if (a[i] > a[i + 1]) { printf("昇順に整列されていません\n"); return; } } printf("昇順に整列されています\n"); } /** * クイックソートの本体 * @param a 整列対象配列 * @param l 対象の最初の要素番号 * @param r 対象の最後の要素番号 */ void quick_sort_core(int a[], int l, int r) { /* ここを実装する */ } /** * これまでの整列関数のインターフェースにあわせるクイックソート呼び出し関数 * @param a 整列対象配列 * @param n 配列の要素数 */ void quick_sort(int a[], int n) { quick_sort_core(a, 0, n - 1); } int main(void) { int i; int n = N; /* 整列対象要素数 */ int a[N]; clock_t start,end; /* 0からRAND_MAXの一様乱数をn個生成し、配列aに格納 */ for (i = 0; i < n; i++) { a[i] = rand(); /* 出力確認(print_array)するときは a[i]=rand()%100 としておくと見やすい */ } /* 昇順にソートされているか確認（デバッグ用） */ is_sorted(a, n); /* 配列の中身を確認（デバッグ用） */ print_array(a, n); /* 開始時刻の取得 */ start = clock(); /* クイックソート関数の呼び出し */ quick_sort(a, n); /* 終了時刻の取得 */ end = clock(); /* 配列の中身を確認（デバッグ用） */ print_array(a, n); /* 昇順にソートされているか確認（デバッグ用） */ is_sorted(a, n); /* 実行時間の表示 */ printf("%d 個の要素のクイックソートの実行に %f [秒]かかりました\n", n, (double)(end - start) / CLOCKS_PER_SEC); return 0; }

  • ファイルの読み込みとメモリ確保について。

    ファイルから文字を読み込んで それを配列に入れて辞書順にソートさせようとしています。 それで、ソート以前の問題なのですが、ファイルから文字列を読み込んで配列にいれようとするのですが、 buffを動的にメモリ確保してその配列に入れたいと考えているのですが、なぜか入ってくれません。 whileでファイルの終わりがくるまで一行ずつ読み込んで それをｓに入れていき、ｓをbuff[]の配列に順番にいれていこうとしているのですが・・・。 ファイルは aaaa aabc dda wer zie ced sdfe be など適当な文字の並びです。 malloc関数で動的に確保したメモリはその後普通の配列と同様に使えるのではなかったのでしょうか？ なので普通にbuff[i]=s;といった処理で入れれると思ったのですが。 ファイルは一行の長さの最大が100で 行数が4000行あると仮定しています。 今は小さいファイルでテストしていますが。 以下ソースです。 #include <stdio.h> #include <stdlib.h> #define MAX_SIZE 100 #define MAX_LINE 4000 main() { FILE *fp; char *buff,s[MAX_SIZE]; int i; fp=fopen("words.txt","r"); buff=(char*)malloc(sizeof(char)*MAX_LINE); i=0; while(fgets(s,MAX_SIZE-1,fp)!=NULL){ buff[i]=s; printf("%s",buff[i]); i++; } fclose(fp); } とりあえずファイルの内容を配列に入れないとソートできないので、配列に全て入れてしまいたいと考えています。 間違いがどこにあるのか指摘よろしくおねがいします。m(-_-)m

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する