분류 전체보기64 퀵 정렬 (Quick Sort) 퀵 정렬 퀵 정렬은 1) 분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 자랑합니다. 1) 분할 정복 분할 정복은 문제를 2개의 문제로 분리하여 각각 해결하고, 결과를 모아 원래의 문제를 해결하는 전략입니다. 퀵 정렬의 진행 과정은 다음과 같습니다. 데이터들의 배열에서 하나의 원소를 선택합니다. 선택된 원소를 피벗(pivot)이라고 부릅니다. 피벗을 기준으로 왼쪽에는 피벗보다 작은 값, 오른쪽에는 피벗보다 높은 값이 오도록 배열을 분할합니다. 피벗을 제외한 왼쪽 배열과 오른쪽 배열을 다시 정렬합니다. 더이상 분할이 불가능할 때까지 반복합니다. 퀵 정렬은 피벗을 기준으로 배열을 나누는 분할, 분할된 배열을 정렬하는 정복, 정렬된 분할 배열들을 다시 합치는 결합의 단계들로 이루어져 있습니다... 2021. 9. 13. 병합 정렬 (Merge Sort) 병합 정렬 병합 정렬은 1) 분할 정복 알고리즘의 하나로, 중복된 수의 입력된 순서와 정렬된 순서가 같은 안정 정렬입니다. 1) 분할 정복 분할 정복은 문제를 2개의 문제로 분리하여 각각 해결하고, 결과를 모아 원래의 문제를 해결하는 전략입니다. 병합 정렬은 하나의 배열을 두 개의 배열로 분할하고, 분할된 배열을 정렬한 후, 정렬된 두 개의 배열을 다시 결합하는 방식으로 정렬합니다. 병합 정렬은 다음과 같은 세가지 과정으로 진행됩니다. 분할(Divide) : 배열을 동일한 크기의 배열 2개로 분할한다. 정복(Conquer) : 분할된 배열을 조건에 맞게 정렬한다. 분할된 배열의 크기가 충분히 작지 않으면 재귀 호출로 다시 분할 정복 과정을 거친다. 결합(Combine) : 정렬된 배열들을 다시 결합한다... 2021. 9. 13. 삽입 정렬 (Insertion Sort) 삽입 정렬 삽입 정렬은 자신의 위치를 찾아서 삽입하여 정렬을 완성하는 알고리즘 입니다. 선택 정렬의 순서는 다음과 같습니다. 두 번째 자료에서 시작하여 앞의 원소들과 비교해 삽입할 위치를 정합니다. 삽입될 위치가 정해지면, 뒤쪽의 원소들을 한 칸씩 뒤로 이동시킵니다. 원소를 정해진 위치에 삽입합니다. 앞쪽의 원소들과 비교 후, 자신의 위치를 정하고 그 위치에 삽입하는 방법으로 정렬을 합니다. 시간 복잡도 최악의 경우 selection sort와 마찬가지로, $O(n^2)$의 시간 복잡도를 가집니다. 수식으로 나타내면 아래와 같습니다. $$ (n-1) + (n-2) + ... + 2 + 1 = {n(n-1)} / {2} $$ 그러나 모두 정렬이 되어 있는 경우, 한 번씩만 비교하기 때문에 $O(n)$의 시.. 2021. 9. 13. 선택 정렬 (Selection sort) 선택 정렬 선택 정렬은 데이터의 순서에 따라 위치는 이미 정해져 있고, 그 위치에 들어갈 원소를 선택하는 알고리즘입니다. 선택 정렬의 진행 과정은 다음과 같습니다. 먼저, 데이터들 중에 최소값을 찾습니다. 찾은 최소값을 맨 앞에 위치한 데이터와 교화합니다. 정렬된 맨 앞의 값을 제외하고 위와 같은 방식으로 데이터의 위치를 교환합니다. 선택 정렬은 버블 정렬과 반대로 회전마다 맨 앞의 데이터를 제외합니다. 선택 정렬은 n번의 회전 마다 n번째 데이터의 위치가 정해집니다. 시간 복잡도 선택 정렬은 버블 정렬과 마찬가지로 $O(n^2)$ 입니다. 한 번의 회전에 데이터 하나를 제외하기 때문에, 데이터가 n개 일 때, n-1 번의 순회가 필요합니다. 이를 수식으로 나타내면 아래와 같습니다. $$ (n-1) + .. 2021. 9. 10. 이전 1 ··· 9 10 11 12 13 14 15 16 다음
