// 퀵정렬(quick sort) - 분할해결법 원리를 이용 ① 정렬 대상 자료에서 기준(피벗키, 제어키)을 선정한다. ② 기준값보다 작은 값은 앞쪽에, 큰값은 뒤쪽에 위치하도록 순차적으로 서로 교환한다. ③ 원래의 자료는 기준값을 중심으로 두 부분으로 나누어진다. ④ 나누어진 각 부분을 ①∼②처럼 반복하면서 정렬을 수행한다.
#define SIZE 9 #define SWAP(x, y, temp) (temp=x, x=y, y=temp) void quick_sort(int list[], int left, int right){ int pivot, a, b, temp, i; if(leftlist[a]); // 피벗보다 큰 값을 찾을 때까지 반복 do{ b--; }while(pivot
// 퀵정렬에서 피벗키(제어키) ㉠ 퀵정렬에서 피벗키는 임의 위치의 키를 사용할 수 있다. ㉡ 인덱스 a, b가 교차되었을 때는 피벗키와 a 또는 b가 가리키는 키와 교환하면 된다. •첫번째 원소를 피벗키로 사용하면 b가 가리키는 원소(작은값)와 교환되고 •마지막 원소를 피벗키로 사용하면 a가 가리키는 원소(큰값)와 교환된다. ㉢ 결론은, 교환 결과 리스트가 피벗키를 기준으로 양분되도록 하면 된다.
1. 키 값 1, 2, 3, 4, 5를 가지는 5개의 레코드로 이루어진 리스트를 퀵정렬(quick sort)로 오름차순정렬하고자 한다. 정렬 과정에서 총 비교횟수가 가장 많은 리스트는? (단, 피봇(pivot)은 정렬하고자 하는 대상의 첫 번째 레코드로 선택한다) [2020년 국가 7급] ① 1, 2, 3, 4, 5 ② 2, 3, 1, 4, 5 ③ 3, 1, 2, 4, 5 ④ 3, 1, 2, 5, 4
![Путин и ПЕСКОВ ждут звонка от ТРАМПА 😁 [Пародия]](/img/n.gif)
// 퀵정렬(quick sort) - 분할해결법 원리를 이용
① 정렬 대상 자료에서 기준(피벗키, 제어키)을 선정한다.
② 기준값보다 작은 값은 앞쪽에, 큰값은 뒤쪽에 위치하도록 순차적으로 서로 교환한다.
③ 원래의 자료는 기준값을 중심으로 두 부분으로 나누어진다.
④ 나누어진 각 부분을 ①∼②처럼 반복하면서 정렬을 수행한다.
2. 다음 정수 리스트를 퀵정렬 알고리즘으로 오름차순정렬할 때, 리스트를 처음 분할한 직후의 분할된 두 리스트의 상태로 옳은 것은? (단, 제어키는 5로 한다) [2017년 국회 9급]
---------------------------------
(5 2 6 4 7 3 8 1)
---------------------------------
① (5 2 6 4), (7 3 8 1)
② (2 4 3 1), (6 7 8)
③ (3 1 2 4), (7 6 8)
④ (3 2 1 4), (7 8 6)
⑤ (1 2 3 4), (6 7 8)
#define SIZE 9
#define SWAP(x, y, temp) (temp=x, x=y, y=temp)
void quick_sort(int list[], int left, int right){
int pivot, a, b, temp, i;
if(leftlist[a]); // 피벗보다 큰 값을 찾을 때까지 반복
do{ b--; }while(pivot
// 퀵정렬에서 피벗키(제어키)
㉠ 퀵정렬에서 피벗키는 임의 위치의 키를 사용할 수 있다.
㉡ 인덱스 a, b가 교차되었을 때는 피벗키와 a 또는 b가 가리키는 키와 교환하면 된다.
•첫번째 원소를 피벗키로 사용하면 b가 가리키는 원소(작은값)와 교환되고
•마지막 원소를 피벗키로 사용하면 a가 가리키는 원소(큰값)와 교환된다.
㉢ 결론은, 교환 결과 리스트가 피벗키를 기준으로 양분되도록 하면 된다.
1. 키 값 1, 2, 3, 4, 5를 가지는 5개의 레코드로 이루어진 리스트를 퀵정렬(quick sort)로 오름차순정렬하고자 한다. 정렬 과정에서 총 비교횟수가 가장 많은 리스트는? (단, 피봇(pivot)은 정렬하고자 하는 대상의 첫 번째 레코드로 선택한다) [2020년 국가 7급]
① 1, 2, 3, 4, 5 ② 2, 3, 1, 4, 5
③ 3, 1, 2, 4, 5 ④ 3, 1, 2, 5, 4