웅재의 코딩세상

Quick Sort와 함께 대표적으로 사용되는 빠른 정렬 알고리즘이다. 시간 복잡도는 O(n log n)을 가진다. 합병 정렬은 3가지의 과정을 가진다. 분할 N 길이의 배열은 N / 2 길이의 배열 2개로 분할 시켜 나간다. 정복 부분 배열의 크기가 충분히 작아질 때까지 재귀 호출을 반복한다. 그 후 부분 배열을 정렬한다. 결합 정렬된 부분 배열을 결합하여 완성된 배열을 만들어 낸다. 구현하기 define MAX_SIZE 20 int arr[MAX_SIZE]; int *arr2; void merge(int left, int right){ int mid = (left + right) / 2; int i = left; int j = mid + 1; int k = left; while(i &arr[i]; m..

분할 정복 패러다임을 기반으로 한 정렬 알고리즘이다. 배열에서 pivot을 정한 후 pivot보다 작은 수를 왼쪽으로, 큰 수를 오른쪽으로 놓는 과정을 재귀적으로 수행한다. 각 부분 수열의 pivot(기준)을 정한다. pivot을 정할 때 중앙에 가까운 값을 선택하여 비슷한 크기로 분할될 수록 성능이 좋아지지만, 여기서는 구현의 편리함을 위해 맨 처음 수를 pivot으로 정한다. 기준에서 작은 수를 왼쪽으로, 큰 수를 오른쪽으로 가게끔 수열을 분해한다. 시간복잡도 퀵 정렬에서 대부분의 시간을 차지하는 것은 수열을 pivot 값을 기준으로 부분 수열로 나누는 과정이다. 두 부분의 수열이 비슷한 크기로 나눠질 수도 있겠지만 아닐수도 있기 때문에 기준 값이 수열의 최소값이나 최대값일 경우 부분 수열의 크기가 ..

삽입정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입하는 알고리즘이다. 매번 비교할 때마다 앞 부분에 해당하는 범위 모두 타겟값과 비교하여 해당 원소를 삽입할 수 있는 위치를 찾아 배열 위치에 넣는다. 특징 구현이 간단하다. 배열의 사이즈가 커질 수록 효율성이 떨어진다. 선택 정렬이나 버블 정렬과 같은 O(n^2) 알고리즘에 비해 빠르고 안정된 정렬이다. 추가적인 공간을 필요로 하지 않는다. 데이터를 서로 교환하기 때문에 임시 변수가 필요하다. 시간 복잡도 best 이동없이 한번씩만 비교할 경우 O(n) worst 비교할때마다 i번씩 비교 O(n^2) 구현하기 void print(vector v, string s); void insertion_..

맨 왼쪽 원소부터 이웃한 오른쪽 원소와 비교해가며 큰 수가 오른쪽으로 가도록 교환하는 정렬방식이다. 두 인접합 원소를 비교하는 것이 핵심이다. 시간 복잡도 : O(n^2) 5개의 숫자를 정렬한다고 하면 n = 5 라고 둔다. 첫 번째 비교에서는 n-1번 비교를 한다. 두 번째 비교에서는 n-2번 비교를 한다. 비교를 할 때마다 정렬되지 않은 숫자들 중 최댓값이 가장 오른쪽에 배치되기 때문에 1번씩 줄게 된다. 구현하기 vector bubble_sort(vector target){ int n = target.size(); int temp; for( int i = 0; i target[j+1]{ temp ..