프로그래밍/알고리즘8 [C언어 알고리즘] 정렬 (8) - 병합정렬 (Merge Sort) 병합정렬은 이미 정렬된 두 파일을 병합(Merge)하는 방식을 일반화한 것입니다. 병합정렬은 아주 자연스럽고 이해가 쉽고 빠른 속도를 가지는 정렬방식입니다. 병합정렬은 두 자료를 순차적으로 읽어가면서 비교 접근하는 방법으로 연결리스트(Linked-list), 테이프(Tape)같은 순차적 접근만이 용이한 자료구조나 기억장치에서 유용하고 유일한 정렬방법입니다. 병합정렬은 메모리내부(internal)정렬뿐 아니라 외부(external) 정렬에서도 사용합니다. 이번 포스팅에서는 하나의 배열을 최소 단위 (배열의 1개요소)부터 단위를 2배로 늘려가며 정렬하는 예제에 대해 공부합니다. 우선 병합정렬의 기본 의사코드(Pseudo code)를 보도록 하죠. 1. size = 1 2. size가 N보다 작을 동안 2.1.. 2020. 7. 21. [C언어 알고리즘] 정렬(7) - 기수정렬 (Radix sort) Radix란 수학에서 밑(Base)를 의미하는 진법 체계에서 기준이 되는 수를 의미합니다. 예를 들어 자연수 1234가 있다면 $$ 1234 = 1 \times 10^3 + 2 \times 10^2 + 3 \times 10^1 + 4 \times 10^0 $$ 으로 표현이 가능합니다. 어떤 진법을 사용해도 상관은 없지만 컴퓨터가 처리하기 좋은 이진법을 사용하여 설명을 드리겠습니다. 초기 데이터가 아래와 같을 때, l e a r n a l g o r i t h m 아래 그림은 문자를 세로로 정렬하여 이진수로 표기하여 맨 앞열은 문자를 세로로 배열한 내용이고, 7~0은 각 비트에 해당하는 이진수를 의미합니다. 최상위 비트(7bit)에서 최하위 비트(0 bit)까지 배열의 맨 앞문자('l')부터 비트 '1'인.. 2020. 7. 14. [C언어 알고리즘] 정렬(6) - 퀵정렬 (Quick Sort) 퀵정렬(Quick Sort)은 분할-정복(Divide and Conquer)전략을 사용하는 알고리즘으로 1960년 C.A.R Hoare에 의해 처음 고안되어 가장 널리 알려진 정렬 방법 중 하나입니다. 퀵정렬은 아주 빠른 속도를 낼 뿐 아니라 원리도 간단해서 많은 부분에서 응용되고 있습니다. 퀵정렬은 연속적인 분할(Partition)에 의해 정렬을 합니다. 여기서 분할은 축(Pivot)을 중심으로 왼쪽은 이 값보다 작은 값 오른쪽은 큰 값으로 배열한다는 의미입니다. 이렇게 축을 기준으로 분할된 왼쪽 오른쪽 부분을 다시 분할하여 분할된 크기가 1이 될 때까지 반복하여 정렬합니다. 퀵정렬의 의사코드를 보면 다음과 같습니다. 퀵정렬 (a, N) 1. N > 1 이면 1.1. N크기의 배열을 분할 (Partit.. 2020. 7. 13. [C언어 알고리즘] 정렬(5) - 쉘정렬(Shell sort) 삽입정렬(Insertion sort)은 이미 정렬되어 있는 경우나 대충 정렬되어 있는 경우 좋은 성능을 보이지만 그렇지 않은 경우 속도가 매우 느립니다. 왜냐면 삽입정렬은 인접한 요소와 비교를 하기 때문인데 역순으로 배열된 경우 가장 작은 값이 맨 뒤에 있으므로 배열의 크기만큼 비교와 이동을 해야해서 비효율적입니다. 쉘정렬(Shell sort)는 이런 문제점을 개선하기 위해 일정 간격으로 떨어진 값을 삽입하여 정렬하는 방법으로 점진적으로 해결하는 형태입니다. 예를 들어 간격이 10이라면 0, 10, 20, 30...의 요소를 뽑아 이 요소간의 삽입정렬을 합니다. 다음으로 1을 더해 1, 11, 21, 31...의 요소 간 삽입정렬을 하는 식으로 반복하여 9, 19, 29, 39 ...의 요소를 마지막으로.. 2020. 7. 11. [C언어 알고리즘] 정렬(4) - 거품정렬(Bubble sort) 이번 시간은 거품정렬(Bubble sort)입니다. 거품정렬은 인접요소(Adjacent element)를 비교하여 교환하는 모습이 마치 거품이 보글보글 하는 모양이라서 붙은 이름입니다. 거품정렬의 의사코드(Pseudo code)는 다음과 같습니다. 거품정렬 알고리즘 1. i=0 2. i가 n-1이면 끝낸다 2.1 j=1 2.1.1 j가 n-i가 되면 2.2로 간다. 2.1.2 a[j-1] > a[j]이면 두 값을 교환 2.1.3. j를 하나 증가 시키고 2.1로 돌아간다. 2.2. i를 하나 증가 시기코 2로 돌아간다. j가 n-i까지 반복하는 이유는 n-i이후는 이미 가장 큰 값들로 정렬이 되어 있는 상태이기 때문입니다. 첫 번째 수행은 다음과 같습니다. 첫 번째 수행에서 값을 교환하여 배열의 가장 마.. 2020. 7. 9. [C언어 알고리즘] 정렬(3) - 삽입정렬 (Insertion sort) 삽입정렬(Insertion sort)은 선택정렬(Selection sort)와 함께 많이 사용되는 아주 간단한 정렬 방법입니다. 카드 뭉치로 예를 들자면, 이미 정렬된 카드패에 새로운 카드를 다른 항목사이에 끼워넣는 것으로 생각하시면 됩니다. 삽입정렬 알고리즘 우선 삽입 정렬의 의사코드(Pseudo code)를 보면 다음과 같습니다. 1. i=1 2. j=i 3. a[j-1] > a[i] 이고 j > 0인 동안 3.1. a[j] = a[j-1] 3.2. j-- 4. a[j] = a[i] 위 코드를 보면 배열에서 i번째 미만은 이미 정렬된 상태이며 i번째 항을 적절한 위치에 삽입하는 과정을 반복합니다. 그림을 통해서 살며보면 우선 다음과 같은 문자 배열이 있다고 가정을 합니다. 첫 번째 수행 시작은 i가 .. 2020. 7. 8. 이전 1 2 다음
