반응형 분류 전체보기340 [알고리즘] Sort - 힙정렬(heap sort) - 1 Sort - 힙정렬(heap sort) - 1 어원인지 모르겠지만 쌓아놓은 더미가 heap의 사전적 의미이다. 이번시간에는 힙 정렬에 대해서 알아보자힙 정렬은 힙, 바이너리 힙, 이진 힙이라고 부르는 자료구조를 이용하는정렬 알고리즘이다.(여기서 힙은, 메모리 영역인 힙과는 다른 말이다) 힙 정렬의 특징은 다음과 같다.1)최악의 경우에도 시간 복잡도가 nlogn이 되는 빠른 정렬이다.2 )힙 정렬은 알고리즘을 구현하는데 추가 배열이 필요하지 않다.3) 힙 이라는 자료구조를 이용해서 정렬을 한다. 따라서 알고리즘을 구현하기 앞서, 힙 이라는 자료구조에 대해알아보도록 하자 힙(Heap)은 1) complete binary tree 이면서2) heap property를 만족해야 한다. complete binar.. 2017. 4. 19. [알고리즘] Sort - 퀵정렬(Quick sort) Sort - 퀵정렬(Quick sort) 퀵 정렬은 합병 정렬과 동일하게 분할정복법을 사용하나방법에서 차이를 보인다. 퀵 정렬에서는 정렬할 데이터가 주어지면하나의 값을 기준값(pivot)으로 사용하여 정렬을 실행한다.어떤 값을 기준값으로 잡는냐가 퀵정렬 성능의 관건이다. 1) 분할하나의 값을 피봇으로 선정 한 후, 데이터들을 피봇보다 큰 값과 작은값으로 분류한다.그렇기 때문에 합병정렬과 같이 반으로 갈라지는 것을 보장하지 않는다.그렇기 때문에 기준값에 따라 최악/최선의 상황이 나뉜다. 2) 정복분할한 양쪽을 각각 재귀로 퀵 정렬한다. 3)합병할일이 없다.이미 분할과 정복 과정에서 정렬이 완료되었기 때문이다. 위의 과정들을 표현한 그림이다.파티션 후에는 재귀적으로 정렬해주면 되기때문에결국 퀵 정렬에서 중요.. 2017. 4. 19. [알고리즘] Sort - 합병정렬(Merge sort) Sort - 합병정렬(Merge sort) 앞서 비교적 간단하지만 효율적이지 않은 정렬 방법을 살펴보았다그 다음으로 합병 정렬과 퀵, 힙 정렬에 대해 알아보자 그 중에 합병과 퀵 정렬은 분할정복법이라는 동일한 정렬을 사용하는 알고리즘이다 분할정복법이라는것은예를들어, 한 나라가 다른 나라를 정복할때 한꺼번에 침략하지않고조금씩 영토를 쪼개어 각각을 하나씩 정복 하는것과 비슷한 것이다.영어로는 divide and conquer라고 한다. 좀 더 간단하게 말하자면 주어진 문제를 3단계에 걸쳐서 해결하는것이다그 순서는 다음과 같다. 1단계(분할)해결하고자 하는 문제를 작은 크기의 동일한 문제로 분할한다. 2단계(정복)각각의 작은 문제를 해결한다 3단계(합병)작은 문제의 해를 합하여(merge) 원래 문제에 대한.. 2017. 4. 19. [알고리즘] Sort - 기본적인 정렬 알고리즘(선택,삽입,버블) Sort - 기본적인 정렬 알고리즘(선택,삽입,버블) 컴퓨터 알고리즘의 가장 기본이 되는 것이 정렬 알고리즘이다.그 종류는 여러가지가 있는데 위와 같은 특징이 있다. 이 중에서 3개의 기본적인 정렬 알고리즘을 살펴 보자 선택 정렬 먼저 선택정렬이다이중에서 가장 큰 값을 찾는다그 후에 가장 큰 값과 맨 마지막 값의 자리를 바꾼다.그럼 결과적으로 가장 큰값이 맨 끝자리로 오게 된다. 그렇다면 마지막 값에 대해서는 더이상 신경쓰지 않아도 된다.이후에 남아있는 4개의 데이터에 대해서다시 가장 큰 값을 찾아 4번째 위치에 있는 값과 자리를 바꿔 준다. 이와 같은 알고리즘을 마지막 1개의 값이 남을 때까지 반복해준다면결론적으로 오름차순, 작은값을 맨 끝자리로 보내면 내림차순의 순서로정렬이 가능하다. 12345678.. 2017. 4. 19. 이전 1 ··· 57 58 59 60 61 62 63 ··· 85 다음 반응형
