728x90 반응형 Language-LAB/Algorithm14 [알고리즘] 기수 정렬(Radix Sort) 기수 정렬 삽입, 병합, 퀵 정렬등의 비교기반 정렬과 다르게 비교 연산을 하지 않는다 추가적인 메모리도 필요하다 즉, 공간을 희생하여 시간 효율을 높이는 방법 기수(Radix) 란 숫자의 자릿수이다 기수 정렬은 이러한 자릿수의 값에 따라서 정렬한다 다단계 정렬이며, 단계의 수는 데이터의 전체 자릿수와 일치 한 자릿수의 정렬 1. 항목들을 저장할 버킷들을 준비 2. 입력 항목들을 순서대로 킷값에 따라 해당 버킷에 넣음 3. 위쪽 버킷부터 순차적으로 버킷 안에 들어 있는 숫자를 출력 여러 자리 숫자의 정렬 먼저 낮은 자릿수로 정렬한 다음 차츰 높은 자릿수로 정렬 여러 자리의 숫자를 정렬하는 방법을 구체적으로 생각해보자 숫자를 십진법으로 나타내면 버킷은 10개를 사용 같은 숫자를 2진법으로 표현한다면 버킷 2.. 2023. 7. 9. [알고리즘] 힙 정렬(Heap Sort) 힙 정렬 최대 힙 트리나 최소 힙 트리를 구성해 정렬 내림차순 정렬을 위해서는 최대 힙을 구성 오름차순 정렬을 위해서는 최소 힙을 구성 오름차순의 힙정렬을 하고 싶다면 정렬해야 할 n개의 요소들로 최대 힙(완전 이진 트리 형태)을 만듬 최대 힙이므로 최상위 루트 노드가 가장 큰 값의 노드 가장 말단 노드가 가장 작은 값의 노드이다 최상위 루트 노드와 말단 노드를 교환하고 다시 힙 구조로 재배열 하는 형식!! 2023. 7. 9. [알고리즘] 셀 정렬(Shell Sort) 셀 정렬 정렬해야 할 리스트의 k번째 요소를 추출해서 부분리스트 만듬!! k를 간격(gap)이라 한다. k 초깃값 = (정렬할 값의 수) / 2 생성된 부분리스트의 갯수는 gap과 같다. k는 홀수로 설정하고, 짝수가 나오면 +1 해준다 각 셀 교환은 삽입정렬의 알고리즘을따른다. 2023. 7. 9. [알고리즘] 병합정렬 (Merge Sort) 병합정렬 분할 정복의 효과를 가장 잘 보여주는 대표적인 정렬 알고리즘 1.분할(Divide) : 입력 리스트를 같은 크기의 2개의 부분 리스트로 분할한다. 2.정복(Conquer) : 부분 리스트를 정렬한다 부분 리스트의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 기법 적용 리스트의 크기가 1이면 이미 정렬 된 것! 3.병합(Combine, merge) : 정렬된 부분 리스트들을 하나의 배열에 통합 알고리즘에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 병합하는 단계인 merge()이다 효율적인 병합을 위해서는 반드시 임시 리스트가 필요하다 병합은 각 부분 리스트의 첫 번째 항목부터 오른쪽으로 시작 두 부분 리스트의 항목 A[i] 와 A[j]를 비교하여 더 작은 요소를 먼저 새.. 2023. 7. 9. 이전 1 2 3 4 다음 728x90 반응형
