質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

ソート

複数のデータを、順序性に従って並べ替えること。 データ処理を行う際に頻繁に用いられ、多くのアルゴリズムが存在します。速度、容量、複雑さなどに違いがあり、高速性に特化したものにクイックソートがあります。

データ構造

データ構造とは、データの集まりをコンピュータの中で効果的に扱うために、一定の形式に系統立てて格納する形式を指します。(配列/連想配列/木構造など)

Q&A

解決済

2回答

2562閲覧

ヒープソートの実装について。ソートできないです。

frere

総合スコア4

Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

ソート

複数のデータを、順序性に従って並べ替えること。 データ処理を行う際に頻繁に用いられ、多くのアルゴリズムが存在します。速度、容量、複雑さなどに違いがあり、高速性に特化したものにクイックソートがあります。

データ構造

データ構造とは、データの集まりをコンピュータの中で効果的に扱うために、一定の形式に系統立てて格納する形式を指します。(配列/連想配列/木構造など)

0グッド

0クリップ

投稿2020/08/09 09:03

編集2020/08/09 09:37

ヒープソートの実装をしたくてプログラムを組んだのですが動かないです。どこをどう直せばよいでしょうか?
[3,1,4,1,5,9,2,6,5,3,3]
上記の結果になりソートできません。

Java

1package exer3.sort; 2 3import java.util.ArrayList; 4import java.util.Comparator; 5import java.util.StringJoiner; 6 7public class HeapSort <T> { 8 9 private ArrayList<T> data; 10 private Comparator<T> cmp; 11 12 public static <E> void sort(ArrayList<E> a, Comparator<E> c){ 13 HeapSort<E> s = new HeapSort<>(a, c); 14 s.hsort(); 15 } 16 17 private HeapSort(ArrayList<T> a, Comparator<T>c) { 18 data = a; 19 cmp = c; 20 } 21 22 private void hsort() { 23 // 今のところ中身なし.プライベートメソッドの動作確認のコードをココに記入可 24 enter(9); 25 extract(9); 26 printHeap(); 27 } 28 29 private void swap(int a, int b) { 30 T tmp = data.get(a); 31 data.set(a, data.get(b)); 32 data.set(b, tmp); 33 } 34 35 private int parent(int n){ 36 return ( n - 1 )/2; 37 } 38 39 private int rightChild(int n){ 40 return 2 * n + 2; 41 } 42 43 private int leftChild(int n){ 44 return 2 * n + 1; 45 } 46 47 private void enter(int n){ 48 T a,b; 49 int pv = parent(n); 50 a = data.get(n); 51 b = data.get(pv); 52 while(pv >= 0){ 53 if(cmp.compare(data.get(pv) , data.get(n)) < 0){ 54 swap(n,pv); 55 n = pv; 56 pv = parent(n); 57 } 58 else 59 break; 60 } 61 } 62 63 private void extract(int n){ 64 65 if(data.size() != 0){ 66 T ret = data.get(0); 67 data.set(0, data.get(n)); 68 int v = parent(n); int lv = leftChild(n); int rv = rightChild(n); 69 while(lv < data.size()){ 70 if( rv < data.size() && cmp.compare(data.get(v) , data.get(lv)) < 0 && cmp.compare(data.get(lv) , data.get(rv)) >= 0){ 71 swap(v, lv); v = lv; 72 } 73 else if(rv < data.size() && cmp.compare(data.get(v) , data.get(rv)) < 0 && cmp.compare(data.get(lv) , data.get(rv)) < 0 ){ 74 swap(v,rv); 75 v = rv; 76 } 77 else if(rv == data.size() && cmp.compare(data.get(v) , data.get(lv)) < 0){ 78 swap(v,rv); 79 v = lv; 80 } 81 else 82 break; 83 lv = 2*v +1; 84 rv = 2*v +2; 85 } 86 data.add(ret); 87 } 88 89 } 90 91 private void printHeap() { 92 StringJoiner j = new StringJoiner(","); 93 for (T e : data) 94 j.add(e.toString()); 95 System.out.println("[" + j.toString() + "]"); 96 } 97} 98 99 100 101 102 103package exer3.sort.tester; 104 105import exer3.sort.HeapSort; 106import java.util.ArrayList; 107import java.util.StringJoiner; 108 109public class TesterHS01 extends Tester { 110 public static void main(String[] args) { 111 ArrayList<Integer> a = new ArrayList<>(); 112 a.add(3); a.add(1); a.add(4); a.add(1); a.add(5); 113 a.add(9); a.add(2); a.add(6); a.add(5); a.add(3); 114 HeapSort.sort(a, (i1, i2) -> Integer.compare(i1, i2)); 115 } 116} 117 118 119 120 121 122package exer3.sort.tester; 123 124import java.util.ArrayList; 125import java.util.StringJoiner; 126 127public class Tester { 128 public static <T> void print(ArrayList<T> lst) { 129 StringJoiner j = new StringJoiner(","); 130 for (T e : lst) 131 j.add(e.toString()); 132 System.out.println("[" + j.toString() + "]"); 133 } 134 135 public static <T> void printA3(ArrayList<Integer> o, 136 ArrayList<String> k, ArrayList<T> v) { 137 for(Integer i : o) 138 System.out.printf("[%d] %s\t%s\n", 139 i, k.get(i), v.get(i).toString()); 140 } 141} 142

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

y_waiwai

2020/08/09 09:29

動かないとはどういうふうになるんでしょうか 詳しく書きましょう
Zuishin

2020/08/09 09:45

> public static <E> void sort(ArrayList<E> a, Comparator<E> c){ > HeapSort<E> s = new HeapSort<>(a, c); > s.hsort(); > } ソート結果を捨ててるからですね。
frere

2020/08/09 10:16

コンストラクタが間違っているということですか?
frere

2020/08/09 10:17

どう直せばいいですか?
guest

回答2

0

ベストアンサー

ヒープソートのアルゴリズムがきちんと実装できていないためソートできていません。
途中経過を出すなりして何が間違っているのか確認しながら修正してください。

メソッドenter()はおそらくUp-Heapを実装していると思いますが、正しく動作しています。
ただし使い方が間違っています。
メソッドextract()はDown-Heapのつもりでしょうが、data.size()を使っていてはヒープソートの実装はできません。
そして、同じく使い方が間違っています。

それぞれ使い方は下記の様な形の使い方になるかと。

private void hsort() { //0~i-1番目まではヒープ済みとし、i番目をヒープに追加する。 for(int i=1;i<data.size();i++){ enter(i); } printHeap(); //ここまでは正しくヒープ木が出力される。 //i~N番目まではソート済みとし、i番目にヒープの最大値を置き、Down-Heapする。 for(int i=data.size()-1;i==0;i--){ extract(i); } printHeap(); }

投稿2020/08/09 12:10

Kaleidoscope

総合スコア257

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

frere

2020/08/09 14:43

private void extract(int n){ if(n != 0){ T ret = data.get(0); data.set(0, data.get(n)); int v = parent(n); int lv = leftChild(n); int rv = rightChild(n); while(lv < n){ if( rv < n && cmp.compare(data.get(v) , data.get(lv)) < 0 && cmp.compare(data.get(lv) , data.get(rv)) >= 0){ swap(v, lv); v = lv; } else if(rv < n && cmp.compare(data.get(v) , data.get(rv)) < 0 && cmp.compare(data.get(lv) , data.get(rv)) < 0 ){ swap(v,rv); v = rv; } else if(rv == n && cmp.compare(data.get(v) , data.get(lv)) < 0){ swap(v,rv); v = lv; } else break; lv = 2*v +1; rv = 2*v +2; } data.add(ret); } } 上記にしてみたんですけど治らないです [9,6,5,5,3,3,2,1,4,1] [9,6,5,5,3,3,2,1,4,1]
guest

0

java

1import java.util.ArrayList; 2import java.util.Comparator; 3 4class HeapSort<T> { 5 private ArrayList<T> data; 6 private Comparator<T> cmp; 7 8 public static <E> void sort(ArrayList<E> a, Comparator<E> c){ 9 HeapSort<E> s = new HeapSort<>(a, c); 10 s.hsort(); 11 } 12 13 private HeapSort(ArrayList<T> a, Comparator<T> c) { 14 data = a; 15 cmp = c; 16 } 17 18 private void hsort() { 19 int i = 0, n = data.size(); 20 while (++i < n) enter(i); 21 while (--i > 0) extract(i); 22 printHeap(); 23 } 24 25 private void swap(int a, int b) { 26 T tmp = data.get(a); 27 data.set(a, data.get(b)); 28 data.set(b, tmp); 29 } 30 31 private int parent(int n) { return (n-1) / 2; } 32 private int rightChild(int n) { return 2 * n + 2; } 33 private int leftChild(int n) { return 2 * n + 1; } 34 35 private void enter(int n) { 36 int pv = parent(n); 37 while (pv > 0 && cmp.compare(data.get(pv), data.get(n)) < 0) { 38 swap(n, pv); 39 n = pv; 40 pv = parent(n); 41 } 42 } 43 44 private void extract(int n) { 45 swap(0, n); 46 int m = 0, v = 0, lv = leftChild(v), rv = rightChild(v); 47 while (lv < n) { 48 if (cmp.compare(data.get(v), data.get(lv)) < 0) 49 m = lv; 50 if (rv < n && cmp.compare(data.get(m), data.get(rv)) < 0) 51 m = rv; 52 if (m == v) break; 53 swap(v, m); 54 v = m; 55 lv = leftChild(v); 56 rv = rightChild(v); 57 } 58 } 59 60 private void printHeap() { System.out.println(data); } 61} 62 63class Main { 64 public static void main(String[] args) { 65 ArrayList<Integer> a = new ArrayList<>(); 66 a.add(3); a.add(1); a.add(4); a.add(1); a.add(5); 67 a.add(9); a.add(2); a.add(6); a.add(5); a.add(3); 68 HeapSort.sort(a, (i1, i2) -> Integer.compare(i1, i2)); 69 } 70}

投稿2021/11/18 20:51

編集2021/11/18 21:33
kazuma-s

総合スコア8224

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問