[정보][자료구조] 2021-A-05 퀵정렬(Quick sort)

<작성 방법>

◦ 배열 a의 값이 {43,87,15,32,29,76,65,1000}인 상태에서 quicksort(a, 7, 0, 6)을 호출하였을 때, 밑줄 친 ㉠이 1번째 수행될 때와 2번째 수행될 때의 출력 결과를 순서대로 쓸 것.

1번째 : 32 29 15 43 89 76 65

2번째 : 15 29 32 43 87 78 65 

 

◦ 배열 a의 값이 {43,87,15,32,29,76,65,1000}인 상태 에서 quicksort(a, 7, 0, 6)을 호출하였을 때, 밑줄 친 ㉡의 수행 출력 결과를 순서대로 쓸 것.

3 2 0 6 4

quicksort(a, 7, 0, 6) -> partition(a, 7, 0, 6) -> j=3 -> quicksort(a, 7, 0, 2); quicksort(a, 7, 4, 6), -> partition(a, 7, 0, 2);  j= 2; > j=2, quicksort(a, 7, 0, 1),quicksort(a, 7, 3, 2)  partition(a, 7, 0. 1)-> j=0, quicksort(a, 7, 0, -1), quicksort(a, 7, 1, 0); 

다시 위로 올라가서 quicksort(a, 7, 4, 6) partition(a, 7, 4, 6) -> J=6, quicksort(a, 7, 4, 5), quicksort(a, 7, 7, 6),  -> partition (a, 7, 4, 5); j=4, quicksort(a, 7, 4, 4), quicksort(a, 7, 5, 5);

 

이렇게 끝이 납니다.

천천히 풀어보니 시간이 엄청 오래 걸리네요. 

시험 시간에 이런 문제를 만나면 진땀 꽤나 날 것 같습니다. 미리미리 연습을 해서 10분 정도에 풀어내야겠습니다.