힙 정렬 (Heap Sort) 힙은 완전 이진트리 기반의 트리형 자료구조로써 최댓값이나 최솟값을 찾아내기 위해 사용됩니다. 힙에는 최대 힙과 최소 힙이 존재합니다. 최대 힙은 부모 노드의 키가 자식 노드의 키보다 같거나 큰 완전 이진 트리이며 최소 힙은 자식 노드의 키가 부모 노드의 키보다 같거나 큰 완전 이진 트리입니다. 힙 구조 생성과 최대 힙 연산에 관해서는 아래 포스팅에서 자세히 설명하였으니 참고하시기 바랍니다. https://yjg-lab.tistory.com/143?category=932096 [자료구조] 우선순위 큐 (priority queue), 히프의 삽입과 삭제 우선순위 큐 (priority queue) 우선순위 큐는 우선순위를 가진 항목들을 저장하는 큐입니다. 일반적으로 큐는 선입선출..

STL sort() 함수 활용하기 STL이란 C++의 표준 템플릿 라이브러리(Standard Template Libirary)의 약자로써 C++프로그래밍을 위해 제공되는 기본 내장 라이브러리입니다. STL에는 기본 4가지 구성요소로 알고리즘, 컨테이너, 함수자, 반복자를 제공합니다. 그중에서 알고리즘 헤더에서 제공하는 sort() 함수에 대한 활용 방법입니다. #include #include // sort() 함수 사용을 위한 라이브러리 using namespace std; int main() { int a[8] = { 2, 4, 11, 8, 5, 9, 1, 13 }; sort(a, a + 8); for (int i = 0; i < 8; i++) cout

병합 정렬 알고리즘(Merge Sort) 병합 정렬은 데이터 배열을 정확히 반으로 나누고 나중에 합쳐서 정렬하는 방식입니다. 정확하게 5:5로 나누기때문에 피벗(Pivot)이 존재하지 않습니다. 8 2 6 5 1 4 2 7 위와 같은 수가 있을 때 수들을 오름차순하는 병합 정렬을 해보겠습니다. 8개의 데이터를 나눌 수 없을때까지 반으로 나누면 크기가 1인 배열로 나누어집니다. 8 | 2 | 6 | 5 | 1 | 4 | 2 | 7 나누는 과정이 끝났다면 이제 데이터를 2의 배수만큼 합치고 합치는 순간 각각을 정렬합니다. 1차 합 : 2 8 | 5 6 | 1 4 | 2 7 2차 합 : 2 5 6 8 | 1 2 4 7 3차 합 : 1 2 2 4 5 6 7 8 알고리즘 구현 // Algorithm Analysi..

퀵 정렬 알고리즘 (Quick Sort) 퀵 정렬은 특정 데이터를 기준으로 큰 데이터와 작은 데이터를 서로 교환한 후 배열을 두 집합으로 나누는 방식의 알고리즘입니다. 기준이 되는 특정한 데이터, 즉 기준점을 피벗(Pivot)이라고 하며 일반적으로 첫번째 원소를 먼저 피벗으로 지정합니다. 퀵 정렬 알고리즘은 한번 과정을 이해하면 어렵지 않은 알고리즘이기에 정렬 과정을 자세히 풀이하겠습니다. 4 9 1 6 11 10 3 15 2 13 위와 같은 수가 있을 때 수들을 오름차순하는 퀵 정렬을 해보겠습니다. 먼저 피벗 값은 4로 시작하여 4를 기준으로 왼쪽부터 큰 값을 찾고 오른쪽 부터 작은 값을 찾는 과정을 수행합니다. 4 9 1 6 11 10 3 15 2 13 4 2 1 6 11 10 3 15 9 13 큰 ..

삽입 정렬(Insertion Sort) 삽입 정렬은 필요할 때만 각 데이터를 적절한 위치에 삽입하는 정렬입니다. 무조건 위치를 교환하는 선택 정렬과 버블 정렬에 비해 다소 효율적이라고 볼 수 있습니다. 1 9 4 6 11 10 3 15 2 13 위와 같은 수가 있을 때 수들을 오름차순하는 삽입 정렬을 해보겠습니다. 삽입 정렬의 경우, 앞에 있는 원소들이 이미 정렬되어 있다고 가정합니다. 1 9 4 6 11 10 3 15 2 13 1 9 4 6 11 10 3 15 2 13 1 4 9 6 11 10 3 15 2 13 1 4 6 9 11 10 3 15 2 13 . . . 1은 앞의 원소가 없으므로 삽입할 위치가 없어 그대로 남습니다. 그 다음 원소인 9는 앞의 원소에서 대소를 비교하여 적절한 위치에 삽입할 수..

버블 정렬 알고리즘 (Bubble Sort) 버블 정렬은 옆에 있는 데이터와 비교하여 더 작은 값을 앞으로 보내는 정렬입니다. 1 9 4 6 11 10 3 15 2 13 위와 같은 수가 있을 때 수들을 오름차순하는 버블 정렬을 해보겠습니다. 먼저 배열의 맨 앞부터 두 수씩 비교합니다. 1과 9를 비교하여 1이 더 작으므로 1을 정렬합니다. 그 다음 9와 4를 비교하여 4가 더 작으므로 9와 4의 위치를 교환하고 4를 정렬합니다. 그 다음 9와 6을 비교하여 6이 더 작으므로 9와 6의 위치를 교환하고 6를 정렬합니다. 그 다음 9와 6을 비교하여 6이 더 작으므로 9와 6의 위치를 교환하고 6를 정렬합니다. 1 9 4 6 11 10 3 15 2 13 1 4 9 6 11 10 3 15 2 13 1 4 6 ..