Computer Science32 [자료구조] 계수 정렬(Counting 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 계수 정렬(Counting Sort) 개념 non-comparison 기반 정렬에서 가장 간단한 정렬 방법입니다. 주어진 값의 범위가 한정적일 때 유용한 방법입니다. 주어진 값의 범위에 대한 count 배열을 생성해 줍니다. 그 후 해당 count 배열을 앞에서부터 누적합을 계산해 줍니다. 이럴 경우 이제 배열에서 특정값에 대한 시작 인덱스를 확인할.. 2024. 4. 17. [자료구조] 퀵 정렬(Quick 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 퀵 정렬(Quick Sort) 개념 퀵 정렬은 기준값(Pivot)을 중심으로 Pivot보다 작으면 왼쪽, 크면 오른쪽으로 분할해 줍니다. 그런 다음 분할된 하위 리스트들을 다시 재귀적으로 pivot을 뽑고 pivot보다 작으면 왼쪽, 크면 오른쪽으로 분할해 줍니다. 이런 식으로 쭉 진행하게 되면 정렬된 리스트를 얻을 수 있습니다. 퀵 정렬은 병합 정.. 2024. 4. 17. [자료구조] 병합 정렬(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. 이전 1 2 3 4 5 ··· 8 다음
