퀵 정렬

지난 게시글과 이어지는 내용입니다

 

 

퀵 정렬 quick sort

 - 빠른 정렬 알고리즘

 - 배열의 원소를 나누어 계산하는 원리

 - 대표적인 분할 정복 방법 중 하나

 - 특정한 값을 기준으로 큰 숫자와 작은 숫자를 나눈다.

• 특정한 값 = 피벗 (pivot)
  • 보통 첫 번째 값으로 잡음

 

 과정

1. 피벗을 기준으로 왼쪽에서는 피벗보다 큰 숫자, 오른쪽에서는 피벗보다 작은 숫자를 고른다.
2. 자리를 바꿔준다.
3. 계속 수행한다.
4. 엇갈리는 상황이 온다면? → 왼쪽에 있는 값(작은 값)과 피벗을 바꾸어준다.
   • 엇갈린다 == 작은 값의 index가 큰 값의 index보다 큰 상황
5. 피벗이 정렬되면 다시 왼쪽 / 오른쪽 집합으로 나누어 정렬을 수행한다.

 - 즉 퀵 정렬은 분할한 뒤에 더하면 전체적으로 봤을 때 연산 횟수가 훨씬 줄어드는 원리를 이용한다 !

 - 평균속도 O(N*logN)

 

핵심

• 큰 값과 작은 값을 엇갈릴 때까지 반복해서 교체하기

•  이미 정렬이 되어 있는 경우 분할정복의 이점을 사용할 수 없으므로 O(N*N)의 함정에 빠질 수 있다는 단점