4 퀵 정렬

• 동작 원리: 기준 선택 → 기준에 맞춰 그룹 나누기 → 그룹별로 각각 정렬(재귀 호출)

• 계산 복잡도: 보통의 경우 O(n·logn)

5 거품 정렬

• 동작 원리: 앞뒤로 이웃한 자료를 비교 → 크기가 뒤집힌 경우 서로 위치를 바꿈

• 계산 복잡도: 보통의 경우 O(n²)

※ 참고로 이 책에서는 정렬을 설명할 때 입력 리스트 안에 같은 값이 여러 개 있는 경우는 생각하지 않고 단순히 값을 ‘크다’와 ‘작다’로만 비교하여 설명하였습니다. 하지만 정렬 알고리즘을 구현한 예제 프로그램은 리스트 안에 같은 값이 여러 개 있더라도 제대로 된 정렬 결과를 보여 줍니다.

예: 입력 [3, 2, 4, 5, 1, 3] → 출력 [1, 2, 3, 3, 4, 5]