분류 전체보기152 [자료구조] 병합 정렬(Merge Sort) 목차 정렬 종류 비교 기반 정렬(Comparison Based Sorts) - Selection Sort, Bubble Sort, Insertion Sort, Heap Sort, Merge Sort, Quick Sort 비비교 기반 정렬(Non-comparison Based Sorts) - Counting Sort, Radix Sort, Bucket Sort 병합 정렬(Merge Sort) 개념 병합 정렬은 분할 정복을 이용한 비교 기반 정렬입니다. 분할 정복은 일종의 DP랑 유사한 방법입니다. 따라서 분할 정복 역시 DP와 마찬가지로 하향식 접근(Top-Down)과 상향식(Bottom-Up) 접근이 존재합니다. 하향식 접근 : 재귀를 이용 상향식 접근 : 반복을 통해 모든 값 표 채우기 다만 DP는 분.. 2024. 4. 16. [자료구조] 힙 정렬(Heap Sort) 목차 정렬 종류 비교 기반 정렬(Comparison Based Sorts) - Selection Sort, Bubble Sort, Insertion Sort, Heap Sort, Merge Sort, Quick Sort 비비교 기반 정렬(Non-comparison Based Sorts) - Counting Sort, Radix Sort, Bucket Sort 힙 정렬(Heap Sort) 개념 먼저 선택 정렬을 할 때, 가장 작은 값을 찾은 뒤 앞으로 이동했습니다. 이 과정을 전체 값들이 정렬이 될 때까지 반복해서 진행했습니다. 이로 인해 시간은 O(N^2)이 소요되게 되었습니다. 이를 이제 힙이라는 특별한 자료구조를 사용하게 되면 이를 개선할 수가 있습니다. 힙 : https://comdon-ai.tis.. 2024. 4. 16. [자료구조] 삽입 정렬(Insertion Sort) 목차 정렬 종류 비교 기반 정렬(Comparison Based Sorts) - Selection Sort, Bubble Sort, Insertion Sort, Heap Sort, Merge Sort, Quick Sort 비비교 기반 정렬(Non-comparison Based Sorts) - Counting Sort, Radix Sort, Bucket Sort 삽입 정렬(Insertion Sort) 개념 리스트의 시작부터 하나책마다 왼쪽에 있는 책들과 비교해서 자기보다 작은 책이 나올 때까지 번갈아가며 껴줍니다. 정렬되지 않은 책장이 있을 때 앞에서부터 왼쪽에 있는 책들과 비교를 하면서 자기 크기에 맞는 곳에 넣어주는 것입니다. 즉, 2 3 5 6 7 4가 있을 때 4는 자기보다 작은 값인 3 뒤로 삽입되.. 2024. 4. 16. [자료구조] 버블 정렬(Bubble Sort) 목차 정렬 종류 비교 기반 정렬(Comparison Based Sorts) - Selection Sort, Bubble Sort, Insertion Sort, Heap Sort, Merge Sort, Quick Sort 비비교 기반 정렬(Non-comparison Based Sorts) - Counting Sort, Radix Sort, Bucket Sort 버블 정렬(Bubble Sort) 개념 버블 정렬은 두 개의 인접한 요소를 비교하여 작은 값을 앞으로 보내주는 과정을 기반으로 정렬하게 됩니다. 이러한 과정을 앞에서부터 뒤에까지 쭈욱 진행하면, 작은 값들이 한 칸씩 앞으로 이동하게 될 것입니다. 이러한 과정은 swap 과정이 발생하지 않을때까지 진행되게 됩니다. 만약 제일 작은 값이 제일 뒤에 있다.. 2024. 4. 16. 이전 1 2 3 4 5 6 ··· 38 다음
