Day10 자료구조 정렬의 시간복잡도
by 효기’s- Bubble Sort
/* * 버블 정렬의 시간복잡도는 o(n^2) 입니다. * 배열의 길이를 n이라고 했을대 두개의 중첩된 for문을 사용했기 때문에 o(n^2)이 되었으며 * 첫번째 for 루프는 n-1번 반복하고 두번째 for 루프는 최대 n-1번 반복하기 때문에 * 전체 루프의 실행 횟수는 대락 (n-1) * (n-1)이 됩니다. * */ package sort; public class BubbleSort { public static void bubbleSort(int[] arr) { // 정렬 알고리즘 시작 시간 기록 long startTime = System.nanoTime(); for (int i = 0; i < arr.length - 1; i++) { // 0~배열의 인덱스 -1 만큼 반복 for (int j = 0; j < arr.length - 1; j++) { // 0~배열의 인덱스 -1 만큼 반복 if (arr[j] > arr[j + 1]) { // 인덱스[0] > 인덱스 [1] (왼쪽과 오른쪽 인덱스를 비교) // 인덱스 J와 인덱스 J+1의 원소의 값을 교환 int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } // 정렬 알고리즘 종료 시간 기록 long endTime = System.nanoTime(); // 정렬 알고리즘 수행 시간 계산 long duration = endTime - startTime; System.out.println("Bubble Sort 수행 시간: " + duration + "ns"); } public static void main(String[] args) { int[] arr = { 39, 10, 59, 50, 29, 19, 45 }; bubbleSort(arr); for (int num : arr) { System.out.print(num + " "); // 결과 } } }
Bubble Sort 수행 시간: 2800ns
- Heap 정렬
// heap sort(힙 정렬) 알고리즘의 시간복잡도는 항상 o(n log n) 입니다. // 이런 이유는 힙을 구성하는데 o(n)시간이 소요되고 힙 정렬을 수행하는데 o(n log n)이 소요되기 때문입니다. // o(n)이 o(n log n)보다 시간복잡도가 더 빠르므로 더 복잡한 o(n log n)이 힙 정렬의 시간복잡도가 됩니다. package sort; public class HeapSort { public static void heapSort(int[] arr) { // 정렬 알고리즘 시작 시간 기록 long startTime = System.nanoTime(); // 힙을 구성 for (int i = arr.length / 2 - 1; i >= 0; i--) { heapify(arr, arr.length, i); // 가장 큰 값이 루트에 위치 } // 힙 정렬 수행 for (int i = arr.length - 1; i > 0; i--) { swap(arr, 0, i); // 루트와 마지막 원소를 교환하고, 배열의 크기를 하나씩 줄여가며 heapify(arr, i, 0); // 힙 구조를 조정. } // 정렬 알고리즘 종료 시간 기록 long endTime = System.nanoTime(); // 정렬 알고리즘 수행 시간 계산 long duration = endTime - startTime; System.out.println("Heap Sort 수행 시간: " + duration + "ns"); } public static void heapify(int[] arr, int n, int root) { int largest = root; // 현재 부분 힙에서 가장 큰 값을 가지는 노드 인덱스 저장 int left = 2 * root + 1; // 왼쪽 자식 노드 인덱스 int right = 2 * root + 2; // 오른쪽 자식 노드 인덱스 // largest가 현재 노드와 다를경우 현재 노드와 largest 노드를 교환 if (left < n && arr[left] > arr[largest]) { largest = left; } if (right < n && arr[right] > arr[largest]) { largest = right; } // 루트가 가장 큰값이 아닐경우 if (largest != root) { swap(arr, root, largest); heapify(arr, n, largest); } } // 두 원소의 위치를 교환하는 역할 public static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } public static void main(String[] args) { int[] arr = { 39, 10, 59, 50, 29, 19, 45 }; heapSort(arr); for (int num : arr) { System.out.print(num + " "); // 결과 } } }
Heap Sort 수행 시간: 5900ns
// 삽입 정렬의 시간복잡도는 최선의 경우 o(n)이며 평균 및 최악의 경우에는 o(n^2) 입니다. // 이 같은 이유는 배열이 이미 정렬되어 있는 경우 최선의 경우가 되고 // 역순으로 정렬되어있으면 평균 및 최악의 경우가 됩니다. // 삽입 정렬은 순차적으로 배열에 우측으로 가면서 작은값이 있으면 올바른 위치의 왼쪽으로 삽입합니다. // 값이 왼쪽으로 끼어들게 되면 큰수들은 오른쪽으로 밀리게 됩니다. package sort; public class InsertionSort { // 삽입 정렬을 진행하는 InsertionSort 메소드를 만들었습니다. public static void InsertionSort(int[] arr) { // 정렬 알고리즘 시작 시간 기록 long startTime = System.nanoTime(); for(int i = 1; i < arr.length; i++) { // (배열의 순회를 위해) 1부터 배열의 길이까지 반복합니다. int key = arr[i]; // 순회중인 배열의 전체를 key 에 넣습니다. (삽입할 원소를 임시로 저장합니다.) int j = i - 1; // 왼쪽에 있는 원소들과 비교하며 위치를 찾기위한 변수 j 입니다. // (작은값이 큰값보다 왼쪽에 있어야 하기때문에 )key값을 올바른 위치로 이동시킵니다. while(j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; // 배열j에 +1을 함으로써 배열j가 우측으로 밀립니다. j--; } arr[j + 1] = key; // key값이 올바른 위치로 할당. } // 정렬 알고리즘 종료 시간 기록 long endTime = System.nanoTime(); // 정렬 알고리즘 수행 시간 계산 long duration = endTime - startTime; System.out.println("Insertion Sort 수행 시간: " + duration + "ns"); } // 메인에서는 배열의 값과 insertionSort 메소드를 실행시킵니다. public static void main(String[] args) { int[] arr = { 39, 10, 59, 50, 29, 19, 45 }; InsertionSort(arr); for (int num : arr) { System.out.print(num + " "); // 결과 } } }
Insertion Sort 수행 시간: 3000ns
- MergeSort
// 병합정렬의 시간복잡도는 항상 o(n log n) 입니다. // 이는 배열을 반으로 조갠 후, 재귀적으로 정렬하고 다시 병합하는 방식으로 진행되기 때문입니다. package sort; public class MergeSort { public static void mergeSort(int[] arr) { // 정렬 알고리즘 시작 시간 기록 long startTime = System.nanoTime(); if (arr.length <= 1) { // 배열길이가 1보다 작거나 같으면 반환 (더이상 쪼개지지 않을때까지 않을때까지) return; // 종료 } int mid = arr.length / 2; // 배열을 중간위치를 기준으로 int[] left = new int[mid]; // 왼쪽으로 나눈다. int[] right = new int[arr.length - mid]; // 오른쪽으로 나눈다. System.arraycopy(arr, 0, left, 0, mid); // mid를 기준으로 왼쪽 배열을 복사 System.arraycopy(arr, mid, right, 0, arr.length - mid); // mid를 기준으로 오른쪽 배열을 복사 mergeSort(left); // 왼쪽 정렬 mergeSort(right); // 오른쪽 정렬 merge(arr, left, right); // 정렬된 배열의 왼쪽과 오른쪽을 merge를 통해 병합 // 정렬 알고리즘 종료 시간 기록 double endTime = System.nanoTime(); // 정렬 알고리즘 수행 시간 계산 double duration = (endTime - startTime)/1000000; System.out.println("Merge Sort 수행 시간: " + duration + "ms"); } // 정렬된 왼쪽 부분과 오른쪽 부분을 병합하여 하나의 배열로 합치는 메소드 private static void merge(int[] arr, int[] left, int[] right) { int i = 0, j = 0, k = 0; // 왼쪽과 오른쪽 배열 길이가 0보다는 클때 반복 while (i < left.length && j < right.length) { // 왼쪽이 오른쪽보다 작거나 같음 if (left[i] <= right[j]) { // 왼쪽 배열에 삽입 arr[k++] = left[i++]; } else { // 오른쪽 배열에 삽입 arr[k++] = right[j++]; } } // 왼쪽 길이 while (i < left.length) { arr[k++] = left[i++]; } // 오른쪽 길이 반복 while (j < right.length) { arr[k++] = right[j++]; } } public static void main(String[] args) { int[] arr = { 39, 10, 59, 50, 29, 19, 45 }; mergeSort(arr); for (int num : arr) { System.out.print(num + " "); // 결과 } } }
Merge Sort 수행 시간: 0.0042ms
Merge Sort 수행 시간: 4.3845ms
Merge Sort 수행 시간: 0.0013ms
Merge Sort 수행 시간: 0.0039ms
Merge Sort 수행 시간: 0.1843ms
Merge Sort 수행 시간: 4.7506ms
- QuickSort
/* * QuickSort 알고리즘 * 최악의 경우 o(n^2) 인데 이는 피벗 기준으로 배열을 분할하고 정복하는 방법을 사용하기 때문에 발생합니다. * 또한 피벗을 선정하기 어려운 상황에서도 최악의 시간복잡도를 보여줍니다. * * 만일 균등하게 나누어지면 평균적으로 o(n log n)의 성능이 발생합니다. * */ package sort; public class QuickSort { // 오름차순으로 정렬 public static void quickSort(int[] arr, int low, int high) { // 정렬 알고리즘 시작 시간 기록 long startTime = System.nanoTime(); // low는 하한 인덱스, high는 상한 인덱스 if (low < high) { int pivotIndex = partition(arr, low, high); quickSort(arr, low, pivotIndex - 1); quickSort(arr, pivotIndex + 1, high); } // 정렬 알고리즘 종료 시간 기록 long endTime = System.nanoTime(); // 정렬 알고리즘 수행 시간 계산 long duration = endTime - startTime; System.out.println("Quick Sort 수행 시간: " + duration + "ns"); } // 피벗 인덱스를 구하는 역할을 합니다. public static int partition(int[] arr, int low, int high) { // high 인덱스에 해당하는 값을 피벗으로 선택합니다. int pivot = arr[high]; // 피벗보다 작은 값을 가진 원소들의 끝 인덱스를 나타냅니다. int i = low - 1; // low부터 high 까지 반복하면서 각 원소의 피벗과 비교 for (int j = low; j < high; j++) { if (arr[j] < pivot) { // 피벗보다 작으면 i를 증가 i++; swap(arr, i, j); // 해당 원소를 교환 } } swap(arr, i + 1, high); // i + 1위치에 피벗을 배치 return i + 1; // 해당 인덱스를 반환 } // 위치를 바꾸는 함수 public static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } public static void main(String[] args) { int[] arr = { 39, 10, 59, 50, 29, 19, 45 }; quickSort(arr, 0, arr.length - 1); for (int num : arr) { System.out.print(num + " "); // 결과 } } }
Quick Sort 수행 시간: 100ns
Quick Sort 수행 시간: 100ns
Quick Sort 수행 시간: 300ns
Quick Sort 수행 시간: 423700ns
Quick Sort 수행 시간: 2118100ns
Quick Sort 수행 시간: 200ns
Quick Sort 수행 시간: 200ns
Quick Sort 수행 시간: 114200ns
Quick Sort 수행 시간: 2415300ns
- SelectionSort
// 시간복잡도 O(n^2) => 이중 for문을 사용했기 때문에 order n^2이 됩니다. // 배열의 길이를 n이라고 했을때 첫번재 for 루프는 n번 반복하고 // 두번재 for 루프는 n-1번 반복하기 때문에 전체 루프의 실행 횟수는 // n * ( n - 1 ) /2 가 됩니다. package sort; public class SelectionSort { public static void selectionSort(int[] arr) { // 정렬 알고리즘 시작 시간 기록 long startTime = System.nanoTime(); for (int i = 0; i < arr.length; i++) { // 0부터 배열의 길이만큼 반복 for (int j = i + 1; j < arr.length; j++) { // 1부터 배열의 길이만큼 반복 if (arr[i] > arr[j]) { // 0 ~ 배열의 길이 > 1 ~ 배열의 길이 // 현재 인덱스 i와 이후 인덱스 j에 위치한 두 원소의 값을 교환 int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } } // 정렬 알고리즘 종료 시간 기록 long endTime = System.nanoTime(); // 정렬 알고리즘 수행 시간 계산 long duration = endTime - startTime; System.out.println("Selection Sort 수행 시간: " + duration + "ns"); } public static void main(String[] args) { int[] arr = { 39, 10, 59, 50, 29, 19, 45 }; selectionSort(arr); for (int num : arr) { System.out.print(num + " "); // 결과 } } }
Selection Sort 수행 시간: 4300ns
- ShellSort
// 셸 정렬의 시간복잡도는 최선, 평균, 최악의 경우 모두 o(n log n) 입니다. // 삽입 정렬의 단점을 보완하여 더 빠르게 동작하는 장점이 있기 때문에 평균적으로 좋은 성능을 보입니다. package sort; public class ShellSort { // 배열을 오름차순으로 정리하는 shellsort 메서드를 만들었습니다. public static void shellSort(int[] arr) { // 정렬 알고리즘 시작 시간 기록 long startTime = System.nanoTime(); // 배열의 길이를 변수 n에 저장합니다. int n = arr.length; int gap = n / 2; // 배열을 부분리스트 간의 거리를 나타내는 간격인 gap 변수를 선언합니다. while (gap > 0) { // gap이 0 이하가 될때까지 과정을 반복합니다. // for 반복문을 통해 각 부분 리스트에 삽입 정렬을 수행합니다. // i는 부분리스트의 시작위치부터 배열의 길이까지 반복합니다. for (int i = gap; i < n; i++) { // 부분 리스트의 요소와 이전 부분리스트의 요소를 비교하여 정렬을 진행합니다. int temp = arr[i]; // temp는 현재 부분 리스트 요소를 임시로 저장 int j = i; // j는 현재 요소의 인덱스를 나타냅니다. // 현재 요소와 이전 부분 리스트의 요소를 비교하여 while 반복문을 통해 삽입 정렬을 합니다. // 이전 부분리스트의 요소가 현재 요소보다 크면 오른쪽으로 이동시키며 정렬을 진행합니다. while (j >= gap && arr[j - gap] > temp) { arr[j] = arr[j - gap]; j -= gap; } arr[j] = temp; // j위치에 temp를 삽입하여 정렬을 완료합니다. } // gap을 줄이며 위 과정을 반복합니다. gap /= 2; } // 정렬 알고리즘 종료 시간 기록 long endTime = System.nanoTime(); // 정렬 알고리즘 수행 시간 계산 long duration = endTime - startTime; System.out.println("Shell Sort 수행 시간: " + duration + "ns"); } // 메인에 배열값과 공백을 넣어서 결과를 출력합니다. public static void main(String[] args) { int[] arr = { 39, 10, 59, 50, 29, 19, 45 }; shellSort(arr); for (int num : arr) { System.out.print(num + " "); // 결과 } } } // 셸 정렬은 삽입 정렬과 비교하여 평균적으로 좋은 성능을 보이며 빠르게 동작하는 장점이 있습니다.
Shell Sort 수행 시간: 6100ns
블로그의 정보
감성 개발자 효기
효기’s