정렬(Sort) 알고리즘 - 퀵정렬 QuickSort (C#)

정렬 알고리즘 중 이번엔 퀵정렬(QuickSort)를 알아보겠습니다.

 

퀵 정렬은 하나의 기준(pivot)을 정해서 기준보다 작으면 왼쪽, 크면 오른쪽으로 보내면서 정렬하는 방식입니다.

우선 가운데 숫자를 기준으로 잡고 왼쪽과 오른쪽으로 나눕니다.

 

start인 8이 privot인 6보다 크기 때문에 오른쪽으로 가야하므로 교환대상입니다.

 

end인 1도 pivot인 6보다 작기 때문에 왼쪽으로 가야하므로 교환대상입니다.

이렇게 8과 1을 swap하였습니다.

 

그 후 교환대상이 나올때까지 Start와 End를 이동시켜줍니다.

 

다시 7과 5를 교환시켜주고 다시 이동을 하면

 

이번엔 6과 3이 교환대상입니다.

End와 Start가 지나치게되면 루프를 종료합니다.

 

그리고 Start를 pivot으로 파티션을 나누고 반복합니다.

위의 내용을 코드로 구현한 부분입니다.

실행하면 정상적으로 정렬이 진행되며, 어떻게 정렬이 일어나는지 확인 가능합니다.

 

확실히 Swap이 일어난 횟수가 저번 버블정렬보다 줄어든 모습을 확인할 수 있습니다.

 

감사합니다.