1. 합병 정렬(Merge Sort) 퀵 정렬과 같이, 합병 정렬은 분할 정복 알고리즘(Divide and Conquer)입니다. 합병 정렬은 리스트의 요소가 한개가 될때까지 리스트를 절반으로 나누는 과정을 수행합니다. 그리고 리스트의 요소가 각각 1개로 나누어지면 다시 정렬하면서 병합하는 과정을 수행합니다. 아래의 merge() 메서드는 절반으로 나누어진 두 리스트를 병합하는데 사용됩니다. 이것을 수두코드로 표현하면 아래와 같습니다. mergeSort(arr[], left, right) if right > 1 1. 리스트를 절반으로 나누기 위해서 중간점을 탐색합니다. middle = (left + right) / 2 2. 첫번째 절반의 리스트에 대해서 합병정렬을 재귀적인 호출합니다. mergeSort(..

1. 쉘 정렬(Shell Sort) 쉘 정렬은 일정한 너비만큼 떨어진 요소를 가져와서 그 둘을 대소비교한 후 바꾸는 방법입니다. 처음에는 큰 간격으로 시작해서 더 적은 가격으로 정렬을 하고 간격의 크기가 1이 되면 삽입 정렬을 수행합니다. 즉, 쉘 정렬은 작은 값을 가진 요소는 오른쪽에서 왼쪽으로 옮기고 큰 값을 가진 요소는 왼쪽에서 오른쪽으로 옮기는 알고리즘입니다. 쉘 정렬은 중복된 숫자의 순서가 보장되지 않는 불안정 정렬(not stable sort)입니다. 그리고 리스트 안에서 순서만 바꾸어주기 때문에 in-place 정렬입니다. 최악의 경우, 삽입 정렬과 같아지므로 시간 복잡도는 O(n²)입니다. 쉘 정렬의 평균적인 시간 복잡도는 얼마의 간격을 사용했는지에 따라 달라집니다. 쉘 정렬은 삽입 정렬을..

1. 삽입 정렬(Insertion Sort) 오름차순 정렬을 가정하고 n개의 데이터를 정렬한다고 가정하였을때 삽입 정렬은 다음과 같이 수행됩니다. arr[1]부터 arr[n]까지 배열을 순회합니다. 현재 데이터값을 기준으로 그 이전 위치에 존재하는 데이터값들과 비교합니다. 만약 기준이 되는 데이터값이 이전 위치에 존재하는 데이터값보다 작다면 값을 서로 교환합니다. 그러나 값이 크다면 비교를 종료합니다. 0번째 위치까지 2~3과정을 반복합니다. 위 삽입 정렬 수행과정을 그림으로 표현하면 다음과 같습니다. 2. 삽입 정렬 코드 구현 public class InsertionSort { public static void sort(int[] arr) { int n = arr.length; for(int i=1;i..

1. 선택 정렬(Selection Sort) 선택 정렬 알고리즘은 정렬되지 않은 배열에서 오름차순으로 정렬한다고 가정하고 배열 중에서 최소값을 반복적으로 탐색하여 시작 부분에 배치함으로써 배열을 정렬하는 알고리즘입니다. 선택 정렬 알고리즘은 정렬 과정에서 주어진 배열에서 2개의 하위 배열을 유지합니다. 한 하위 배열은 최소값을 탐색하여 시작 부분에 배치함으로써 정렬된 배열입니다. 다른 하위 배열은 정렬되지 않은 남은 요소들이 담긴 배열입니다. 2. 선택 정렬 수행 과정 선택 정렬의 수행 과정을 그림으로 표현하면 아래와 같습니다. 선택 정렬 수행 과정을 정리하면 다음과 같다. 배열의 시작부분 값을 기준으로 최소값을 탐색합니다. 최소값을 찾았다면 시작부분의 위치와 최소값의 위치의 값을 서로 교환합니다. 시작..

이전글 https://yonghwankim-dev.tistory.com/204 비선형 데이터구조, RedBlackTree #2 add 메서드 이전글 https://yonghwankim-dev.tistory.com/202 비선형 데이터구조, RedBlackTree #1 RedBlackTree의 규칙 및 수행과정 1. RedBlackTree의 규칙 모든 노드는 Red 또는 Black Root 노드는 언제나 Black 새로 추가.. yonghwankim-dev.tistory.com 개요 이전글에서는 RedBlackTree의 add메서드와 Rotate 메서드를 구현하였습니다. 이번글에서는 LeftRotate 메서드를 구현하도록 하겠습니다. 1. LeftRotate 메서드 LeftRotate 메서드의 역할은 한쪽..

이전글 https://yonghwankim-dev.tistory.com/202 비선형 데이터구조, RedBlackTree #1 RedBlackTree의 규칙 및 수행과정 1. RedBlackTree의 규칙 모든 노드는 Red 또는 Black Root 노드는 언제나 Black 새로 추가되는 노드는 항상 Red Root 노드에서 Leaf 노드까지 가는 모든 경로에는 같은 수의 Black 노드가 있어야한다 어떤 경로 yonghwankim-dev.tistory.com 개요 이전글에서는 RedBlackTree가 불균형 하였을때 트리를 Rebalance하는 연산들에 대해서 알아보았습니다. 이번글에서는 RedBlackTree의 add 메서드와 Rebalance(correctTree) 메서드를 구현하겠습니다. 1. a..