한국어
메뉴

자료 구조와 알고리즘

(이름, 점수) 데이터 (A, 80), (B, 70), (C, 80), (D, 70)이 이 순서로 늘어서 있다. 점수의 오름차순으로 안정 정렬했을 때 이름의 순서는?

  1. AB, D, A, C
  2. BD, B, A, C
  3. CB, D, C, A
정답과 해설 보기

정답: A. B, D, A, C

안정 정렬에서는 키(여기서는 점수)가 같은 원소끼리는 정렬하기 전의 순서가 그대로 유지됩니다. 70점인 B와 D는 원래 순서대로 B, D, 80점인 A와 C도 원래 순서대로 A, C가 되므로 B, D, A, C입니다. 안정적인 정렬에는 버블 정렬, 삽입 정렬, 병합 정렬이 있으며, 선택 정렬, 퀵 정렬, 힙 정렬은 일반적으로 안정적이지 않습니다. 안정 정렬을 사용하면 먼저 이름순으로 정렬한 뒤 점수로 다시 정렬하는 식의, 여러 키에 의한 정렬을 할 수 있습니다.

이 분야 연습하기 분야로 돌아가기

자료 구조와 알고리즘의 다른 문제

  1. 퀵 정렬의 시간 복잡도가 O(n²)이 되는 전형적인 경우는?
  2. 병합 정렬에서 오름차순으로 정렬된 두 열 1, 4, 7, 9와 2, 3, 8, 10을, 맨 앞끼리 비교하여 작은 쪽을 출력하는 것을 반복하여 하나의 열로 합친다(병합한다). 한쪽 열이 비면 나머지는 비교하지 않고 그대로 출력한다. 비교 횟수는 몇 회인가?
  3. 이진 힙을, 루트를 a[0]으로 하는 배열 a[0], a[1], a[2], …에 위쪽 단부터 차례로 왼쪽부터 채워 저장한다. a[4]의 자식과 부모로 올바른 것은?
  4. 부모의 값이 자식의 값 이상이 되는 최대 힙을, 루트를 a[0]으로 하는 배열로 나타내고 있다. 힙 50, 30, 40, 10, 20, 35에 45를 추가한다. 맨 끝에 놓은 뒤 부모보다 큰 동안은 부모와 교환하는 조작을 수행한 후의 배열은?
  5. 이진 탐색 트리를 중위 순회(왼쪽 서브트리, 그 노드, 오른쪽 서브트리 순으로 방문한다)로 따라갔을 때, 방문한 노드의 값은 어떻게 늘어서는가? 값은 모두 서로 다르다고 한다.