연습문제 21-2

위키피디아에서 정렬 알고리즘(https://en.wikipedia.org/wiki/Sorting_algorithm)에 대해서 읽어보고 다음 질문에 답하자.

1. “비교 정렬”이란? 비교 정렬에서 최선/최악의 경우 증가 기준은 무엇인가? 다른 정렬 알고리즘의 최선/최악의 경우 증가 기준은 무엇인가?

2. 버블 정렬의 증가 기준은 무엇인가? 왜 버락 오바마는 “버블 정렬만큼은 아니라고 생각한다”라고 했는가?

3. 기수 정렬의 증가 기준은 무엇인가? 기수 정렬을 사용하기 위한 사전 조건은 무엇인가?

4. 안정 정렬(stable sort)이란 무엇이고, 실무에서는 왜 중요한가?

5. 이름이 알려진 최악의 정렬 알고리즘은 무엇인가?

6. C 라이브러리가 사용하는 정렬 알고리즘은 무엇인가? 파이썬이 사용하는 정렬 알고리즘은 무엇인가? 이들 알고리즘은 안정한가? 이 질문에 대답을 찾기 위해 구글을 검색해야 할 수도 있다.

7. 비교를 하지 않는 대다수 정렬도 선형인데, 파이썬은 왜 O(n log n) 비교 정렬을 사용하는가?