[ALGORITHMS]문제 11 퀵정렬

문제 11

퀵정렬

리스트 안의 자료를 작은 수부터 큰 수 순서로 배열하는 정렬 알고리즘을 만들어 보세요

앞서 병합 정렬로 줄 세우기는 학생들을 일단 두 그룹으로 나눠 각각 병합 정렬을 한 후, 정렬된 두 그룹에 있는 학생들의 키를 다시 비교하여 한 줄로 합치는(병합) 과정이었습니다. 

이번에 배울 퀵정렬은 '그룹을 둘로 나눠 재귀호출'하는 방식은 병합 정렬과 같지만, 그룹을 나눌때 미리 기준과 비교해서 나눈다는 점이 다릅니다. 즉, 먼저 기준과 비교해서 그룹을 나눈 다음 각각 재귀호출하여 합치는 방식입니다.

1. 퀵정렬로 줄 세우기

1. 학생들에게 일일이 지시하는 것이 귀찮아진 선생님은 학생들이 알아서 줄을 서는 방법이 없을지 고민입니다. 그렇다고 열 명이나 되는 학생들에게 한번에 알아서 줄을 서라고 하면 소란스러울 것 같아 조를 나눕니다.

2. 열 명 중에 기준이 될 사람을 한명 뽑습니다. 기준으로 뽑은 태호를 줄 가운데 세운 다음 태호보다 키가 작은 학생은 태호앞에, 태호보다 큰 학생은 태호 뒤에 서게합니다

3. 기준인 태호는 가만히 있고, 태호보다 키가 작은 학생은 작은 학생들끼리 큰 학생들은 큰 학생들끼리 다시 키 순서대로 줄을 서면 줄 서기가 끝납니다.

2. 쉽게 설명한 퀵 정렬 알고리즘

퀵 정렬은 언뜻 굉장히 어려워 보이지만, 차근히 보면 쉽습니다

3. 일반적인 퀵 정렬 알고리즘

이번에는 입력 리스트 안에서 직접 위치를 바꾸면서 정렬하는 일반적인 퀵 정렬을 살펴 보겠습니다.

4. 알고리즘 분석

퀵 정렬의 계산 복잡도는 최악의 경우 선택 정렬이나 삽입 정렬과 같은 O(n^2)이지만, 평균적일 때는 병합정렬과 같은 O(nlogn)입니다 최악의 경우는 기준을 잘못 선택해서 그룹이 제대로 나뉘지 않은 경우를 말합니다.

*연습문제

11-1 지금까지 배운 네가지 정렬 알고리즘 말고도 훨씬 많은 정렬 알고리즘이 있습니다. 그 중 하나인 거품정렬(Bubble sort)을 줄 서기로 비유하면 다음과 같습니다. 다음 과정을 읽고 리스트 [2,4,5,1,3]이 정렬되는 과정을 알고리즘으로 적어보세요

1. 일단 학생들을 아무렇게나 일렬로 줄을 세웁니다

2. 선생님이 맨 앞에서부터 뒤로 이동하면서 이웃한 앞뒤학생의 키를 서로 비교합니다. 앞에 있는 학생의 키가 바로 뒤에 있는 학생보다 크면 두 학생의 자리를 서로바꿉니다.

3. 선생님은 계속 뒤로 이동하면서 이웃한 앞뒤 학생의키를 비교해서 필요하면 앞뒤학생의 위치를 서로 바꿉니다.

4. 모든 학생이 키 순서대로 줄을 설때 까지 이 과정을 반복합니다

답

읽어주셔서 감사합니다