퀵정렬
정렬알고리즘 중에 가장 빠른 알고리즘 중 하나로
피벗과 그륩 개념을 이용하는 알고리즘 이라생각한다
여기서 피벗은 비교 기준이 되는 요소(배열의 인덱스)를 뜻한다
특정 배열의 요소(피벗의 값)가 어떤 점수를 나타낸다면
그 점수(피벗의 점수) 이상인 그룹과 그 점수 이하인 그룹
또는 초과 미만으로도 표현할 수 있겠다.
우선 가장 생각하기 쉬운 ' 그 점수(피벗의 점수) 이상인 그룹과 그 점수 이하인 그룹 ' 으로 생각해보자
다음과 같은 배열이 있다고 생각해보자
여기에 특정 포인터 3개를 줄건데 ( 가리키는 인덱스를 표현한거다)
pl : 왼쪽 인덱스
pr: 오른쪽 인덱스
피벗: pl + pr / 2 을 나타내는 인덱스
그렇다면 이런 표현이다
여기서 부터 개념이 시작되는데
arr[pl] 이 피벗의 값보다 이상인 값을 찾는다
arr[pr] 이 피벗의 값보다 이하인 값을 찾는다
위의사진에서는 바로 0번 인덱스와 8번 인덱스에서 바로찾았다
그렇다면 서로 교환해준다, 다음 그림과 같을 것이다
0번 인덱스의 값과 8번 인덱스의 값이 서로 교환 되었다
그리고 사진에 pl과 pr이 그 다음 조건을 만족하는 인덱스를 가르키고 있다
조건은 이거였다
arr[pl] 이 피벗의 값보다 이상인 값을 찾는다
arr[pr] 이 피벗의 값보다 이하인 값을 찾는다
마찬 가지로 찾았으니 교환하면, 다음 그림과 같을 것이다
3번 인덱스의 값과 6번 인덱스의 값이 서로 교환 되었다
그리고 다음 조건을 만족하는 인덱스를 가르키고 있다
그럼 다음그림과 같을 것 이다
pl이 피벗을 가리키고있어서
pl과 피벗이 같이 묶여서 pr이랑 자리가 바뀌었다
그리고 pl이 pr보다 크다 정확히 현재는 1만큼 더크다
(단, pl과 pr이 떨어진 거리가 1보다 크면 서로의 그륩에 중복이 발생할 것이다)
시작 인덱스 0, 종료 인덱스 8
pr, pl 가지고 나타내면 두가지 그륩을 얻을수 있다
하늘색 영역은 피벗이하의 값만 있다
연두색 영역은 피벗이상의 값만 있다 심지어 운이 좋게 완전한 정렬도 되었다
어쨋거나 피벗을 기준으로 거칠게는 정렬 된 것이다
이를 완전한 정렬을 이룰려면 계속 반복하면 된다
새로 구한 그룹을 다시 피벗을 설정하고 계속 재귀적으로 반복하는 것이다
정렬이 될것이다