[Algorithm] 퀵 정렬(Quick Sort)

퀵 정렬(Quick Sort)이란? 퀵 정렬은 정렬 알고리즘 중 하나로 일반적으로 O(nlogn)의 시간복잡도로 수행된다고 알려져 있습니다.

퀵 정렬은 분할 정복(Divide and Conquer) 방법을 기반으로 만들어진 정렬 알고리즘입니다. "퀵"이라는 이름은 시행될 경우 다른 로그선형시간 정렬 알고리즘 대비 빠르게 수행되기 때문에 붙은 이름입니다.

하지만, 최악의 경우에는 O(n2)의 시간복잡도가 필요해서 사용에 주의해야합니다. 원리 퀵 정렬은 분할 정복(divide and conquer) 방법을 기반으로 합니다.

알고리즘은 다음과 같은 단계로 진행됩니다. 피벗(Pivot) 선택: 배열에서 하나의 요소를 피벗으로 선택합니다.

파티션(Partitioning): 피벗을 기준으로 배열을 두 개의 부분 배열로 나눕니다. 피벗을 기준으로 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 이동시킵니다.

재귀적인 정렬: 각 부분 배열에 대해 재귀적으로 퀵 정렬을 수행합니다. 결합(Combine): ...

요청 처리 중입니다...

[Algorithm] 퀵 정렬(Quick Sort)

등록된 다른 글