LUNA's Archive

이번 시간에는 가장 이해하기 쉬운 정렬 알고리즘 중 하나인 선택 정렬에 대해 알아보겠다. 선택 정렬 알고리즘은 구현하기 굉장히 단순하지만 정렬시 많은 시간이 걸리는 비효율적인 방법이다. 선택 정렬? 선택 정렬 알고리즘이 어떻게 동작하는지 살펴보자. 먼저 정렬되지 않은 숫자들이 들어 있는 리스트와 정렬이 완료된 숫자들이 들어가는 리스트가 있다고 하자. 아래 그림과 같이 초기 상태에서 정렬된 리스트는 비어 있고 정렬되어야 할 숫자들은 모두 오른쪽 리스트에 들어 있다. 선택 정렬은 오른쪽 리스트에서 가장 작은 숫자를 선택하여 왼쪽 리스트로 이동하는 작업을 반복한다. 이것은 오른쪽 리스트가 공백 상태가 될 때까지 되풀이 된다. 위 설명에서는 두 개의 리스트로 나누어 설명했지만 실제로 선택 정렬을 구현하기 위해 ..

Data Structure & Algorithm 2019. 8. 21. 22:29

이번에는 평균적으로 매우 빠른 수행 속도를 보장하는 정렬 방법인 퀵 정렬에 대해 알아보겠다. 퀵 정렬(quick sort)? 퀵 정렬은 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법이다. 이 정렬 방법은 분할-정복법(divide and conquer)을 사용하고, 합병 정렬과 달리 리스트를 균등하지 않게 분할한다. 여기서 분할-정복법이란 문제를 작은 문제들로 분리하여 각각 해결하고 결과를 모아서 문제를 해결하는 전략이다. 그리고 분할-정복법은 대게 순환 호출을 이용하여 구현한다. 이제 퀵 정렬이 어떻게 이뤄지는지 살펴보자. 먼저 리스트 안에 있는 한 요소를 피벗(pivot)으로 선택한다. 여기서는 리스트의 첫 번째 요소를 피벗으로 하자. 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮기고 피벗보다..

Data Structure & Algorithm 2019. 8. 5. 19:48