퀵 정렬 (Quick Sort)

• 특정 값 기분으로 큰 숫자와 작은 숫자를 서로 교환한 뒤 배열을 반으로 나눈다.
• 일반적으로는 가장 빠른 정렬이지만 거의 정렬이 되어있는 경우는 최악의 시간 복잡도가 나올 수 있다. (이경우 삽입 정렬 사용)
• 중간 정도 위치 수가 정렬이 되어있을 경우 가장 빠르게 정렬이 가능하다.
• 선택, 버블, 삽입은 데이터가 10만 개만 넘어도 사용하기 어렵다

퀵정렬 방법

1. 왼쪽에서 오른쪽으로 이동 시에는 피벗보다 더 큰 값을 찾는다
2. 오른쪽에서 왼쪽으로 이동 시에는 피벗보다 더 작은 값을 찾는다
3. 찾은 수의 자리를 바꾼다.
4. 계속 바꾸다 작은 값과 큰 값이 서로 엇갈린 상황이 온다면 작은 값과 피벗의 자리를 바꾼다.
5. 자리를 바꾼 피벗을 기준으로 왼쪽은 피벗보다 작은 값 들이고 오른쪽은 피벗보다 큰 값 외 위치하게 된다.

단점

• 정렬이 거의 되어있는 경우에는 N * logN을 보장할 수 없다.
• 같은 숫자들을 정렬할 경우 순서가 섞일 수 있다는 겁니다.

시간복잡도

최악 : O(N ^ 2)
최고 : O(N * logN)

• 정렬을 두개 그룹으로 분리하기 때문에 10개의 배열이라고 한다면
  5 5 = 25, 5 5 = 25 => 25 + 25 => 50이 된다

  코드

  github/quickSort