덕's IT Story

힙정렬(Heap Sort)은 힙(Heap)이라는 특수한 자료구조를 사용하는 정렬 알고리즘이다. 힙은 최소힙(Minimum Heap)과 최대힙(Maximum Heap)이 있는데 값이 저장되는 방향만 반대일 뿐 성질은 똑같다. 우선 힙(heap)에 대해서 설명하면, 힙은 이진트리(Binary Tree)로서 맨 아래 층을 제외하고는 완전히 채워져 있고 맨 아래층은 왼쪽부터 꽉 채워져 있다(nearly complete binary tree). 힙은 최소힙, 최대힙에 따라 다음의 성질을 가지고 있다. 최소힙(minimum heap)의 성질각 노드의 값은 자신의 자식의 값보다 작다. 최대힙(maximum heap)의 성질각 노드의 값은 자신의 자식의 값보다 크다. 위의 그림은 최대힙(maximum heap)의 예를..

선택정렬(Selection Sort)는 원리가 가장 간단한 정렬 알고리즘 중의 하나다. 우선 배열 A[1...n]에서 가장 큰 원소를 찾아 이 원소와 배열의 맨 끝자리에 있는 A[n]과 자리를 바꾼다. 그러면 방금 맨 뒷자리로 옮긴 원소, 즉 가장 큰 원소는 자기 자리를 찾았으므로 더 이상 신경쓰지 않아도 된다. 이 원소는 정렬이 끝났다고 볼 수 있으므로 이제 이 원소를 제외한 나머지 원소들로 같은 작업을 반복하면 된다. 간결하게 나타내면 각 루프마다최대 원소를 찾는다.최대 원소와 맨 오른쪽 원소를 교환한다.맨 오른쪽 원소를 제외한다.하나의 원소만 남을 때까지 위의 루프를 반복한다. 예를 들면, 정렬하고자 하는 배열(Initial array)에서 가장 큰 수(37)을 찾아 배열의 맨 끝 원소인 13과 자..