정용이의 놀이동산

소개 매우 빠른 정렬 알고리즘입니다. 피벗(pivot)을 기준으로 그룹을 나누어 모든 그룹에 요소가 1개일 때 정렬을 마칩니다. 배열의 요소가 n개 있을 때 시간복잡도는 O(n log n) 구현 // 분할 정복 패러다임 public class QuickSort { public void quickSort(int[] arr, int left, int right) { int pl = left; int pr = right; int pivot = arr[(pl + pr) / 2]; do { // 피벗보다 큰 요소를 찾습니다. while (arr[pl] pivot) { pr--; } // 왼쪽과 오른쪽 포인터가 서..

소개 도널드 쉘(Donald L. Shell)이 고안한 정렬 알고리즘입니다. 삽입 정렬의 장점은 살리고, 단점은 보완한 정렬 알고리즘입니다. 단순 삽입 정렬 장점 : 정렬을 마친 상태에 가까울수록 정렬속도가 높아짐 단점 : 삽입할 위치가 멀수록 이동횟수가 증가함 정렬할 배열의 요소를 그룹으로 나누어 그룹별 삽입정렬(H-정렬)을 수행합니다. 그룹을 합치며 정렬을 반복합니다. 증분값 H는 초깃값이 너무 크면 효과가 없습니다. n(배열의 요솟수)/9 값을 넘지 않도록 합니다. 배열의 요소가 n개 있을 때 시간복잡도는 O(n^1.25) 구현 public class ShellSort { public void shellSort(int[] arr) { // 증분값 h int h; // h의 초기값을 구합니다. for..

소개 선택한 요소를 선택한 위치의 앞쪽에 있을 수 있는 올바른 위치에 삽입합니다. 2번 째 요소부터 선택해서 정렬 작업을 수행합니다. 선택한 요소 앞쪽은 항상 정렬되어 있는 구간입니다. 정렬이 수행되면서 정렬된 구간을 탐색하는 내부 반복문의 반복 횟수는 증가합니다. 배열의 요소가 n개 있을 때 시간복잡도는 O(n^2) 구현 public class InsertionSort { static void insertionSort(int[] arr) { // 정렬은 배열의 2번째 요소부터 시작합니다. for (int i = 1; i < arr.length; i++) { int j; int temp = arr[i]; // 정렬된 구간을 뒤에서부터 앞으로 순회한다. // 처음 temp와 arr[j]는 같은 대상이다. ..

소개 가장 작은 요소부터 선택하여 순서대로 정렬하는 알고리즘입니다. 선택 --> 교환 --> 정렬이 반복됩니다. 정렬은 배열의 앞쪽부터 이뤄집니다. 선택할 요소를 고르는 구간은 뒤쪽으로 점점 좁아집니다. 배열의 요소가 n개 있을 때 시간복잡도는 O(n^2) 구현 public class SelectionSort { static void selectionSort(int[] arr) { // 앞쪽부터 순서대로 정렬합니다. for (int i = 0; i < arr.length; i++) { // 가장 작은 값의 인덱스를 찾기 위해 초기화합니다. int min = i; for (int j = i + 1; j < arr.length; j++) { // 탐색 과정에서 더 작은 값이 있다면 해당 값의 인덱스를 저장합..

소개 이웃한 두 수의 크기를 비교하여 교환을 반복합니다. 매 라운드마다 1개씩 요소가 앞쪽부터 정렬됩니다. 정렬은 앞쪽부터 이뤄지고, 라운드 별 수의 크기 비교는 뒤쪽부터 시작됩니다. 배열의 요소가 n개 있을 때 시간복잡도는 O(n^2) 구현 public class BubbleSort { static void bubbleSort(int[] arr) { // 배열 앞쪽부터 정렬해간다. for (int i = 0; i i; j--) { if (arr[j - 1] > arr[j]) { swap(arr, j - 1, j); } } }..