삽입 정렬의 개선

이 정렬(sorting)되고 있다. 여기서 숫자가 키(key)이고, 알파벳 정보는 단지 레코드와 함께 수반되는 것이다.

7. [13] 알고리즘 D(Algorithm D)는 안정 정렬(stable sort) 방법인가?

8. [15] 알고리즘 D에서 단계 D5에서 j가 N부터 1까지 감소하는 대신 1부터 N까지 증가하더라도 여전히 올바르게 작동하는가?

8. [15] 알고리즘 D에서 단계 D5에서 j가 N부터 1까지 감소하는 대신 1부터 N까지 증가하더라도 여전히 올바르게 작동하는가?

9. [23] 프로그램 C(Program C)와 연습문제 4에 유사한 알고리즘 D를 위한 MIX 프로그램을 작성하라. N과 (v - u)의 함수로서 프로그램의 실행 시간은 얼마인가?

10. [25] N개의 값 (R₁, ..., Rₙ)을 각각 (Rₚ₍₁₎, ..., Rₚ₍ₙ₎)로 대체하는 효율적인 알고리즘(algorithm)을 설계하라. 단, R₁, ..., Rₙ의 값과 {1, ..., N}의 순열(permutation) p(1) ... p(N)이 주어진다. 추가 메모리 공간의 사용을 피하도록 하라. (이 문제는 주소 테이블 정렬 후 메모리에서 레코드를 재배열하고자 할 때 발생하는데, 2N개의 레코드를 저장할 충분한 공간이 없는 경우이다.)

10. [25] N개의 값 (R₁, ..., Rₙ)을 각각 (Rₚ₍₁₎, ..., Rₚ₍ₙ₎)로 대체하는 효율적인 알고리즘(algorithm)을 설계하라. 단, R₁, ..., Rₙ의 값과 {1, ..., N}의 순열(permutation) p(1) ... p(N)이 주어진다. 추가 메모리 공간의 사용을 피하도록 하라. (이 문제는 주소 테이블 정렬 후 메모리에서 레코드를 재배열하고자 할 때 발생하는데, 2N개의 레코드를 저장할 충분한 공간이 없는 경우이다.)

11. [M27] 연습문제 10의 알고리즘에 대한 MIX 프로그램을 작성하고 그 효율성을 분석하라.

12. [25] 리스트 정렬(list sort, 그림 7)이 완료된 후 레코드 R₁, ..., Rₙ을 정렬된 순서로 재배열하기에 적합한 효율적인 알고리즘을 설계하라. 추가 메모리 공간의 사용을 피하도록 하라.