Java での検索と並べ替え: 主な違いと用途

この記事では、Java の検索および並べ替えアルゴリズムを対比し、その独特な機能、メソッド、および時間の複雑さを強調します。 データ整理のためのマージ ソートや効率的な検索のためのバイナリ サーチなどの実用的な例と実装を提供し、現実世界の問題解決機能を紹介します。

Java では、検索と並べ替えのアルゴリズムとその主な違いをしっかりと理解することが、アプリケーションの機能と効果的なデータ管理に不可欠です。 検索ではデータセット内の特定のデータを特定し、並べ替えではデータ自体を並べ替えます。この記事では、例を使用して、目的、方法論、アプリケーションの違いを探ります。

Java の検索アルゴリズムと並べ替えアルゴリズムの主な違いは、その目的、出力、効率、時間の複雑さにあります。 比較分析については表 1 を参照してください。

表 1 Java での検索と並べ替え

アルゴリズムの選択は、多くの場合、望ましい結果、アプリケーションのニーズ (データセットのサイズ、事前に並べ替えられたデータなど)、および特定の要件によって決まります。

表 2 は、いくつかの検索および並べ替えアルゴリズムの擬似コードの例と時間計算量を示しています。

表 2 実行時の複雑さと疑似コードの例 注: Java の Comparable インターフェースがなければ、コードはプリミティブ データ型にのみ適しています。 (出典: Lysecky, R.、および Lizarraga, A. (2022)。ZyLabs を使用した Java でのプログラミング、18.3 O 表記、図 18.3.2.)

分割統治アルゴリズムであるマージ ソートは、データ配列をより小さいサブ配列に再帰的に分割し、それらをソートしてから、ソートされたサブ配列をマージします (GeeksforGeeks、2020a)。 逆に、二分探索は、事前にソートされた配列に対して機能し、ターゲット要素が見つかるか、存在しないとみなされるまで、検索間隔を繰り返し半分にします (GeeksforGeeks、2020b)。

次の例は、マージ ソートを使用して ArrayList オブジェクトの Book を発行年ごとに並べ替え、続いて並べ替えられたリストで二分検索を実行する方法を示しています。

Book.java

/**
 * Book object with title and publication year. Implements Comparable for year-based sorting.
 * 
 * @author Alexander Ricciardi
 * @version 1.0
 * @date 07/14/2024
 */
class Book implements Comparable<Book> {
    String title;
    int year;

    /**
     * Book constructor.
     * @param title Book title.
     * @param year Publication year.
     */
    public Book(String title, int year) {
        this.title = title;
        this.year = year;
    }

    /**
     * Compares books by publication year.
     * @param other Book to compare.
     * @return Comparison result.
     */
    @Override
    public int compareTo(Book other) {
        return Integer.compare(this.year, other.year);
    }

    /**
     * Returns book's string representation.
     * @return String representation.
     */
    @Override
    public String toString() {
        return title + " (" + year + ")";
    }
}

BookSortingSearching.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

/**
 * Sorts and searches a list of books using merge sort and binary search.
 * 
 * @author Alexander Ricciardi
 * @version 1.0
 * @date 07/14/2024
 */
public class BookSortingSearching {

    // ... (mergeSort and binarySearch methods remain the same) ...

    public static void main(String[] args) {
        // ... (main method remains largely the same) ...
    }
}

...(mergeSort メソッドと binarySearch メソッドは、元の入力にあったため、ここに含まれます。長くなり、すでに存在するため、簡潔にするために省略しました。)

出力 (例):

... (Original and sorted lists are displayed here) ...
<p>Enter a year to search for: 1951
Book found: The Catcher in the Rye (1951)</p>

マージ ソートの O(n log(n)) の複雑さにより、大規模なデータセットに対して効率的になります。一方、Binary Search の対象を絞ったアプローチは、機械学習などのアプリケーション (最適なハイパーパラメーターの検索など) に適しています。

結論として、検索アルゴリズムと並べ替えアルゴリズムは別個ではありますが、相互依存しています。 並べ替え (マージ ソートなど) は、効率的な検索 (二分探索など) のためにデータを準備し、両方ともさまざまなドメインにわたる多様な問題解決に不可欠なものとなります。

---

参考文献:

オタクのためのオタク。 （2020a、11月18日）。 並べ替えを結合。オタクのためのオタク。 https://www.php.cn/link/d0e7b521c18b09876cb7693e42880dba

オタクのためのオタク。 （2020b、2月3日）。 二分探索。オタクのためのオタク。 https://www.php.cn/link/d29af1fd577b037033dd1149e816d521

リセッキー、R.、リザラガ、A. (2022)。 ZyLabs を使用した Java でのプログラミング。株式会社ザイアンテ

---

元々は、2024 年 11 月 22 日に Level UPcoding により、Medium の Alex.omegapy で公開されました。

以上がJava での検索と並べ替え: 主な違いと用途の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。