본문 바로가기
반응형

adl7

기수 정렬(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.
버블 정렬(Bubble Sort) 버블 정렬(Bubble Sort)는 배열 속의 모든 값을 비교해서 서로 자리를 바꾸는 알고리즘이다. 인접한 원소와 인접한 원소의 크기를 비교해서 자리를 바꾸는 알고리즘이다. ADL은 다음과 같다. bubbleSort(a[],n) for (i = 1; i 2021. 10. 22.
반응형

티스토리툴바