컴퓨터 언어에는 대부분 내장 정렬 함수가 있어 사용자가 스스로 구현하는 데 드는 시간과 노력을 아껴준다. 컴퓨터 언어 중 대다수가 내부적으로 채택한 정렬 알고리즘은 퀵 정렬(quick sort)이다. 퀵 정렬은 재귀를 사용한 알고리즘으로, 그 동작 방식을 알아보며 재귀를 사용해 어떻게 알고리즘의 속도를 향상시키는지 배울 수 있다. 퀵 정렬은 매우 빠른 정렬 알고리즘으로 특히 평균 시나리오에서 매우 효율적이다. 최악의 시나리오(역순 정렬된 배열)에서는 삽입 정렬이나 선택 정렬과 성능이 유사하나 대부분의 경우에서는 훨씬 빠르다. 퀵 정렬은 분할(partitioning)이라는 개념에 기반한다. 1. 분할 배열을 분할한다는 것은 배열로부터 임의의 수, 즉 피벗을 가져와 피벗보다 작은 수는 피벗의 왼쪽에, 큰 수..
어떤 문제 해결을 위해 여러 알고리즘 중 하나를 선택할 때는, 모든 시나리오를 고려하는 능력이 필요하다. 1. 삽입 정렬 버블 정렬과 선택 정렬의 시간 복잡도는 O(N^2)으로 같지만 실제 실행되는 단계 수는 선택 정렬이 두 배 적다. 즉, 두 배 빠르다. 6장에서는 삽입 정렬에 대해 배우면서 최악의 시나리오가 아닌 다른 시나리오를 분석하는 것에 어떤 장점이 있는지 알아본다. 삽입 정렬의 수행 순서 첫 번째 pass through에서 두 번째 셀의 값을 삭제하고 이 값을 임시 변수에 저장한다. 삭제한 공간은 공백으로 남는다. 공백 기준 왼쪽의 값과 차례대로 비교하여 올바른 위치에 임시 변수의 값을 삽입한다. 두 번째 pass through는 세 번째 셀의 값을 삭제하고, 위의 pass through를 반..
빅 오는 알고리즘을 비교하고 주어진 상황에 알맞은 알고리즘을 결정하게 해 주는 좋은 도구이지만, 유일한 도구는 아니다. 1. 선택 정렬 선택 정렬의 시퀀스 배열의 각 셀을 왼쪽에서 오른쪽으로 확인하면서 어떤 값이 최솟값인지 판단하고 가장 작은 값을 기록한다. 최솟값과 pass through를 시작했을 때의 값을 교환한다. pass through를 반복한다. 2. 선택 정렬 실제로 해보기 & 3. 선택 정렬 구현 (Kotlin) fun main() { selectionSort(arrayOf(10, 9, 4, 6, 7, 8, 3, 2, 11, 1)).forEach { print("$it ") } } fun selectionSort(arr: Array): Array { for (i in arr.indices)..
