[7급 국가직 자료구조론 2017년 7번]

다음 자료에서 첫 행은 오름차순으로 정렬하기 위해 주어진 입력 값이고 마지막 행은 정렬이 완료된 후의 결과이다. 중간의 행들은 합병정렬(merge sort), 삽입정렬(insertion sort), 선택정렬(selection sort), 퀵정렬(quick sort) 알고리즘을 통하여 얻을 수 있는 중간 과정을 보여준다. 각 행에 사용된 정렬 알고리즘을 바르게 나열한 것은? (단, 퀵정렬에서 피봇은 가장 오른쪽에 있는 원소를 사용한다)

입력	21	41	15	25	21	37	45	9	23	18	36	4	11
㉠	9	15	21	21	25	37	41	45	23	18	36	4	11
㉡	4	9	11	15	18	37	45	41	23	21	36	21	25
㉢	15	21	21	25	37	41	45	9	18	23	4	11	36
㉣	4	9	11	25	21	37	45	41	23	18	36	21	15
결과	4	9	11	15	18	21	21	23	25	36	37	41	45

㉠ ㉡ ㉢ ㉣