파이썬과 함께하는 자료구조) 7장 정렬 연습문제.

7장 정렬 연습문제..

# 이 책이 대학 교재로 쓰일 줄은 몰랐다.. 그래서 답지가 없었구나.

# 간단하거나 쉽게 풀수 있는 문제는 skip..

7.3 입력이 역으로 정렬되어있을때 동일 수행시간 정렬 알고리즘을 모두 고르시오.

- 입력이 역으로 정렬 = 큰수로 정렬되어있다 = 무조건 정렬을 한번은 해야한다

- 따라서 위의 경우엔 O(N^2)이므로 이 수행시간을 갖는 알고리즘을 찾으면 된다.

7.9 두개의 정렬 리스트를 하나로 합병하는 데 필요한 최소, 최대 횟수를 바르게 표현한 것은?

(단 리스트의 길이는 각각 M과 N이며 M>= N 이다)

- 최소의 경우엔 극단적인 경우를 생각한다

즉 N의 모든 원소가 M의 가장 첫번째(M에서 가장 작은 원소) 보다 작은 경우... 따라서 이 경우엔 N이다.

- 최대의 경우엔 당연히 모든 경우를 다 확인하는것 이므로 M+N이다. 단 이때!

M >=N인 상황에서 제일 마지막은 할 필요가 없으므로 -1을 해줘야 한다. 따라서 M+N-1이다.

7.14 안정한 정렬 알고리즘을 모아놓은 것을 고르시오.

- Stable 알고리즘을 검색하면 많이 나온다.

- 단 여기서 Selection sort가 왜 안정하지 않은지 다시한번 상기하려 한다.

Selection sort는 최소값을 정하고 n번 돌면서 더 작은 최소값을 찾은뒤 교체를 한다.

만약 4, 4, 5, 6, 2, 1, 0 의 리스트가 있다면

첫번째에 4를 min으로 하고 n회 돌고 난 뒤에 0과 교체 된다.

즉 0, 4, 5, 6, 2, 1, 4가 되는데 이때 두개의 4의 인덱스 순서가 바뀌게 된다.

7.22 입력크기가 클때 힙정렬이 캐시메모리를 비효적으로 사용하는 이유를 설명하시오.

- 메모리구조, 운영체계 등에 대한 깊은 이해가 없어서 100% 설명은 못하겠으나 이해한것을 바탕으로 한다.

- 캐시 메모리는 일종의 주소의 즐겨찾기, 미래의 쓸거 같은 주소를 더 가져오는 셈

- 그렇기에 주소들이 모여있어야 효율이 좋다(배열처럼)

- 힙정렬의 핵심은 root와 제일 마지막 node를 교환 한 후에 heap을 생성 하는 것

- 문제는 바로 root와 마지막 node가 바로 옆에 붙어 있는게 아니라는 것이다.

- 즉 입력 크기가 매우 크다면 root와 마지막 node는 매우 멀기 때문에 캐시 메모리를 비효율적으로 사용하게 된다.

그 외에 나머지 문제들은 전부 프로그램 작성이라... 이번 장에선 이정도만 기억하면 될듯 싶다.