끄적끄적 코딩
article thumbnail
[자료구조] Heap Sort (힙 정렬)
자료구조 2021. 2. 12. 19:34

개념 최대 힙 트리나 최소 힙 트리를 구성해 정렬하는 방법 추가적인 메모리를 필요로 하지 않음 항상 O(n log n)정렬의 성능을 발휘 퀵정렬이 힙정렬보다 일반적으로 빠르게 동작 데이터의 순서가 바뀌는 불안정 정렬 1. 원소들을 전부 힙에 삽입 2. 힙의 루트에 있는 값은 남은 수들 중에서 최솟값(혹은 최댓값)을 가지므로 루트를 출력하고 힙에서 제거 3. 힙이 빌 때까지 2의 과정을 반복 시간복잡도 (Worst Case = Best Case = Average Case) O(n log n) 예제 코드 void heapify(int arr[], int n, int i) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left < n ..

article thumbnail
[자료구조] Merge Sort (합병 정렬)
자료구조 2021. 2. 11. 18:31

개념 분할정복 알고리즘 기법을 사용해서 배열을 작게 나누어 분할한뒤 다시 합치는 (병합, 합병하는) 방식의 정렬 퀵 정렬보다는 성능이 떨어짐 데이터 크기만한 메모리가 필요함 안정적 정렬 n-way 합병 정렬 1. 정렬되지 않은 리스트를 각각 하나의 원소만 포함하는 n개의 부분리스트로 분할 2.부분리스트가 하나만 남을 때까지 반복해서 병합하며 정렬된 부분리스트를 생성 마지막 남은 부분리스트가 정렬된 리스트 2-way 합병 정렬 1. 리스트의 길이가 1 이하이면 이미 정렬된 상태 2. 분할(divide) : 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눔 3. 정복(conquer) : 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬 4. 결합(combine) : 두 부분 리스..

article thumbnail
[자료구조] Select Sort (선택 정렬)
자료구조 2021. 2. 10. 19:07

개념 리스트의 가장 작은 값을 선택하여 앞으로 하나씩 가져오는 방식 (오름차순) 1. 주어진 리스트 중에 최소값을 찾음 2. 그 값을 맨 앞에 위치한 값과 교체 (패스(pass)) 3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체 버블 정렬보다 성능이 좋음 작은 배열을 정렬할 때 삽입정렬이나 선택정렬이 더 빠름 제자리 정렬에 속함 시간복잡도 (Worst Case = Best Case = Average Case) 비교 - O(n^2) 교환 - O(n) 예제 코드 void selectSort(int array[], int n) { int temp; for (int i = 0; i < n - 1; ++i) { int index = i; for (int j = i + 1; j < n; ++j) { i..

article thumbnail
[자료구조] Insert Sort (삽입 정렬)
자료구조 2021. 2. 8. 11:11

개념 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘 정렬하는 배열이 작은 경우 효율적, 배열이 길 수록 비효율적 선택 정렬, 거품 정렬과 같은 O(n^2) 알고리즘에 비교하여 빠름 구현이 간단하며 Stable Sort (안정 정렬)임 1. 첫번째 원소를 리스트에 삽입 2. n번째 원소를 리스트에 적절한 위치에 삽입 (반복) 시간복잡도 Worst Case - 비교, 교환 O(n^2) Best Case - 비교 O(n), 교환 O(1) Average Case - 비교, 교환 O(n^2) 예제 코드 void insertionSort(int list[], int n) { int i, j, temp; for (i = 1; ..

article thumbnail
[자료구조] Quick Sort (퀵 정렬)
자료구조 2021. 2. 7. 20:04

개념 하나의 리스트를 피벗을 기준으로 분할하고 작은 값은 왼쪽, 큰 값은 오른쪽으로 정렬하는 과정을 반복한 다음, 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법 컴퓨터로 가장 많이 구현된 정렬 알고리즘 중 하나 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬 같은 값들의 정렬 이후 순서가 초기 순서와 달라질 수 있는 불안정 정렬 퀵 정렬은 분할 정복(divide and conquer) 방법을 통해 리스트를 정렬 합병 정렬(Merge Sort)와 달리 퀵 정렬은 리스트를 비균등하게 분할 속도가 빠름 정렬된 리스트에 대해서는 퀵 정렬의 불균형 분할에 의해 수행시간이 오래 걸림 1. 리스트 가운데서 하나의 원소를 고른다. (이렇게 고른 원소 = 피벗) 2. 피벗 앞에는 피벗보다 값이 ..

article thumbnail
[자료구조] Bubble Sort (버블 정렬)
자료구조 2021. 2. 6. 20:01

개념 서로 인접한 두 원소를 비교해서 일정한 기준을 만족하면 서로의 값을 교환하여 정렬하는 방식 코드가 단순해서 구현이 쉬움 비교 작업이 많아서 연산 시간이 오래 걸림 첫번째와 두번째를 비교 후 변경, 두번째와 세번째를 비교 후 변경, ... n번째와 n + 1번째를 비교 후 변경 위의 작업을 한번 수행시 마지막 위치에 가장 큰 값이 위치함 (오름차순 정렬의 경우) 그러므로 n번 수행을 하면 n개가 정렬이 됨 시간 복잡도 (Best Case = Average Case = Worst Case) T(n) = O(n^2) 예제 코드 void buubleSort(int array[], int len) { int temp; for (int i = len - 1; i > 0; --i) { for (int j = 0..

검색 태그