[解決済み] javaでマージソート
2022-02-11 19:14:31
質問
私はJavaの初心者で、Javaでマージソートを実装しようとしました。しかし、何度プログラムを実行しても、望ましいソートされた出力ではなく、ユーザーが与えた入力と同じものが出力として得られます。この予期せぬ挙動を理解するために、どなたかご助力いただければ幸いです。
import java.io.*;
import java.util.Arrays;
public class MergeSort {
public static void main(String[] args) throws IOException {
BufferedReader R = new BufferedReader(new InputStreamReader(System.in));
int arraySize = Integer.parseInt(R.readLine());
int[] inputArray = new int[arraySize];
for (int i = 0; i < arraySize; i++) {
inputArray[i] = Integer.parseInt(R.readLine());
}
mergeSort(inputArray);
for (int j = 0; j < inputArray.length; j++) {
System.out.println(inputArray[j]);
}
}
static void mergeSort(int[] A) {
if (A.length > 1) {
int q = A.length / 2;
int[] leftArray = Arrays.copyOfRange(A, 0, q);
int[] rightArray = Arrays.copyOfRange(A, q + 1, A.length);
mergeSort(leftArray);
mergeSort(rightArray);
A = merge(leftArray, rightArray);
}
}
static int[] merge(int[] l, int[] r) {
int totElem = l.length + r.length;
int[] a = new int[totElem];
int i, li, ri;
i = li = ri = 0;
while (i < totElem) {
if ((li < l.length) && (ri < r.length)) {
if (l[li] < r[ri]) {
a[i] = l[li];
i++;
li++;
} else {
a[i] = r[ri];
i++;
ri++;
}
} else {
if (li >= l.length) {
while (ri < r.length) {
a[i] = r[ri];
i++;
ri++;
}
}
if (ri >= r.length) {
while (li < l.length) {
a[i] = l[li];
li++;
i++;
}
}
}
}
return a;
}
}
解決方法は?
以下は、あなたのコードの修正版です。
import java.io.*;
import java.util.Arrays;
public class MergeSort {
public static void main(String[] args) throws IOException{
BufferedReader R = new BufferedReader(new InputStreamReader(System.in));
int arraySize = Integer.parseInt(R.readLine());
int[] inputArray = new int[arraySize];
for (int i = 0; i < arraySize; i++) {
inputArray[i] = Integer.parseInt(R.readLine());
}
mergeSort(inputArray);
for (int j = 0; j < inputArray.length; j++) {
System.out.println(inputArray[j]);
}
}
static void mergeSort(int[] A) {
if (A.length > 1) {
int q = A.length/2;
//changed range of leftArray from 0-to-q to 0-to-(q-1)
int[] leftArray = Arrays.copyOfRange(A, 0, q-1);
//changed range of rightArray from q-to-A.length to q-to-(A.length-1)
int[] rightArray = Arrays.copyOfRange(A,q,A.length-1);
mergeSort(leftArray);
mergeSort(rightArray);
merge(A,leftArray,rightArray);
}
}
static void merge(int[] a, int[] l, int[] r) {
int totElem = l.length + r.length;
//int[] a = new int[totElem];
int i,li,ri;
i = li = ri = 0;
while ( i < totElem) {
if ((li < l.length) && (ri<r.length)) {
if (l[li] < r[ri]) {
a[i] = l[li];
i++;
li++;
}
else {
a[i] = r[ri];
i++;
ri++;
}
}
else {
if (li >= l.length) {
while (ri < r.length) {
a[i] = r[ri];
i++;
ri++;
}
}
if (ri >= r.length) {
while (li < l.length) {
a[i] = l[li];
li++;
i++;
}
}
}
}
//return a;
}
}
関連
-
[解決済み】「'void' type not allowed here」エラーの原因とは?
-
[解決済み】純粋なJUnitテストにVisibleForTestingを使用する方法
-
[解決済み] JavaでInputStreamを読み込んでStringに変換するにはどうすればよいですか?
-
[解決済み] JavaでNullPointerExceptionを回避する方法
-
[解決済み] JavaにおけるHashMapとHashtableの違いは何ですか?
-
[解決済み] Java Mapの各エントリを効率的に反復処理するには?
-
[解決済み] Javaでメモリーリークを発生させるにはどうしたらいいですか?
-
[解決済み] Javaにおけるpublic、protected、package-private、privateの違いは何ですか?
-
[解決済み] JavaでArrayListではなくLinkedListを使用するのはいつですか?
-
[解決済み] JavaでStringをintに変換するにはどうしたらいいですか?
最新
-
nginxです。[emerg] 0.0.0.0:80 への bind() に失敗しました (98: アドレスは既に使用中です)
-
htmlページでギリシャ文字を使うには
-
ピュアhtml+cssでの要素読み込み効果
-
純粋なhtml + cssで五輪を実現するサンプルコード
-
ナビゲーションバー・ドロップダウンメニューのHTML+CSSサンプルコード
-
タイピング効果を実現するピュアhtml+css
-
htmlの選択ボックスのプレースホルダー作成に関する質問
-
html css3 伸縮しない 画像表示効果
-
トップナビゲーションバーメニュー作成用HTML+CSS
-
html+css 実装 サイバーパンク風ボタン
おすすめ
-
[解決済み】Hibernateエラー:同じ識別子値を持つ別のオブジェクトがすでにセッションに関連付けられました。
-
[解決済み] if / for / while 内で "Missing return statement" が発生する。
-
[解決済み】Android Studio クラス org.codehaus.groovy.runtime.InvokerHelper を初期化できませんでした。
-
[解決済み】StringUtils.isBlank() vs String.isEmpty()
-
[解決済み】"比較メソッドはその一般契約に違反する!"
-
[解決済み】「error: '.class' expected」の意味と修正方法について
-
[解決済み】「java -cp」と「java -jar」の違い?
-
[解決済み】java 'jar'が内部コマンドまたは外部コマンドとして認識されない。
-
[解決済み】Javaのswitch文。定数式が必要だが、定数である
-
[解決済み】CreateProcess error=2, The system cannot find file specified.