정렬알고리즘
-
[간단 정리] 합병 정렬알고리즘/프로그래머스 2019. 11. 28. 17:21
* 오름차순 기준입니다 이름에서 알 수 있듯이 합병의 과정에서 데이터가 정렬되는 알고리즘이다. 합병하기 위해선 분할을 해야겠지? 합병 정렬은 분할 정복 알고리즘에 속한다. 연결 리스트로 구현하면 퀵 정렬을 포함한 어느 정렬 알고리즘보다 효율이 좋다고 하지만 배열로 공부했기 때문에 여기에선 배열을 사용한다. 최소 단위까지 분할을 하고 나서 합병하면서 대소를 비교해 정렬한다. 분할한다고 해서 매번 그 과정에 배열을 진짜로 나누진 않는다. 인덱스를 가지고 구간을 분할하며, 합병할 때 배열이 등장한다. 주어진 배열에 left, mid, right가 있을 때 분할하는 범위는 left ~ mid와 mid+1 ~ right이다. 나눠서 수행하며 재귀호출로 분할할 수 없을 때까지 분할한다. 즉 마지막까지 분할되면 왼쪽..
-
[간단 정리] 힙 정렬알고리즘/프로그래머스 2019. 11. 27. 21:10
* 오름차순 기준입니다 생각보다 쉽지 않았다. 처음에 개념을 잘못 잡는 바람에 완전히 이해하기까지 반나절 정도 걸렸다. 현상을 이해하는 방식이 꽤 자주 스스로도 특이하다고 느껴질 때가 있다. 친절하게 설명하려면 그림을 곁들여야 하는데, 바람은 언제나 텍스트만으로 마무리 짓는 것이다. 그러기 위해서는 두괄식으로 설명해야 할 듯하다. 힙은 자료구조로서 '키'의 우선 순위가 있을 때 유용하다. 기본적으로 완전 이진 트리다. 트리의 왼쪽부터 데이터가 삽입되기 때문에 배열을 이용하면 매우 편하다. 순차적으로 인덱스를 활용할 수 있기 때문. 데이터는 키를 통해 최대 힙 혹은 최소 힙으로 정렬한다. 최대 힙은 부모 노드가 자식 노드보다 크거나 같고, 최소 힙은 부모 노드가 자식 노드보다 작거나 같은 속성이다. 최대 ..
-
[간단 정리] 정렬 알고리즘(버블, 선택, 삽입)컴퓨터 과학/자료구조와 알고리즘 2019. 11. 26. 19:44
*오름차순 기준입니다 1. 버블정렬 첫 번째 자료부터 마지막 자료까지 인접한 자료끼리 비교해가면서 교환한다. 정렬이 되어 있지 않은 자료를 기준으로(최악) 최초에 n-1번, 그다음에 n-2번, 그다음에 n-3번, 이렇게 해서 최대 횟수는 1 + 2 + .. + (n-1) = n(n-1)/2이므로 시간복잡도는 O(N^2)이다. 최고, 평균, 최악의 경우 모두 O(N^2). 구현은 매우 간단하고 성능이 안 좋다. 교환할 때마다 3번의 임시복사가 일어나기 때문이다. >>구현 #include #include void BubbleSort(int arr[], int size); void Swap(int& value1, int& value2); void PrintArr(int arr[], int size); int ..