퀵 정렬(Quick Sort)는 분할 정복 알고리즘으로 분류 되지만 정복 후 분할하는 알고리즘이다.
분할할때는 O(n)
합병 시 O(1)
분할 정복과 반대 이다.
퀵정렬은 피봇(pivot)이라는 배열의 원소(숫자)를 기준으로 피봇보다 작은 숫자들은 왼편, 피봇보다 큰 숫자들은 오른푠에 위치하도록 분할한다.
A[12] =ㅣ6ㅣ3ㅣ11ㅣ9ㅣ12ㅣ2ㅣ8ㅣ15ㅣ18ㅣ10ㅣ7ㅣ14ㅣ
피봇을 A[0]=6으로 선택했다고 해보자
ㅣ3ㅣ2ㅣ6ㅣ11ㅣ9ㅣ12ㅣ8ㅣ15ㅣ18ㅣ10ㅣ7ㅣ14ㅣ
피봇 6을 기준으로 6보다 작은것은 왼쪽에 , 6보다 큰것은 오른쪽에 가져다 놓았다.
'학교 공부 정리 > 컴퓨터 알고리즘' 카테고리의 다른 글
| 합병정렬 (0) | 2019.05.01 |
|---|---|
| 1-2임의의 숫자 찾기 (0) | 2019.05.01 |
| 1-1최대 숫자 찾기 (0) | 2019.05.01 |