[알고리즘] - 정렬 - 퀵 정렬

[01] 주어진 데이터를 퀵정렬 해보자.

A [] = {30, 35, 50, 45, 10, 20, 70}

먼저 퀵정렬이란 특정 원소를 기준으로 주어진 배열을 두 부분배열로 분할하고 부분배열에 대해 퀵정렬을

순환적으로 적용하는 분할 정복 알고리즘을 사용하여 정렬을 수행하는 방법입니다.

두 부분배열로 분할할 때 기준이 되는 특정 원소인 피벗으로 지정하는데 일반적으로는 첫 번째 요소(30)를 선택합니다.

그리고 피벗을 기준으로 배열을 분할합니다. 피벗보다 작은 요소는 왼쪽 배열, 큰요소는 오른쪽 배열에 배치합니다.

왼쪽 모든 값 < 피벗 < 오른쪽 모든 부분배열의 모든 값 이렇게 정렬하면

{10,20} 30 {35,50,45,70}

이렇게 정렬이 됩니다.

그러면 분할된 두 배열에 대해 퀵정렬을 순환적으로 적용해서 각 부분배열을 정렬합니다.

왼쪽 배열기준으로 먼저 설명드리자면 {10,20}은 피벗이 10이며

왼쪽 배열 없음, 오른쪽 배열 {20}이 됩니다.

오른쪽 배열 기준으로 생성된 배열 {35,50,45,75}은 퀵정렬 수행하여 피벗이 35가 되며

피벗 35, 왼쪽 배열 없음,, 오른쪽 배열 {50,45,75}가 됩니다.

다시 퀵정렬을 수행하면 피벗은 50이 되며

피벗 50, 왼쪽 배열 {45}, 오른쪽 배열 {75}가 됩니다.

단계가 모두 수행되면 분할된 작은 배열들은 각각 정렬되어

A [] = {10,20,30,35,45,50,70}

이 됩니다.

이 정렬된 작은 배열들은 다시 동일한 값으로 원래순서가 정렬되는 것이 아니라서 퀵정렬은 안정적인 정렬이 아닙니다.

퀵정렬은 피벗을 기준으로 분할과정을 거치기 때문에 동일한 값의 원래 순서가 유지되지 않고 비교하면서 찾기 때문에 비교정렬이면서, 데이터 외에 추가적인 공간을 필요로 하지는 않기 때문에 제자리 정렬 알고리즘으로 분류됩니다.