퀵소트는 우선 재귀로 이루어집니다.
중요 개념은 PIVOT입니다.
정렬할 배열을 생성합니다. 그후
퀵소트함수에 (배열, L, R)을 담아서 불러옵니다.
L은 정렬할 범위의 제일 좌측이고,
R은 정렬할 범위의 제일 우측입니다.
----------------------------------------------------------------
소트(배열, 0, 배열.length-1); //호출
소트(배열, L, R){ //퀵소트함수
if( L < R){
int pivot = 정복(배열, L, R);
소트(배열,L, 피봇-1); //피봇위치보다 좌측(작은값들) 정렬
소트(배열, 피봇+1, R); //피봇위치보다 우측(큰값들) 정렬
}else{
L이 R보다 크거나 같다.
}
}
--------------------------------------------------------------
소트에 들어가면 L과 R을 비교하여
L이 작으면 안의 정복 분할을 반복합니다.
재귀를 반복하면서 L이 R보다 크거나 같아지는데 이때 정렬이 마무리되고 퀵소트는 끝이 납니다.
여튼 처음시작을 하면 L은 0 R은 배열의 크기이므로 IF문안에 들어갑니다
제일먼저
정복(배열, L, R) 이 호출됩니다.
---------------------------------------------------------------
정복(배열, L, R){
int pivot = 배열[R];
int i = (L - 1);
for(int j = L; j<=R-1; j++){
if(배열[j] <= pivot){
i++;
swap(배열[i], 배열[j]); //두값을 바꾸는거인듯?
}
}
swap(배열[i+1], 배열[R]);
return (i+1);
}
----------------------------------------------------------------
정복에서 실질적인 정렬(L~R범위)을 하게됩니다.
pivot을 좌측에 둘수도있고 중간 랜덤 여러곳에 설정할수있지만 우측기준으로 해보겠습니다.
고로 pivot의 위치는 R, 정렬범위의 최우측입니다.
그후 i는 L - 1을 넣어줍니다. 제일처음기준으로 -1값을 가지게 됩니다.
pivot과 i값을 설정후 반복문에 들어가게 됩니다.
0 ~ R-1까지, 배열 처음부터 마지막한칸앞까지 j가 돌아갑니다.
돌아가며 배열[j]가 피봇값보다 크거나 작으면
i를 1추가하여 배열[i], 배열[j]를 바꾸어줍니다.
만약 j가 pivot보다 크면 -1였던 i를 1추가해줘 j번째 배열값과 i번째 배열값(최초스왑시 i = 0)
을 스왑해줍니다. 이렇게 R-1까지 반복하면 배열[0~i]은 모두 피봇보다 작은 값이 됩니다.
그리고 for문 탈출후 배열[i+1]과 배열[R]값을 바꾸게 됩니다.
그러면
---------------------------------------------------------------
배열[0 ~ i-1] <-i보다 작음, 정렬보장X
배열[i]
배열[i+1 ~ R] <- i보다 큼, 정렬 보장X
----------------------------------------------------------------
이 됩니다. 또 정복이 한번 호출될때마다 원소하나의 위치가 확정되어집니다.
int pivot = 정복(배열, L, R); 이므로
확정된 원소위치를 pivot에 담아줍니다.
소트(배열,L, 피봇-1); //피봇위치보다 좌측(작은값들) 정렬
소트(배열, 피봇+1, R); //피봇위치보다 우측(큰값들) 정렬
이제 무한반복입니다.
위에는 R값으로 피봇이 들어가게 되므로 계속 호출해주면
R값은 작아지다가
if( L < R) 조건을 못맞추고 끝이 납니다.
아래 소트는 L+1이여서 올라가다가 조건에서 터집니다.
퀵소트는 배열이 이미 정렬이 많이 되어있을수록 효율성이 떨어진다고 하네요
로그를 읽을줄모르므로 빅오는 다음에 공부해보겠습니다.
소트API는 뭐가있는지 몰라 다음 자료구조,알고리즘시간에 찾아서 써보겠습니다.
끝
댓글 0