quick sort

quick sort

---

• quick sort는 분할 정복(Devide and Conquer) 알고리즘의 하나이다. 
• 분할과 병합의 두 단계로 나눌 수 있다.
  • 분할 : 리스트 안에서 pivot(기준)을 잡는다. 지정된 pivot을 기준으로 잡아 pivot보다 작은 요소들은 모두 pivot의 왼쪽 리스트로 옮겨지고 pivot보다 큰 요소들은 모두 pivot의 오른쪽 리스트로 옮긴다. 분할된 왼쪽 리스트와 오른쪽 리스트는 재귀 호출을 통하여 다시 분할 단계를 거친다.
  • 병합 : 분할 과정을 거쳐 더 이상 쪼갤 수 없는 크기까지 분할되었다면 정렬이 완료된 리스트를 차례로 병합을 진행한다.  그리고 최종적으로 정렬된 리스트가 완성된다.

 

알고리즘 이해하기

---

[3, 9, 4, 2, 1]라는 데이터를 가진 배열이 병합정렬되는 과정은 이하와 같다.

1. 3을 pivot으로 잡아 작은 값을 왼쪽 리스트로 큰 값을 오른쪽 리스트로 분할

2. 2를 pivot으로 잡아 왼쪽 리스트와 오른쪽 리스트로 분할(2보다 큰 수가 없기 때문에 오른쪽 리스트는 없음)

 

3.  더 이상 분할을 진행할 수 없으므로 병합

4. 9를 pivot으로 잡아 왼쪽 리스트와 오른쪽 리스트로 분할(9보다 큰 수가 없기 때문에 오른쪽 리스트는 없음)

5. 더 이상 분할은 진행할 수 없으므로 병합

6. 모든 요소의 리스트가 정렬되었기 때문에 최종적으로 정렬된 모든 리스트를 병합

 

quick sort 구현해 보기

---

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;

public class QuickSort {

    public ArrayList<Integer> quickSort(ArrayList<Integer> quickArr) {
        if (quickArr.size() < 1) {
            //size가 0일 경우는 분할 할 리스트가 없으므로 그대로 return
            return quickArr;
        }

        Integer pivot = quickArr.get(0);

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

        for (Integer num : quickArr) {
            if (num < pivot) {
                //pivot보다 작은 경우는 왼쪽리스트
                leftArr.add(num);
            } else if (num > pivot) {
                //pivot보다 큰 경우는 오른쪽리스트
                rightArr.add(num);
            }
        }

        ArrayList<Integer> mergeArr = new ArrayList<>();
        //재귀호출로 배열 내용을 크기순으로 정리. return된 리스트는 크기순으로 정리된 리스트
        mergeArr.addAll(this.quickSort(leftArr));
        mergeArr.addAll(new ArrayList(Arrays.asList(pivot)));
        //재귀호출로 배열 내용을 크기순으로 정리. return된 리스트는 크기순으로 정리된 리스트
        mergeArr.addAll(this.quickSort(rightArr));

        return mergeArr;
    }

}