クイックソート

クイックソート 手順

クイックソートは以下の手順で行われる。

1. ピボットの選択：適当な値（ピボット（英語版）という）を境界値として選択する
2. 配列の分割：ピボット未満の要素を配列の先頭側に集め、ピボット未満の要素のみを含む区間とそれ以外に分割する
3. 再帰：分割された区間に対し、再びピボットの選択と分割を行う
4. ソート終了：分割区間が整列済みなら再帰を打ち切る

時間計算量

アルゴリズム	平均時間複雑度	最悪時間複雑度	最悪空間複雑度
クイックソート	O(n log(n))	O(n^2)	O(log(n))

JAVAサンプルコード

package Quick_sort;
import java.util.Scanner;

public class Quick_sort {

    static class Student {
        String name;
        int mark;

        public Student(String name, int mark) {
            this.name = name;
            this.mark = mark;
        }
    }

    static int partition(Student[] arr, int low, int high) {
        int pivot = arr[high].mark; // Choose the rightmost element as pivot
        int i = (low - 1); // Index of smaller element

        for (int j = low; j <= high - 1; j++) {
            if (arr[j].mark > pivot) {
                i++;
                Student temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        Student temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        return (i + 1);
    }

    public static void swap(int arr[], int i,  int j) {
        int temp = arr[i];
        arr[i] =  arr[j];
        arr[j] = temp;
    }

    public static void quick_sort(Student[] arr, int low, int high) {
        if (high > low) {
            int pivot = partition(arr, low, high);
            quick_sort(arr, low, pivot - 1);
            quick_sort(arr, pivot + 1, high);
        }
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);  // Create a Scanner object
        System.out.print("Enter the number of students (n): ");
        int n = scanner.nextInt();  // Read user input

        Student[] students = new Student[n];

        for (int i = 0; i < n; i++) {
            System.out.print("Enter name for student " + (i + 1) + ": ");
            String name = scanner.next();
            System.out.print("Enter mark for " + name + ": ");
            int mark = scanner.nextInt();
            students[i] = new Student(name, mark);
        }

        quick_sort(students, 0, n - 1);

        // Display names of M students with highest marks
        System.out.println("Students with the highest marks:");
        for (int i = 0; i < n; i++) {
            System.out.println("name is " + students[i].name + " mark is " + students[i].mark);
        }

    }
}