정렬

13장 속도를 높이는 재귀 알고리즘

컴퓨터 언어에는 대부분 내장 정렬 함수가 있어 사용자가 스스로 구현하는 데 드는 시간과 노력을 아껴준다. 컴퓨터 언어 중 대다수가 내부적으로 채택한 정렬 알고리즘은 퀵 정렬(quick sort)이다. 퀵 정렬은 재귀를 사용한 알고리즘으로, 그 동작 방식을 알아보며 재귀를 사용해 어떻게 알고리즘의 속도를 향상시키는지 배울 수 있다. 퀵 정렬은 매우 빠른 정렬 알고리즘으로 특히 평균 시나리오에서 매우 효율적이다. 최악의 시나리오(역순 정렬된 배열)에서는 삽입 정렬이나 선택 정렬과 성능이 유사하나 대부분의 경우에서는 훨씬 빠르다. 퀵 정렬은 분할(partitioning)이라는 개념에 기반한다. 1. 분할 배열을 분할한다는 것은 배열로부터 임의의 수, 즉 피벗을 가져와 피벗보다 작은 수는 피벗의 왼쪽에, 큰 수..