본문 바로가기
반응형

분류 전체보기359

합병 정렬(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.
버블 정렬(Bubble Sort) 버블 정렬(Bubble Sort)는 배열 속의 모든 값을 비교해서 서로 자리를 바꾸는 알고리즘이다. 인접한 원소와 인접한 원소의 크기를 비교해서 자리를 바꾸는 알고리즘이다. ADL은 다음과 같다. bubbleSort(a[],n) for (i = 1; i 2021. 10. 22.
선택 정렬 선택 정렬(Selection Sort)은 매우 간단한 알고리즘이다. 가장 작은 숫자의 index를 선택하고 이를 배열의 맨 처음 값과 비교해서 자리를 바꾸는 것이다. ADL은 다음과 같다. selectionSort(a[],n) for (i 2021. 10. 22.
반응형

티스토리툴바