최씨네 블로그

Quick sort 퀵 소트는 분할정복을 이용한 정렬방식 중 하나로 이름처럼 빠른 정렬입니다. 퀵 소트의 방식은 이렇습니다. 1. 무작위로 기준이 되는 수(pivot)를 고릅니다. 2. 이 때 피벗보다 작은 수를 왼쪽으로 놓습니다. 3. 피벗보다 큰 수를 오른쪽에 놓습니다. 4. 왼쪽과 오른쪽에 놓인 각각의 배열을 다시 1번 과정부터 반복합니다. 다음 아래와 같은 그림으로 보면 이처럼 pivot은 정렬된 것으로 보고 피벗을 기준으로 나머지를 분할하여 다시 피벗을 구해 마지막 피벗하나를 구할때까지 반복하는 구조입니다. 그렇다면 시간 복잡도 어떠할까요? 일반적인 경우의 시간복잡도는 NlogN을 가집니다. 왜냐하면 실제 N개의 수가 있다고 합시다. 만약 피벗이 정말 잘 골라져서 N이 딱 절반씩 계속해서 나눠진..