프로그래밍60 [정렬] 힙 정렬 자료구조 연결 리스트 이진 트리 스택 큐 해시 정렬 버블 정렬 선택 정렬 삽입 정렬 퀵 정렬 힙 정렬 알고리즘 재귀 함수 너비 우선탐색(BFS) 깊이 우선탐색(DFS) 다익스트라 힙 정렬(Heap Sort) 힙 정렬은 완전 이진 트리의 조건을 만족해야한다. 완전 이진 트리란 마지막 LEVEL를 제외한 나머지 LEVEL의 노드가 모두 NULL이 아니여야하고 마지막 LEVEL은 왼쪽부터 채워져 있는 이진트리를 말한다. Heapify(최대힙 구성) 각 노드의 값이 자식노드(왼쪽, 오른쪽)보다 항상 큰값을 가진 이진트리를 만든다. 1번 노드부터 부모 노드와 비교하며 크면 교환해준다.(0번 노드까지) Heap Sort 마지막 노드와 0번째 노드를 교환하다. 마지막 노드를 제외한 나머지 노드로 최대힙을 구한다. 1.. 2020. 11. 17. [정렬] 퀵 정렬 자료구조 연결 리스트 이진 트리 스택 큐 해시 정렬 버블 정렬 선택 정렬 삽입 정렬 퀵 정렬 힙 정렬 알고리즘 재귀 함수 너비 우선탐색(BFS) 깊이 우선탐색(DFS) 다익스트라 퀵 정렬(Quick Sort) 퀵정렬은 이름 그대로 아주 빠른 속도를 자랑한다. 중앙값(Key)을 기준으로 왼쪽에는 작은값 오른쪽에는 큰값을 넣어주고 2파트로 나눠서 반복한다. 이처럼 큰 문제를 작은 문제로 나눠서 해결하고 이를 합치는 방법을 분할 정복이라고 한다. 퀵 정렬은 분할 정복을 이용한 정렬이다. 시간 복잡도 : O(n * log(n)) 소스코드 #define __main #ifdef __main #include #include #include #define MAX_SIZE 10 void Init(int arr[]) {.. 2020. 11. 10. [정렬] 삽입 정렬 자료구조 연결 리스트 이진 트리 스택 큐 해시 정렬 버블 정렬 선택 정렬 삽입 정렬 퀵 정렬 힙 정렬 알고리즘 재귀 함수 너비 우선탐색(BFS) 깊이 우선탐색(DFS) 다익스트라 삽입 정렬(Insertion Sort) 배열의 두번째 부터 끝까지 2~4을 반복한다. 선택된 값(Key)과 이전 배열들의 값을 비교한다. Key값이 작으면 한칸씩 오른쪽으로 쉬프트 해준다. Key값이 크면 다음 배열에 Key값을 넣어준다. 시간 복잡도 : O(n^2) 소스코드 #define __main #ifdef __main #include #include #include #define MAX_SIZE 10 void Init(int arr[]) { srand(time(NULL)); for (int i = 0; i < MAX_S.. 2020. 11. 9. [정렬] 선택 정렬 자료구조 연결 리스트 이진 트리 스택 큐 해시 정렬 버블 정렬 선택 정렬 삽입 정렬 퀵 정렬 힙 정렬 알고리즘 재귀 함수 너비 우선탐색(BFS) 깊이 우선탐색(DFS) 다익스트라 선택 정렬(Selection Sort) 배열 중 가장 작은 값을 찾는다. 배열의 첫번째 값과 교환한다. 첫번째 배열을 제외한 나머지 배열을 가지고 1~3을 반복한다. 시간 복잡도 : O(n^2) 소스코드 #define __main #ifdef __main #include #include #include #define MAX_SIZE 10 void Init(int arr[]) { srand(time(NULL)); for (int i = 0; i < MAX_SIZE; i++) { // 임의의 정수 입력 arr[i] = rand() .. 2020. 11. 6. 이전 1 2 3 4 5 ··· 15 다음
