콘텐츠로 이동

11.12   연습 문제

11.12.1   개념 확인

1.   선택 정렬과 버블 정렬의 처음 몇 회전

배열 [4, 2, 5, 1, 3]이 주어진다. 다음은 모두 오름차순으로 정렬한다.

  1. 선택 정렬의 첫 두 회전을 따라가며 각 회전이 끝난 뒤의 배열을 적고, 어느 위치가 확정되었는지 설명하라.
  2. 버블 정렬의 첫 회전을 따라가며 배열 상태와 교환 횟수를 적고, 어느 위치가 확정되었는지 설명하라.
참고 답안

  1. 첫 두 회전은 다음과 같다.

    회전 배열 상태 설명
    1 [1, 2, 5, 4, 3] 가장 작은 원소 1을 첫 번째 원소와 교환
    2 [1, 2, 5, 4, 3] 값 2가 이미 인덱스 1에 있으므로 교환할 필요 없음

    이때 앞의 두 위치는 확정되었으므로, 이후에는 [5, 4, 3]에서 계속 최솟값을 선택하면 된다.

  2. 이웃한 원소를 차례대로 비교한다. 4와 2는 교환하고, 4와 5는 교환하지 않으며, 5와 1을 교환한 뒤 5와 3을 교환한다. 결과는 [2, 4, 1, 3, 5]이고 총 3번 교환한다. 가장 큰 원소 5가 배열 끝으로 이동했으므로 마지막 위치가 확정되었다.

2.   값이 같은 원소의 순서가 달라지는가

배열 \([2_a, 2_b, 1]\)에서 \(2_a\)와 \(2_b\)는 값이 같지만, 아래 첨자로 원래 순서를 표시했다.

  1. 선택 정렬의 첫 회전이 끝난 뒤의 배열을 적어 보자. \(2_a\)와 \(2_b\)의 상대적인 순서가 바뀌었는가?
  2. 버블 정렬의 첫 회전이 끝난 뒤의 배열을 적어 보자. \(2_a\)와 \(2_b\)의 상대적인 순서가 바뀌었는가?
  3. 앞의 두 결과를 바탕으로, 값이 같은 원소의 원래 순서를 유지하는 측면에서 두 정렬이 어떻게 다른지 설명하라.
참고 답안

  1. 선택 정렬의 첫 회전에서는 가장 작은 원소 1을 골라 첫 원소 \(2_a\)와 교환한다. 결과는 \([1, 2_b, 2_a]\)다. \(2_a\)가 \(2_b\) 뒤로 옮겨졌으므로 두 원소의 상대적인 순서가 바뀌었다.

  2. 버블 정렬은 먼저 \(2_a\)와 \(2_b\)를 비교한다. 두 값이 같으므로 교환하지 않는다. 이어서 \(2_b\)와 1을 비교하여 교환한다. 첫 회전이 끝나면 \([2_a, 1, 2_b]\)가 된다. \(2_a\)가 여전히 \(2_b\) 앞에 있으므로 상대적인 순서는 바뀌지 않았다.

  3. 이 예에서 선택 정렬은 값이 같은 원소의 원래 순서를 바꾼다. 버블 정렬은 왼쪽 원소가 오른쪽 원소보다 클 때만 이웃한 원소를 교환한다. 값이 같은 원소끼리는 교환하지 않으므로 원래의 앞뒤 순서를 유지할 수 있다.

3.   계수 정렬과 기수 정렬 비교하기

학교에서 자릿수가 8자리로 고정된 학번을 대량으로 정렬하려 한다. 다음에 답하라.

  1. 가장 낮은 자리부터 처리하는 기수 정렬은 총 몇 회전이 필요한가?
  2. 학번을 그대로 정수로 취급하여 계수 정렬을 하면, 사용하지 않는 계수 배열의 자리를 많이 마련하게 되는 이유는 무엇인가?
  3. 앞의 두 결과를 바탕으로, 8자리로 고정된 학번을 대량으로 처리하려면 계수 정렬과 기수 정렬 중 어느 것을 선택하겠는가? 이유도 설명하라.
참고 답안

  1. 학번은 8자리이므로 가장 낮은 자리부터 가장 높은 자리까지 총 8회전이 필요하다. 매 회전에서는 0~9에 따라 그룹을 나누기만 하면 된다.

  2. 학번 전체의 출현 횟수를 직접 세려면 가능한 모든 8자리 값에 대해 자리를 마련해야 한다. 하지만 실제 학생이 사용하는 학번은 그중 일부에 불과하므로, 계수 배열의 대부분은 계속 0으로 남는다.

  3. 기수 정렬을 선택해야 한다. ‘자릿수가 고정되어 있고, 각 자리에 올 수 있는 값은 10가지뿐’이라는 특징을 이용하면 안정적인 그룹 나누기를 8회 반복하는 것으로 충분하다. 계수 정렬에서 8자리 학번 전체를 정수 인덱스로 사용하면 실제로는 나타나지 않을 수많은 값에 대해서도 계수 배열의 자리를 마련해야 한다.

11.12.2   프로그래밍 연습

1.   병합 정렬로 배열 정렬하기

정수 배열 nums가 주어진다. 병합 정렬을 직접 구현하여 원소를 비내림차순으로 정렬한 뒤 반환하라. 언어에서 제공하는 정렬 함수를 호출하지 마라.

풀이 힌트
  1. 구간 길이가 1 이하면 이미 정렬되어 있다.
  2. 중간 지점에서 구간을 둘로 나누고 각각 재귀적으로 정렬한다.
  3. 두 포인터로 정렬된 두 구간을 병합한 뒤, 결과를 원래 배열에 다시 쓴다.

LeetCode

2.   계수 정렬로 정수 배열 정렬하기

정수 배열 nums와 음이 아닌 정수 \(K\)가 주어진다. 배열의 모든 원소는 \(0\) 이상 \(K\) 이하이다.

계수 정렬을 구현하여 비내림차순으로 정렬한 결과를 nums에 다시 쓰고 nums를 반환하라. 원소의 대소 비교로 순서를 결정하거나 언어에서 제공하는 정렬 함수를 호출하지 마라.

풀이 힌트
  1. 모든 원소가 0 이상 K 이하이므로 원소 값을 계수 배열의 인덱스로 바로 사용할 수 있다.
  2. 먼저 nums를 한 번 순회하면서 해당 위치의 계수를 1씩 늘린다.
  3. 이어서 계수 배열을 0부터 K까지 순회한다. 값 x가 나타난 횟수만큼 nums에 x를 연속해서 쓴다.
댓글로 의견이나 질문, 제안을 남겨 주세요