1. 선택 소트 void selection_sort(int list[], int n) { int least=0, i=0, j=0; for (i = 0; i < n-1; i++) { least = i; for (j = i + 1; j < n; j++) { if (list[j] < list[least]) least = j; //가장 작은 값 찾기 } swap(list, i, least); } } 1) 인덱스 0 부터 n-1까지 차례대로 해당 인덱스에 올 i번째로 작은 값을 찾는다. 2) 이를 위해 내부 루프는 i보다 1큰 인덱스부터 시작하여 맨 끝 인덱스까지 본다. 선택 소트는 , 인접요소들 끼리 차례대로 정렬하는 것이 아니라, 앞의 인덱스에 있는 요소와 뒤의 랜덤의 요소 (가장 작은 값)을 정렬하는 것으로..
[자료구조 복습7] 우선순위 큐 - Heap 구현하기 / Heap Sort
'우선순위 큐'란 ? 우선순위큐는, 큐에 우선순위가 있는 것으로, 무작정 맨 앞의 값을 pop하는 것이 아니라, 가장 높은 우선순위의 값을 pop해주는 큐를 말한다. 이러한 우선순위 큐를 구현하는 가장 좋은 방법은 바로 'Heap'이다. 일반 배열이나, 연결리스트를 사용 할 수 있겠지만, 일반 배열/ 연결리스트를 사용할 경우, 값을 올바른 위치에 넣는 시간 혹은 정렬 시키는 시간이 O(n)이므로, 비효율적이다. 반면 heap는 O(log2N)의 시간 효율을 가지므로, 다른 방법보다 유리하다. 왜 heap가 O(log2N)의 시간효율을 갖는지 알기 위해서는 heap의 구현법을 알아보자. heap는 배열을 이용한 완전이진트리로 구현하게 된다. 완전 이진트리의 높이는 요소가 n개일 때 log2N이 된다. he..
[자료구조 복습6] 이진 탐색 트리 (Binary Search Tree)
이진탐색트리 (Binary Search Tree)란, 기존의 이진 트리가 변형된 형태이다 . 이는 말 그대로 '탐색'을 더 효율적으로 하기 위해 설계된 자료구조로, 맨 위 노드를 기준으로 왼쪽은 맨 위 노드보다 작은 데이터가, 오른 쪽은 맨 위 노드보다 큰 데이터가 삽입된다. 또한, 모든 subtree는 이진탐색트리이므로, 모든 subtree에도 이러한 법칙이 적용된다. 그러면 이진탐색트리의 cpp 코드를 하나씩 살펴보도록 하겠다. 1. 트리 노드 타입 class BSTNode { public: int key; BSTNode* left =NULL; BSTNode* right = NULL; }; 2. BST 클래스 class BST { public: BSTNode* root = NULL; void inse..