Java & Kotlin/알고리즘4 [Java] 정렬 알고리즘 (4) - 퀵 정렬 (Quick Sort) 퀵 정렬 (Quick Sort) 1. Pivot 값을 기준으로 왼쪽에서부터 검사해서 큰 값을, 오른쪽에서부터 작은 값을 발견한다. 2. 두 값을 바꾸기 연산하고, 같은 과정을 수행한다. 3. 큰 값의 index 와 작은 값의 index 가 교차하는 경우, 작은 값과 Pivot 값을 바꾸기 연산한다. → Pivot 값을 기준으로 왼쪽은 Pivot 값보다 작은 값들, 오른쪽은 큰 값들로 분할된다. 4. 분할된 영역에서 같은 과정을 수행한다. → 재귀 성격 3. 시간 복잡도 : O(𝑁𝑙𝑜𝑔𝑁) 4. 작은 값과 큰 값으로 분할을 할 수 없는 경우 = 이미 정렬되어 있는 경우 : O(𝑁²) import java.util.Arrays; public class QuickSort { int[] array = new .. 2021. 5. 23. [Java] 정렬 알고리즘 (3) - 삽입 정렬 (Insertion Sort) 삽입 정렬 (Insertion Sort) 1. 앞의 원소들이 이미 정렬이 되어 있다고 가정한다. 2. 특정 원소에서 앞의 원소들을 살펴보며 적당한 위치를 찾는 것 3. 시간 복잡도 : O(𝑁²) 4. 선택 정렬, 버블정렬보다 효율적인 알고리즘 → 필요 시에 바꾸기 연산을 수행하기 때문. 특히 이미 정렬이 되어 있을 경우에는 최고의 효율을 보여준다. import java.util.Arrays; public class InsertSort { int[] array = new int[]{10, 2, 5, 8, 12, 73}; public void sort() { int j, temp; for (int i = 0; i = 0 && a.. 2021. 5. 23. [Java] 정렬 알고리즘 (2) - 버블 정렬 (Bubble Sort) 버블 정렬 (Bubble Sort) 1. 두 숫자를 비교해서 더 작은 숫자를 왼쪽에 두는 것 2. 반복이 끝났을 때, 최댓값이 맨 뒤에 있게 된다. 3. 시간 복잡도 : O(𝑁²) 4. 선택 정렬보다 비효율적인 알고리즘 → 선택 정렬은 비교하면서 최솟값을 저장하고, 한 번 반복이 끝나고 바꾸기 연산을 수행하지만 버블 정렬은 비교할 때마다 바꾸기 연산이 이뤄지기 때문이다. import java.util.Arrays; public class BubbleSort { int[] array = new int[]{10, 2, 5, 8, 12, 73}; public void sort() { int temp; for (int i = 0; i < array.length; i++) { for (int j = 0; j < .. 2021. 5. 23. [Java] 정렬 알고리즘 (1) - 선택 정렬 (Selection Sort) 선택 정렬 (Selection Sort) 1. 가장 작은 숫자를 가장 앞에 두는 것 2. 반복이 끝났을 때, 최솟값이 맨 앞에 있게 된다. 3. 시간 복잡도 : O(𝑁²) import java.util.Arrays; public class SelectionSort { int[] array = new int[]{10, 2, 5, 8, 12, 73}; public void sort() { int min, temp, index = 0; for (int i = 0; i array[j]) { min = array[j]; index = j; } } temp = .. 2021. 5. 23. 이전 1 다음