본문 바로가기
반응형

자료구조15

기수 정렬(Radix Sort) 기수 정렬(radix sort)는 정렬할 원소의 키 값을 나타내는 숫자의 자리 수(10의 자리수, 1의 자리수 등)를 기초로 정렬하는 기법이다. 이는 80칼럼 punched card를 정렬시키거나 도서관 목록 카드 정렬과 같은 생활 응용에 많이 활용된다. 예를 들어 [437,123,234,578,351,625,543] 을 정렬하면 다음과 같다. 1단계(1의 자리 수 기준 정렬) : [351,123,543,234,625,437,578] 2단계(10의 자리 수 기준 정렬) : [123,625,234,437,543,351,578] 3단계(100의 자리 수 기준 정렬) : [123,234,351,437,543,578,625] 이에 따른 기수 정렬 ADL은 다음과 같다. radixSort(a[],n) for (k 2021. 10. 24.
계수 정렬(counting sort) 계수 정렬(counting sort)는 키가 일정한 범위, 예를 들어, 1부터 M 사이의 정수로만 이뤄져 있다는 사실을 알고 있을 떄 사용할 수 있는 방법이다. 예를 들어 M = 4 이고 a = [1,2,2,1,3,4,4,1] 일 때 count 라는 배열을 만들어서 각 원소의 개수를 저장한다. j 1 2 3 4 count[j] 3 2 1 2 그리고 이를 누적시켜서 저장한다. j 1 2 3 4 count[j] 3 5 6 8 다음으로 배열 a에서 원소들을 뒤에서부터 하나씩 가져와서 count 리스트에 있는 인덱스에 따라 빈 배열 b로 복사한다. a에서 b로 복사하고 나면 count에 있는 인덱스 값을 하나 감소시킨다. 마지막으로 배열 b에 있는 원소들을 배열 a로 복사한다. 이러한 process 의 ADL은.. 2021. 10. 24.
합병 정렬(Merge Sort) 합병 정렬(Merge Sort)는 기본 아이디어를 3단계로 나눌 수 있다. # 합병 정렬 Process 정렬해야 할 A라는 리스트 [6,2,8,1,3,9,4,5,10,7] 이 있다고 하자 1. A를 이등분하여 L = [6,2,8,1,3], R = [9,4,5,10,7]로 만든다. 2. L과 R을 각각 정렬한다. 3. L 과 R을 합병하여 정렬된 리스트 S = [1,2,3,4,5,6,7,8,9,10]을 만든다. 이를 ADL로 표현하면 다음과 같다. mergeSort(a[],l,r) if (r>l) then { m 2021. 10. 24.
퀵 정렬(Quick Sort) Quick Sort는 진짜 혼신의 힘을 다해서 정리할 것이다. 얘는 대학원 면접 단골 문제는 물론 지금까지 최고라고 또, 앞으로도 최고일거라는 호평을 받은 정렬 알고리즘이다. 퀵 소트는 분할과 정복으로 이루어진 알고리즘 중 하나이다. 따라서 매우 복잡하지만 성능만큼은 확실하다. ## Quick Sort process 1. 배열 a[l:r]에서 가장 오른쪽에 있는 원소를 pivot 이라고 선정한다. 피봇은 분할 원소이다. 2. 이 피봇을 기준으로 두개의 partition으로 분할한다. 그리고 이 파티션은 다음과 같은 성질을 따른다. - 분할 후 피봇은 a[i]로 들어가게 되는데, 이는 정렬 후 피봇이 들어가는 정확한 위치가 된다(즉, 정렬이 된다) - 왼쪽 파티션에 있는 원소 a[l] , ... a[i-1.. 2021. 10. 23.
쉘 정렬(Shell Sort) shell sort는 삽입 정렬의 단점을 보안하기 위해 고안된 알고리즘이다. 삽입 정렬은 처음부터 끝까지 다 검사하지만 이는 처음에 몇개의 서브리스트로 나누어 작업한 다음에 삽입 정렬을 수행하는 것이다. 여기서 일정한 간격 h 를 두고 서브리스트를 구성하게 된다. 보통 h는 h = 3h+1 로 구성한다. 이를 ADL 로 나타내보자 shellsort(a[],n) for (h 2021. 10. 23.
삽입 정렬(Insertion Sort) 삽입 정렬을 소개할 때 하는 설명들이 있다. 카드를 정렬하는 방법과 비슷하다. 예를 들어 원카드를 한다 생각해보자 패에 내 카드 5장이 들어있다. 모양은 모두 스페이스고, J K 3 9 7 로 구성되어있다. 이러면 어떻게 패를 정리할 것인가? 보통은 3을 하나 뽑고 맨 앞으로 놓는다. 그러면 3 J K 9 7 이 된다. 이런 식으로 정렬되는 것이 삽입 정렬이다. 이에 대한 ADL은 다음과 같다. insertSort(a[],n) for (i 2021. 10. 23.
반응형

티스토리툴바