정렬 - 퀵 정렬

UkJJang·2021년 9월 15일
0

퀵정렬

  • 기준점을 정해서 기준점보다 작은값은 왼쪽, 큰값은 오른쪽으로 모으는 함수를 작성한다.
  • 각 모은 왼쪽과 오른쪽에서 재귀를 이용해서 동일한 함수를 반복한다.
  • 함수는 왼쪽 + 기준점 + 오른쪽을 리턴한다.
import java.util.ArrayList;
import java.util.Arrays;

public class MyQuickSort {

    public ArrayList<Integer> Quick(ArrayList<Integer> dataList) {

        if (dataList.size() <= 1) {
            return dataList;
        }

        int pivot = dataList.get(0);

        ArrayList<Integer> leftArr = new ArrayList<>();
        ArrayList<Integer> rightArr = new ArrayList<>();

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


        ArrayList<Integer> mergedArr = new ArrayList<>();
        mergedArr.addAll(this.Quick(leftArr));
        mergedArr.add(pivot);
        mergedArr.addAll(this.Quick(rightArr));

        System.out.println(mergedArr);
        return mergedArr;
    }


    public static void main(String[] args) {
        MyQuickSort mySplitSort = new MyQuickSort();
        Integer[] arr = {1, 23, 4, 5, 6,7};
        mySplitSort.Quick(new ArrayList<Integer>(Arrays.asList(arr)));

    }
}
profile
꾸준하게 성실하게

0개의 댓글