Programming/Algorithm5 [algorithm] 정렬 4. 정리 및 응용 목차어떤 정렬 알고리즘을 사용해야 하는가환원 : 정렬 알고리즘 응용하기정렬알고리즘 사용 사례어떤 정렬 알고리즘을 사용해야 하는가 명제 : 퀵-정렬은 가장 빠른 범용 정렬 알고리즘이다.위 가설은 퀵-정렬이 개발된 이래 수십 년간 수많은 컴퓨팅 시스템에서 수많은 방식으로 구현되어 왔다. 일반적으로 퀵 정렬이 빠른 이유는 내부 루프의 명령어 수가 적기 때문이다. 결론 : 대부분의 실제 상황에서 퀵-정렬을 선택하는 것이 안전하다. 그 선택이 올바른지는 예외 상황들을 토대로 살펴봐야 한다. 예를 들어 안정정렬이 중요하고 공간이 충분하다면 병합 정렬이 최선일 것이다. 기본형 데이터 타입의 정렬성능에 매우 민감하거나 숫자의 정렬에만 집중한다면 int와 같은 기본형을 사용하는 것이 좋다. int는 후술 할 포인터 .. 2024. 6. 22. [algorithm] 정렬 3. 우선순위 큐 (Priority Queues) 2024.02.04 - [Programming/Algorithm] - [algorithm] 정렬 2. 퀵 정렬 [algorithm] 정렬 2. 퀵 정렬 https://kghworks.tistory.com/175 [알고리즘] 정렬 1. 병합 정렬 목차 병합정렬 하향식 병합 정렬 (top-down) 상향식 병합 정렬 (bottom-up) 병합 정렬은 점근적으로 볼 때 최적의 비교 기반 정렬 알고리즘이다 kghworks.tistory.com 이어지는 포스팅이다. 목차 우선순위 큐 (Priority Queues) 기초적인 구현 힙 (Heap) 힙 알고리즘 구현하기 힙을 이용한 알고리즘 1 : 인덱스 기반 우선순위 큐 힙을 이용한 알고리즘 2 : 힙 정렬 큐 (Queue)는 FIFO (First-in-first-.. 2024. 4. 19. [algorithm] 정렬 2. 퀵 정렬 https://kghworks.tistory.com/175 [알고리즘] 정렬 1. 병합 정렬 목차 병합정렬 하향식 병합 정렬 (top-down) 상향식 병합 정렬 (bottom-up) 병합 정렬은 점근적으로 볼 때 최적의 비교 기반 정렬 알고리즘이다 병합정렬 병합 (merge)은 정렬 대상을 2개의 배열로 쪼갠 kghworks.tistory.com 이어지는 포스팅이다. 목차 퀵 정렬 퀵 정렬 성능 특성 퀵 정렬 알고리즘 개선 퀵 정렬 퀵 정렬은 가장 널리 사용되는 정렬 알고리즘이다. 구현이 쉽고, 다양한 형태의 input이 가능하다. 응용상황에서 다른 정렬 알고리즘들보다 (병합, 선택, 삽입 정렬) 빠르고, 추가적인 메모리 사용을 하지 않는 in-place sorting인 장점이 있다. 그러나 부주의한 .. 2024. 2. 4. [algorithm] 정렬 1. 병합 정렬 목차 병합정렬 하향식 병합 정렬 (top-down) 상향식 병합 정렬 (bottom-up) 병합 정렬은 점근적으로 볼 때 최적의 비교 기반 정렬 알고리즘이다 병합정렬 병합 (merge)은 정렬 대상을 2개의 배열로 쪼갠 다음, 각각 정렬시킨 다음 큰 정렬된 배열로 다시 합치는 것을 말한다. 이때 배열을 쪼개어 정렬한 뒤 합치는 작업을 재귀적으로 수행한다면, 최종적으로 배열이 정렬된다는 것이다. 크기가 N인 배열을 정렬하는데 NlogN이 소요된다. 재귀적으로 구현한다는 것은 분할정복 패러다임 (문제를 잘게 쪼개어 각 부분을 해결한뒤 다시 전체 문제를 해결)을 사용한다는 것이다. 아래에서 살펴보겠지만, 분할정복은 다시 하향식 (top-down)으로 구현하는 방법과, 상향식 (bottom-up)으로 구현방법이.. 2024. 1. 7. [algorithm] 기초적인 정렬 : 선택 정렬, 삽입 정렬 목차 선택 정렬 삽입 정렬 삽입정렬 vs 선택정렬 셸 정렬 선택정렬 (Selection sorting) 길이 N의 배열이 주어졌을 때, 배열의 가장 작은 항목을 찾아 [0]와 교환 그다음으로 작은 항목을 찾아 [1]와 교환 ... 그 다음으로 작은 항목을 찾아 [N-1]과 교환 와 같이 모든 배열이 정렬될 때까지 (N-1) 번을 교환하는 방법이다. public class Selection { // a[]를 오름차순으로 정렬 public static void sort(Comparable[] a) { int N = a.length; for (int i = 0; i < N; i++) { // a[i]를 a[i+1..N] 중에서 가장 작은 원소와 교환 int idxMin = i; for (int j = i + .. 2023. 12. 28. 이전 1 다음
