分割征服

学習内容

問題をいくつかの部分に分けて再結合して答えを得るポリシーです.

連結ソート

クイックソート

Arrays.asList関数
関数

は、所定のパラメータを有するリスト

を生成する.

Arrays.asList(4,1,2,3,5,7,1,13,0,3,5)

連結ソート

分割征服ポリシーの使用

SplitとMergeに分けて実施

各ステップの時間複雑度O(n)は,高さlog nであるためO(n log n)

import java.util.ArrayList;
public class MergeSort {
    public ArrayList<Integer> mergeFunc(ArrayList<Integer> left, ArrayList<Integer> right) {
        ArrayList<Integer> mergeList = new ArrayList<>();
        int leftPoint = 0;
        int rightPoint = 0;

        // left/right 존재
        while(left.size() > leftPoint && right.size() > rightPoint) {
            if (left.get(leftPoint) <= right.get(rightPoint)) {
                mergeList.add(left.get(leftPoint));
                leftPoint++;
            } else {
                mergeList.add(right.get(rightPoint));
                rightPoint++;
            }
        }

        // left만 존재
        while(left.size() > leftPoint) {
            mergeList.add(left.get(leftPoint));
            leftPoint++;
        }

        // right만 존재
        while(right.size() > rightPoint) {
            mergeList.add(right.get(rightPoint));
            rightPoint++;
        }

        return mergeList;
    }
    public ArrayList<Integer> mergeSplitFunc(ArrayList<Integer> dataList) {
        //base
        if (dataList.size() <= 1) {
            return dataList;
        }

        int middle = dataList.size() / 2;
        ArrayList<Integer> left = new ArrayList<>();
        ArrayList<Integer> right = new ArrayList<>();

        // 나누고
        left = mergeSplitFunc(new ArrayList<>(dataList.subList(0, middle)));
        right = mergeSplitFunc(new ArrayList<>(dataList.subList(middle, dataList.size())));

        // 정렬
        return this.mergeFunc(left, right);
    }
}

クイックソート

ピボットの使用(Use Pivot)

時間的複雑さのデフォルトはO(n logn)ですが、最悪はO(n)です.

pivot値を最適化するために他のアルゴリズムを実装する必要がある

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

public class QuickSort {
    public ArrayList<Integer> splitFunc(ArrayList<Integer> dataList) {
        if (dataList.size() <= 1) {
            return dataList;
        }

        int pivot = dataList.get(0);
        ArrayList<Integer> left = new ArrayList<>();
        ArrayList<Integer> right = new ArrayList<>();

        for (int i = 1; i < dataList.size(); i++) {
            if (pivot < dataList.get(i)) {
                right.add(dataList.get(i));
            }else {
                left.add(dataList.get(i));
            }
        }

        left = this.splitFunc(left);
        right = this.splitFunc(right);

        ArrayList<Integer> result = new ArrayList<>();
        result.addAll(left);
        result.addAll(Arrays.asList(pivot));
        result.addAll(right);

        return result;
    }
}