병합 정렬이란 분할 정복 기법을 이용한 정렬기법 이다. 기본 개념은 일단 반으로나누고 나중에 합친다. 이것이 기본 개념이다. 시간 복잡도는 O(N*logN) 이다. 알고리즘 밑에 그림을 살펴보자 . 1. 초기 상태에서 더이상 반으로 나눌수 없을 때까지 계속 분할한다. 2. 그리고 다시 병합(merge) 할 때 크기를 비교하여 병합한다. 3. 병합을 모두 마무리하면 정렬이 완료된다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 ..

계수 정렬 이란 단순히 '크기 기준' 으로 세는 알고리즘이다. 범위가 한정되어있을때 가장 빠른 속도를 낸다. 시간 복잡도는 O(N) 이다. 알고리즘 1. 사실 알고리즘 이라고 할것도 없다. 2. 그냥 배열에서 해당 숫자의 갯수를 센다음 3. 작은 값부터 갯수만큼 출력하면된다 .. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #include int main(void) { int count[5] = { 0,0,0,0,0 }; int data[20] = { 2,3,4,1,3,5,4,2,1,3,2,4,5,1,2,3,5,4,2,3 }; // 반복문 한번으로 정렬 완료 for (int i = 0; i

힙정렬을 이해하기 위해서는 아래 3개의 정의를 알고 가야함 . 이진 트리 : 모든 노드의 자식이 2개 이하인 트리. 완전 이진 트리 : 데이터가 루트 노드 부터 시작해서 왼쪽 부터 빼곡하게 차있는 트리 형태 힙 (heap) : 완전 이진 트리의 일종으로 최댓값, 최솟값을 쉽세 추출 할 수 있는 자료구조 이다. 최대 힙 : 부모 노드가 자식 노드보다 큰 힙 최소 힙: 부모 노드가 자식 노드보다 작은 힙 힙 정렬 : 자료구조 '힙(heap)'을 이용하여 최대 힙 트리나 최소 힙 트리를 구성해 정렬 하는 방법 오름 차순으로 정렬 을 하기 위해서는 최대 힙을 사용하고 , 내림차순은 최소힙을 사용. 힙 정렬의 시간 복잡도는 O(N*log N) 이다. 정렬 순서 알고리즘 오름차순 기준 1. 현재 배열을 최대 힙구조..

퀵 정렬은 피벗이라는 기준 숫자를 정하여 기준숫자보다 작으면 왼쪽인덱스로 크면 오른쪽은덱스로 옮기는 방식으로 약간 분할정복 개념 으로 정렬을 한다. c++의 sort STL 은 퀵정렬을 사용하며 시간복잡도 O(NlogN)을 보장한다. 퀵정렬의 시간복잡도는 최악의 경우 O(N^2) 이지만 평균적으로 O(NlogN)을 보인다. 정렬 과정 밑줄친 숫자는 피벗 숫자이고 빨간색 숫자는 정렬이 완료된 숫자이다 알고리즘 1. 배열의 가장 왼쪽 에 있는 수를 피벗 으로 정함 2. 피벗기준으로 피벗보다 작은수는 왼쪽으로 큰수는 오른쪽으로 옮김 3. 피벗을 계속 갱신해주고 피벗을 이용하여 정렬한 숫자를 다시 1-2번과정을 통하여 정렬. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ..

삽입 정렬은 정렬이 필요한 경우에만 알맞은 위치에 삽입하며 정렬한다. 시간복잡도는 O(N^2) 으로 버블 정렬,선택정렬과 동일하지만 일반적으로 두개의 정렬보다 더 빠르다. 진행 과정을 살펴보며 이해하자. 정렬 과정 알고리즘 1. 앞의 회색은 정렬된 배열이고 빨간색 수는 정렬 할 수이다. 2. 빨간색수를 정렬된 배열 맨뒤부터 값을 비교하며 대상 인덱스의 숫자보다 크면 앞으로 이동 3. 2번 과정을 반복하다가 더이상 이동이 없을시 정렬이 완료된것. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 #include using namespace std; int main() { int arr[10] = { 1,10..

버블 정렬은 인접한 두 수를 비교하여 작은수를 앞으로 큰수를 뒤로 보내는 방법이다.(오름차순 기준) 정렬이 앞이아니라 뒤에서 부터 된다는 특징을 가진다. 시간 복잡도 : O(N^2) 정렬 과정 알고리즘 1. 첫번째 인덱스와 두번째 인덱스를 비교하여 큰수가 뒤로가게 교환한다. 2. 1번과정을 마지막 인덱스 까지 진행 3. 2번과정이 1번진행되면 가장 큰수가 뒤로 가기때문에 그다음 에는 마지막 인덱스-1까지 1-2 번 과정을 진행. 4. 정렬이 완벽해질때까지 진행. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 #include using namespace std; int main() { int arr..