IK.AM

@making's tech note


マージソート復習

🗃 {Programming/Algorithm/Sort/MergeSort}
🗓 Updated at 2014-03-04T23:19:31Z  🗓 Created at 2014-03-04T23:19:31Z   🌎 English Page

復習

import java.util.Arrays;
import java.util.Random;

public class MergeSort {

    public static void mergesort(int[] arr) {
        mergesort(arr, 0, arr.length);
    }

    static void mergesort(int[] arr, int i, int j) {
        // arrのうち、i <= x < jの区間をソートする
        if (j - i <= 1) {
            // ソート済み
            return;
        }
        int mid = i + (j - i) / 2;
        mergesort(arr, i, mid);
        mergesort(arr, mid, j);
        merge(arr, i, mid, j);
    }

    static void merge(int[] arr, int i, int mid, int j) {
        int size = j - i;
        int[] work = new int[size];
        System.arraycopy(arr, i, work, 0, size);

        int k = i;
        int p = 0;
        int q = mid - i;

        while (p < (mid - i) && q < size) {
            if (work[p] <= work[q]) {
                arr[k++] = work[p++];
            } else {
                arr[k++] = work[q++];
            }
        }

        while (p < (mid - i)) {
            arr[k++] = work[p++];
        }
        while (q < size) {
            arr[k++] = work[q++];
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[100];
        Random r = new Random(System.nanoTime());
        for (int i = 0; i < arr.length; i++) {
            arr[i] = r.nextInt(100);
        }
        System.out.println(Arrays.toString(arr));
        mergesort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

✒️️ Edit  ⏰ History  🗑 Delete