퀵 정렬

대표적인 분할 정복 알고리즘 으로 평균 속도는 

O(N*logN)이다 

삽입, 버블, 선택 보다는 훨씬 더 빠르다.

 

포인트는 특정한 값을 기준으로 서로 교환한 뒤에 배열을 반으로 나누는 것!

 

3 7 8 1 5 9 6 10 2 4 이런 배열이 있다면 가장 앞에 있는 3이 피벗값(기준값)이 된다. 

이것을 기준으로 오른쪽으로 가면서 자신보다 큰 값을 찾고 

배열의 끝 4부터는 자신보다 작은 값을 찾는다. 

찾았다면 서로의 위치를 바궈준다. 

3 2 8 1 5 9 6 10 7 4 

이렇게 피벗값은  변하지 않은 채로 이 과정을 반복해준다. 

3 2 1 8 5 9 6 10 7 4 

이 경우 엇갈렸다 라는 표현을 쓰는 데 배열 끝에서부터 피벗값보다 작은 값의 INDEX 값이 

오른쪽에서 피벗값보다 큰 값을 찾는 데의 INDEX 보다 작다 

즉 피벗값보다 작은 값이 오른쪽에서 더 가깝다는 소리다

이때는 그 작은 값을 피벗값과 위치를 바꿔준다. 

1 2 3 8 5 9 6 10 7 4

 이렇게 됐을 경우 3을 기준으로 왼쪽은 다 3보다 작고 오른쪽은 다 3보다 크다 

따라서 3을 기준으로 배열을 나누어 준다. 

1 2 3 , 8 5 9 6 10 7 4

파랑색은 각 배열의 피벗값이다. 

앞의 1 2 3의 경우 이미 정렬이 된 것이라 바뀌지 않는다. 

8 5 4 6 10 7 9 

8 5 4 6 7 10 9 => 엇갈림!!

7 5 4 6 8 10 9 => 그럼 8를 기준으로 배열을 또 분할해주고 분열된 배열의 첫번째값 7이 또다른 피벗값이 된다. 

7 5 4 6 의 경우도 엇갈리기 때문에 6 5 4 7 이 되고 피벗값이 7왼쪽으론 다 작기 때문에 멈춘다.

이 과정을 반복하다 보면 결국 오름차순으로 정렬된다. 

 

퀵정렬이  빠른 이유 

기존의 삽입, 선택, 버블 정렬의 경우 

1 2 3 4 5 6 7 8 9 10 을 비교하기 위해 

N * N=100번 비교를 한다. 

하지만  퀵정렬의 경우 

1 2 3 4 5 

6 7 8 9 10 으로 나누어 

5 * 5=25

5 * 5=25 

총 50번 비교를 하고 계속 2로 나누어 주기 때문에 log2n으로 계산하여 계산이 훨씬 빨라질 수 있다. 

 

이것을 코드로 나타내면 

 

그러나 만약 이미 정렬이 되어 있는 배열의 경우에는 

O(N^2)와 같은 시간 복잡도가 나온다. 

 

만약 내림차순으로 바꾸고 싶다면 18번과 21번만 바꿔주면 된다!!