자료구조 - 정렬 8 (Topological) 전체 정렬 개요의 설명은 여기를 참조 Bubble / Selection / Insertion 정렬의 설명은 여기를 참조 Shell 정렬의 설명은 여기를 참조 Merge 정렬의 설명은 여기를 참조 Quick 정렬의 설명은 여기를 참조 Heap 정렬은 우선순위 큐에서 사용하는 정렬이므로 해당 포스팅 여기를 참조 Counting 정렬의 설명은 여기를 참조 Radix 정렬의 설명은 여기를 참조 Bucket 정렬의 설명은 여기를 참조 1. Topological Sort(위상 정렬) 위상 정렬은 순서가 있는 작업을 해야할 때 그 순서를 임의로 설정할 수 있도록 정렬하는 알고리즘이다. 예를 들어서 A라는 작업을 한 뒤에 B라는 작업을 해야한다고 생각하자. 그 경우, 작업 순서는 A → B 가 될 것이다. B → A는.. 자바 프로그래밍/자료구조(Data Structure) 4년 전
자료구조 - 정렬 7 (Bucket) 전체 정렬 개요의 설명은 여기를 참조 Bubble / Selection / Insertion 정렬의 설명은 여기를 참조 Shell 정렬의 설명은 여기를 참조 Merge 정렬의 설명은 여기를 참조 Quick 정렬의 설명은 여기를 참조 Heap 정렬은 우선순위 큐에서 사용하는 정렬이므로 해당 포스팅 여기를 참조 Counting 정렬의 설명은 여기를 참조 Radix 정렬의 설명은 여기를 참조 Topological 정렬의 설명은 여기를 참조 1. Bucket Sort(버킷 정렬) 버킷 정렬은 전체 데이터가 특정 범위 안에 균등하게 분포되어 있다는 가정을 할 수 있을 때 매우 유용하게 쓰일 수 있는 정렬 알고리즘이다. 예를 들어, 전체 데이터가 0.0 이상 1.0 미만의 범위 안에 있는데 이 데이터가 매우 소수점.. 자바 프로그래밍/자료구조(Data Structure) 4년 전
자료구조 - 정렬 6 (Radix) 전체 정렬 개요의 설명은 여기를 참조 Bubble / Selection / Insertion 정렬의 설명은 여기를 참조 Shell 정렬의 설명은 여기를 참조 Merge 정렬의 설명은 여기를 참조 Quick 정렬의 설명은 여기를 참조 Heap 정렬은 우선순위 큐에서 사용하는 정렬이므로 해당 포스팅 여기를 참조 Counting 정렬의 설명은 여기를 참조 Bucket 정렬의 설명은 여기를 참조 Topological 정렬의 설명은 여기를 참조 Radix Sort (기수 정렬) 이전의 버블 / 선택 / 삽입 / 병합 / 퀵 정렬 등은 모두 값을 비교함으로써 정렬을 수행하게 되고 이는 아무리 좋은 성능을 낼지라도 평균적으로 O(nlogn)보다 더 빠르게 수행할 수는 없다. 그런데, 이전의 Counting Sort(.. 자바 프로그래밍/자료구조(Data Structure) 4년 전
자료구조 - 정렬 5 (Counting) 전체 정렬 개요의 설명은 여기를 참조 Bubble / Selection / Insertion 정렬의 설명은 여기를 참조 Shell 정렬의 설명은 여기를 참조 Merge 정렬의 설명은 여기를 참조 Quick 정렬의 설명은 여기를 참조 Heap 정렬은 우선순위 큐에서 사용하는 정렬이므로 해당 포스팅 여기를 참조 Radix 정렬의 설명은 여기를 참조 Bucket 정렬의 설명은 여기를 참조 Topological 정렬의 설명은 여기를 참조 Counting Sort(계수 정렬) 간단하게 그림으로 이해할 수 있는 자료는 다음과 같다. 혹은 이를 간단하게 테스트해볼 수 있는 웹 페이지 링크도 있다. 여기를 들어가서 확인. 계수 정렬의 특징은 다음과 같다. 특성 설명 Not In-place 알고리즘 배열을 나누는 과정에.. 자바 프로그래밍/자료구조(Data Structure) 4년 전
자료구조 - 정렬 4 (Quick) 전체 정렬 개요의 설명은 여기를 참조 Bubble / Selection / Insertion 정렬의 설명은 여기를 참조 Shell 정렬의 설명은 여기를 참조 Merge 정렬의 설명은 여기를 참조 Heap 정렬은 우선순위 큐에서 사용하는 정렬이므로 해당 포스팅 여기를 참조 Counting 정렬의 설명은 여기를 참조 Radix 정렬의 설명은 여기를 참조 Bucket 정렬의 설명은 여기를 참조 Topological 정렬의 설명은 여기를 참조 Quick Sort(퀵 정렬) 이름만 봐도 매우 빠르게 동작할 것 같다. 우선 애니메이션으로 한 번 살펴보자. 퀵 정렬은 영국의 Computer Scientist인 Tony Hoare 가 고안한 방식이다. 위의 애니메이션에서 주목할 점은 Pivot이라는 문구이다. 이 Pi.. 자바 프로그래밍/자료구조(Data Structure) 4년 전
자료구조 - 정렬 3 (Merge) 전체 정렬 개요의 설명은 여기를 참조 Bubble / Selection / Insertion 정렬의 설명은 여기를 참조 Shell 정렬의 설명은 여기를 참조 Quick 정렬의 설명은 여기를 참조 Heap 정렬은 우선순위 큐에서 사용하는 정렬이므로 해당 포스팅 여기를 참조 Counting 정렬의 설명은 여기를 참조 Radix 정렬의 설명은 여기를 참조 Bucket 정렬의 설명은 여기를 참조 Topological 정렬의 설명은 여기를 참조 Merge Sort(병합 정렬) 애니메이션만 봐도 굉장히 쉽게 이해할 수 있다. 아래를 확인하자. 병합 정렬은 존 폰 노이만(John von Neunmann)이 제안한 Stable 정렬의 기법이다. 위의 애니메이션만 봐도 쉽게 이해가 가능한데, 말 그대로 기존의 배열을 반.. 자바 프로그래밍/자료구조(Data Structure) 4년 전
자료구조 - 정렬 2 (Shell) 전체 정렬 개요의 설명은 여기를 참조 Bubble / Selection / Insertion 정렬의 설명은 여기를 참조 Merge 정렬의 설명은 여기를 참조 Quick 정렬의 설명은 여기를 참조 Heap 정렬은 우선순위 큐에서 사용하는 정렬이므로 해당 포스팅 여기를 참조 Counting 정렬의 설명은 여기를 참조 Radix 정렬의 설명은 여기를 참조 Bucket 정렬의 설명은 여기를 참조 Topological 정렬의 설명은 여기를 참조 Shell Sort(셸 정렬) 애니메이션을 보아도 이해가 어렵겠지만 참고적으로 살펴보자. 셸 정렬은 'Donald L. Shell' 이 제안한 방법으로, 지난 포스팅의 삽입 정렬(Insertion Sort)를 보완한 방식이다. 삽입 정렬의 문제점은 무엇이 있을까? 삽입 정.. 자바 프로그래밍/자료구조(Data Structure) 4년 전
자료구조 - 정렬 1 (Bubble / Selection / Insertion) 전체 정렬 개요의 설명은 여기를 참조 Shell 정렬의 설명은 여기를 참조 Merge 정렬의 설명은 여기를 참조 Quick 정렬의 설명은 여기를 참조 Heap 정렬은 우선순위 큐에서 사용하는 정렬이므로 해당 포스팅 여기를 참조 Counting 정렬의 설명은 여기를 참조 Radix 정렬의 설명은 여기를 참조 Bucket 정렬의 설명은 여기를 참조 Topological 정렬의 설명은 여기를 참조 1. Bubble Sort(버블 정렬) 설명보단 보는 것이 제일 빠르다. 다음의 애니메이션을 보고 버블 정렬이 무엇인지 이해해보자. 한 눈에 보아도 이해가 쉽다. 오름차순 정렬을 기준으로 보여주는 애니메이션이다. 연속된 값들을 서로 비교하면서 더 작은 값이 왼쪽에 위치하도록 상호 위치 변경을 해주는 작업을 해주고 있.. 자바 프로그래밍/자료구조(Data Structure) 4년 전
