- 가장 빠른 정렬 알고리즘 중 하나
- 피벗을 기준으로 배열을 더이상 분해할 수 없을 때까지(그룹 요소의 개수가 1개인 경우) 분해한다.
- 평균 시간 복잡도 : O(n logn)
- 최악 시간 복잡도 : O(n^2)
ex> 이미 정렬이 되어 있는 경우, 매번 단 하나의 요소와 나머지 요소로 나누어지는 경우
-> 이 때는 삽입정렬이 더 빠르다.
퀵 정렬 예시
start, end : 구간의 시작점과 끝점
pivot: 그룹을 나누는 기준점(인덱스가 아닌 들어있는 값임)
left, right: 인덱스 값
1. 가장 왼쪽에 있는 수(5)를 피벗으로 지정한다.
2. left부터 오른쪽으로 가면서 피벗보다 큰 값을 가진 인덱스 를 찾을 때까지 left의 값을 증가시킨다. ex> 7
3. right부터 왼쪽으로 가면서 피벗보다 작은 값을 가진 인덱스를 찾을 때까지 right를 감소시킨다. ex> 1
4. left와 right의 값이 각각 2, 4로 바뀐다.
5. 큰 값(right)과 작은 값(left)를 swap 해준다.
6. left와 right값을 조건에 맞게 또 움직인다.
7. left와 right값이 각각 4, 3으로 바뀐다.
-> 이번에는 엇갈림! (right가 left보다 왼쪽으로 감)
8. 엇갈린 후에는 왼쪽에 있는 값(right)과 피벗을 swap한다.
9. swap을 해주면 피벗이었던 5의 위치는 고정이 된다.
10. 이후 {4,2,1}, {7,6} 에 대해서 또 퀵 정렬이 실행된다.
11. 그룹의 요소의 개수가 1개가 될 때까지(start == end) 계속 퀵 정렬이 실행되며 분해된다.
12. 위와 같은 과정이 반복되면 오름차순으로 정렬이 완료된다.
public class quickSort1 {
static void swap(int[]a,int idx1,int idx2) {
int t=a[idx1];
a[idx1]=a[idx2];
a[idx2]=t;
}
// 중요 포인트!!! -> 안하면 index 범위 벗어나는 오류남.
// i) quickSort 재귀 쓰기전에 조건을 붙이던가
// ii) qucikSort 시작하자마자 if문을 넣던가
// 오름차순 정렬
private static void quickSort(int[]a,int start,int end) {
// 아래 두 줄 중요!!
if (start>=end)
return;
int left= start+1; // 피벗을 제외한 가장 왼쪽부터 시작
int right = end;
int pivot = a[start];
while(left<=right) { // left>right 되면 반복문 탈출!
while(left<=end && a[left]<pivot)left++; // left<=end 조건 완전 중요!
while(right>start && a[right]>=pivot)right--; // right>start 조건 완전 중요!
if(left<=right) swap(a,left,right); // 엇갈리지 않은 상태
}
if(start<end) {// 1로 쪼개질때까지
swap(a,start,right); // 왼쪽에 있는 것(엇갈린 후에는 right가 됨) 과 피벗을 바꾼다.
// 퀵 정렬 시작하자마자 if문으로 start<=end를 검사해주었기 때문에 바로 재귀만 써도 OK.
// if(start<right)quickSort(a,start,right-1); // 재귀
// if(left<end) quickSort(a,right+1,end);
quickSort(a,start,right-1); // 피벗 이전 집합
quickSort(a,right+1,end); // 피벗 이후 집합
}
return;
}
private static void printResult(int[]a,int n) {
for(int i=0;i<n;i++)
System.out.print(a[i]+" ");
}
public static void main(String[]args) {
Scanner kb = new Scanner(System.in);
int[]a= {5,2,7,4,1 };
int n=5;
quickSort(a,0,n-1); // 처음 인덱스 값과 마지막 인덱스 값을 인자로 넘긴다.
printResult(a,n);
}
}
quickSort 시작하자마자 나오는 if문과 while문에서의 left<=end 조건과 right>start 조건, 이 세가지 때문에 시간이 오래걸렸다.. 조건 빼먹지 말자.
댓글