1. 퀵 정렬(Quick Sort)
- 분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법이다.
- 속도가 log로 나온다면 연산해야할 횟수가 절반 혹은 1/n으로 줄어든다는 뜻으로 퀵 정렬의 속도는 O(NlogN)으로 매우 빠르다.
분석
-
리스트 안에 있는 중간 값을 선택한다. 이렇게 고른 값은 피벗(Pivot)이라고 한다.
-
피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 Left로 옮겨지고 피벗보다 큰 요소들은 모두 피벗의 Right로 옮겨진다.
-
피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다.
- 분할된 부분 리스트(Left,Right)는 재귀함수를 통해 다시 처음부터 1,2번 과정을 거친다.
-
부분 리스트들이 더 이상 분할이 불가능할 때까지 반복한다.
(리스트의 크기가 0이나 1이 될때까지 반복한다.)
재귀함수란?
- 함수가 직접 또는 간접적으로 자신을 호출하는 프로세스를 재귀함수라고 한다.
- 사용자가 설정한 종료시점을 도달하기 전까지 계속해서 자기 자신의 메서드를 반복한다.**
2. 퀵 정렬 - List 풀이
(1) 설계
(1) 부분 리스트들의 결과값을 저장하는 공간
public List<Integer> merge(List<Integer> left,List<Integer> mid,List<Integer> right){
List<Integer> answer = new ArrayList<>();
answer.addAll(left);
answer.addAll(mid);
answer.addAll(right);
return answer;
}- 부분 리스트를 더 이상 분할이 불가능하여 출력되는 결과값을 합치는 공간
- 데이터 저장 순서는 left → mid → right 순으로 저장함
(2) 재귀(반복되는) 부분
if(arr.size()<=1) return arr;- 재귀함수에서는 탈출부분을 꼭 만들어줘야 한다. 그렇지 않으면 무한반복을 하게 됨
- 현재 여기서는 리스트들이 계속해서 부분분할이 되고 있는데 Left , Right 리스트 모두 사이즈가 0이 되면 더이상 분할을 못하고 1이되면 비교를 하지못해 분할을 못하니 리스트의 사이즈가 1이하일때 종료시키고 현재 자신값을 반환한다.
int pivot = arr.get(arr.size()/2);- Left / Right를 구분하기위해 기준값이 필요하다.
- 기준값은 입력받은 리스트의 중간값을 기준으로 하여 연산을 절반만 할 수 있도록 함
for(int i=0; i<arr.size(); i++){
if(arr.get(i)<pivot){
left.add(arr.get(i));
}else if(arr.get(i)>pivot)
right.add(arr.get(i));
else
mid.add(arr.get(i));
}- 기준값을 기준으로 Left / mid / Right에 들어갈 숫자를 구분한다.
- 위에서 정한 pivot보다 작으면 Left로, 크면 Right로, 그 외의 경우면 mid에 저장한다.
return merge(sort(left),mid,sort(right));- 마지막으로 size가 0~1이 될때까지 반복하게끔 하기 위해 자기 자신 메서드를 호출하여 반복 후 merge로 값을 보냄
(2) CODE
// 재귀함수를 통한 퀵 정렬
public class QuickSort {
public List<Integer> merge(List<Integer> left,List<Integer> mid,List<Integer> right){
List<Integer> answer = new ArrayList<>();
answer.addAll(left);
answer.addAll(mid);
answer.addAll(right);
return answer;
}
public List<Integer> sort(List<Integer> arr){
// 재귀 탈출 조건
if(arr.size()<=1) return arr; // mid보다 값이 모두 작거나 커서 한쪽으로 쏠려 한쪽에는 아예 들어가지 않는 경우도 생기고
// 1개의 값만 들어가는 경우도 생긴다. 1개만 들어가면 더이상 비교를 할 수 없기에 1이하로 하여 재귀를 빠져나오도록 한다.
// 1. 기준값 뽑는 로직 구현
int pivot = arr.get(arr.size()/2); // index = 4 , arr[4] = 5
// 2. 기준값 기준으로 왼쪽 오른쪽으로 나누어 담는 로직 구현
List<Integer> left = new ArrayList<>();
List<Integer> right = new ArrayList<>();
List<Integer> mid = new ArrayList<>();
for(int i=0; i<arr.size(); i++){
if(arr.get(i)<pivot){
left.add(arr.get(i));
}else if(arr.get(i)>pivot)
right.add(arr.get(i));
else
mid.add(arr.get(i));
}
// list를 합치는 연산
return merge(sort(left),mid,sort(right));
}
public static void main(String[] args) {
int[] arr = {20,18,5,19,5,25,40,50}; // 8
List<Integer> al = new ArrayList<>();
for(int i =0; i<arr.length; i++){
al.add(arr[i]);
}
QuickSort q = new QuickSort();
System.out.println(q.sort(al));
}
}- 코드 구동 방식
1st
입력 값 : {20,18,5,19,5,25,40,50}
pivot = arr[4] = 5
left = {}
mid = {5,5}
right={20,18,19,25,40,50}
left값이 없으므로 mid값을 merge로 보내 answer 리스트에 저장
answer = [5,5]
right값으로 재귀 진행 - - - - 2st
2st
입력 값 :{20,18,19,25,40,50}
pivot = arr[3] = 25
left = {20,18,19}
mid = {25}
right = {40,50}
left값으로 재귀 진행 ---- 2st_(1)
2st_(1)의 재귀가 끝나면 mid값을 answer 리스트에 저장
answer = [5,5,18,19,20,25]
right값으로 재귀 진행 ---- 2st_(2)
2st_(1)
입력 값 : {20,18,19}
pivot = arr[2] = 19
left = {18}
mid = {19}
right = {20}
left와 right모두 1개씩 있으므로 더 이상 재귀 진행 불가
따라서 merge로 left -> mid -> right 순으로 값 전송하여 answer 리스트에 저장
answer = [5,5,18,19,20]
2st_(2)
입력 값 :{40,50}
pivot = arr[1] = 50
left = {40}
mid = {50}
right = {}
left는 1개만 있으므로 더 이상 재귀 진행 불가
따라서 merge로 left -> mid 순으로 값을 전송하여 answer 리스트에 저장
answer = [5,5,18,19,20,25,40,50]
3. 퀵 정렬 - Array 풀이
