이야기박스

귀찮아서 미루고 미루다, 이제야 작성하네요이걸로 정렬은 끝나고 다른 알고리즘들을 다루어야겠습니다 ㅎㅎ정렬 알고리즘 전체 코드는 코드 게시판가면 있어요 (c++로 작성했음) § 퀵 정렬 (Quick Sort) 퀵 정렬 또한 분할통치법을 이용한 알고리즘입니다.퀵 정렬의 핵심은 피벗(Pivot) 입니다. 여기서 피벗이란?기준점입니다.무조건 이걸 피벗으로 써야한다! 하는 기준은 없고, 각자 편한대로 정해주시면 됩니다.단, 피벗에 따라 수행시간에 차이가 생길 수 있으니 그건 고려하면서.. 간단히 말하면 퀵 정렬은 이 피벗을 기준으로 작은 것은 왼쪽으로, 큰 것은 오른쪽으로 몰아 넣는 방식입니다. ○ 과정1. 분할 (divide)- LT (피벗보다 작은 원소들)- EQ (피벗과 같은 원소들)- GT (피벗보다 큰 ..

합병 정렬 힙 정렬과 같이 비교에 기초한 정렬이며 수행 시간은 O(n log n) 하지만, 우선순위 큐를 사용하지 않고 데이터를 순차적 방식으로 접근한다. 과정 1. 분할 : L을 n/2 사이즈의 L1, L2로 분할 2. 재귀 : L1, L2를 재귀적으로 정렬 3. 통치 : L1, L2을 단일 순서리스트로 합병 코드를 보면 눈에 확 들어온다 Alg mergeSort(L) if(L.size > 1 ) (L1, L2)

분할통치법이란?- 일반적인 알고리즘 설계 기법의 일종- 원래의 문제를 작은 부문제로 분할하고 각 부문제의 해결을 위임하는 것 다음 3가지 절차를 통해 진행1. 분할 (Divide)2. 재귀 (Recur)3. 통치 (Conquer) 분석재귀 알고리즘은 일반적으로 점화식을 통해 실행시간을 분석한다.하지만 점화식을 사용하지 않더라도 논리적 직관으로 실행시간을 유추할 수 있다. 응용분할통치법의 대표적 예로는 합병정렬과 퀵 정렬이 있다.이외에도 다양한 분야에서 사용되는 알고리즘 설계 기법이다.

§ 힙 (Heap): 내부노드에 키를 저장하면서 다음 두 가지 속성을 만족하는 이진트리--> 우선순위 큐의 ADT 의 하나 1. 힙 순서: 모든 내부노드 v에 대하여 key(v) >= key(parent(v)) 을 만족 ( 반대도 성립한다 )2. 완전이진트리 * 힙의 마지막 노드 : 높이를 h라 한다면, 깊이 h-1의 가장 오른쪽 내부노드* 힙의 높이는 O(log n)이다. ~ 완전 이진트리의 경우 ==> 완전 이진트리의 높이 증명 깊이가 1인 경우 - 최소 노드 2개

두 정렬 알고리즘 모두 Priority Queue의 개념을 이용합니다. § Priority Queue ADT란?데이터 항목이 자유롭게 삽입될 수 있는 저장소, 삭제는 키 값에 의해 결정된다.여기서 키란 가장 작은것 혹은 큰것 과 같이 기준을 제시해줌. 두 정렬을 요약하자면 아래와 같습니다.- 삽입 정렬은 리스트의 값이 자신의 위치를 찾아서 들어가는 것.- 선택 정렬은 주어진 위치에 알맞은 값을 찾아서 넣는 것. § 분석- 두 정렬 모두 O()의 전체적인 수행시간을 갖는다.- 기존의 리스트를 제외하면 O(1)의 추가 상수공간만 있으면 된다. § 간단한 C 구현 코드 #include #include #include #define SIZE100 void selection(int *arr); void inser..