퀵정렬
분할 정복을 이용한 정렬알고리즘이다. 병합 정렬과 비슷하지만 퀵정렬은 pivot을 기준으로 이보다 작은 것은 왼쪽 큰 것은 오른쪽에 위치한다.
이 배열을 퀵정렬 해보자
1. 맨 왼쪽을 피벗으로 둔다. 그리고 피벗보다 큰 것을 왼쪽에서 부터 찾고 피벗보다 작은 것을 오른쪽에서 부터 찾는다.
왼쪽에서부터 찾게 되면 2는 피벗보다 작다. 그래서 그냥 넘어간다. 하지만 4는 피벗보다 크다. 이제 오른쪽에서부터 피벗보다 작은 것을 찾는다. 5,7,8은 그냥 넘어간다. 하지만 1은 피벗보다 작다. 이제 4와 1을 스왑한다.
2. 스왑 후 포인터를 옮긴다.
스왑 후 포인터를 옮긴다.
3. i > j면 종료한다.
더 이상 i는 피벗보다 작은 것은 없으므로 해당 포인터에서 종료한다. 반면에 j는 피벗보다 작은 것이 존재 한다. 하지만 이제 i가 j보다 크게 되므로 해당 파티션은 종료한다.
4. j와 피벗을 스왑한다.
여기서 보게 되면 pivot 기준으로 왼쪽은 작은 값 오른쪽은 큰값으로 되어 있다. 이제 left, right도 마찬가지로 pivot을 기준으로 나눈다.
5. left를 마찬가지로 퀵정렬 한다.
j가 i보다 크므로 종료한다.
6. right를 마찬가지로 퀵정렬 한다.
6을 피벗으로 하고 왼쪽부터 6보다 큰값을 찾는다. 바로 9가 있으므로 오른쪽에서 피벗보다 작은 값을 찾는다. 바로 5가 있으므로 둘이 스왑한다.
포인터를 옮긴다.
4는 피벗보다 작으므로 넘어간다. 하지만 8은 피벗보다 크다. 이제 j를 생각하자. 7은 피벗보다 크다. 그냥 넘어간다. 마찬가지로 8도 피벗보다 크다. 넘어간다. 하지만 4는 피벗보다 작으므로 멈춘다. i가 j보다 크므로 해당 파티션은 멈춘다.
알고리즘 코드
partition 함수는 i는 피봇보다 작은값이 있으면 넘어가고 큰값이 있으면 멈춘다. j는 피봇보다 큰값이 있으면 넘어가고 작은값이 있으면 멈춘다. j <= i라면 멈추고 그렇지 않으면 둘이 스왑한다.
마지막으로 j와 pivot값을 스왑하고 j를 리턴한다.(해당 j는 정렬이 된것이므로 이것을 기준으로 재정렬해야함)
quick_sort 함수는 pivot을 기준으로 왼쪽 오른쪽을 퀵정렬한다.
