JAVA 시간복잡도와 정렬 출력프로그램
by 효기’s
package sort; import java.util.Scanner; public class Main { // 난수 설정 public static void prepare(int []arr) { for (int i = 0; i < arr.length; i++) { arr[i] = (int)(Math.random() * 1000); } } // 배열 print public void printSort(int []arr) { for(int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); } public static void main(String[] args) { int[] arr = new int[1000]; Scanner sc = new Scanner(System.in); boolean startEnd = true; while(startEnd) { Main s = new Main(); System.out.println("1.버블정렬 2.힙정렬 3.삽입정렬 4.합병정렬 5.퀵정렬 6.선택정렬 7.셸정렬 0.종료"); int inputData = sc.nextInt(); switch(inputData) { case 1: prepare(arr); BubbleSort.bubbleSort(arr); // 합병정렬 s.printSort(arr); continue; case 2: prepare(arr); HeapSort.heapSort(arr); // 합병정렬 s.printSort(arr); continue; case 3: prepare(arr); InsertionSort.InsertionSort(arr); // 합병정렬 s.printSort(arr); continue; case 4: prepare(arr); MergeSort.mergeSort(arr); // 합병정렬 s.printSort(arr); continue; case 5: prepare(arr); QuickSort.quickSort(arr, 0, arr.length - 1); // 합병정렬 s.printSort(arr); continue; case 6: prepare(arr); SelectionSort.selectionSort(arr); // 합병정렬 s.printSort(arr); continue; case 7: prepare(arr); ShellSort.shellSort(arr); // 합병정렬 s.printSort(arr); continue; case 0: System.out.println("종료되었습니다."); startEnd = false; } } } }
/* * 버블 정렬의 시간복잡도는 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) { // 정렬 알고리즘 시작 시간 기록 double 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; } } } // 정렬 알고리즘 종료 시간 기록 double endTime = System.nanoTime(); // 정렬 알고리즘 수행 시간 계산 double duration = (endTime - startTime) / 1000000; System.out.println("Bubble Sort 수행 시간: " + duration + "ns"); } }
// 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) { // 정렬 알고리즘 시작 시간 기록 double 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); // 힙 구조를 조정. } // 정렬 알고리즘 종료 시간 기록 double endTime = System.nanoTime(); // 정렬 알고리즘 수행 시간 계산 double duration = (endTime - startTime) / 1000000; 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; } }
// 삽입 정렬의 시간복잡도는 최선의 경우 o(n)이며 평균 및 최악의 경우에는 o(n^2) 입니다. // 이 같은 이유는 배열이 이미 정렬되어 있는 경우 최선의 경우가 되고 // 역순으로 정렬되어있으면 평균 및 최악의 경우가 됩니다. // 삽입 정렬은 순차적으로 배열에 우측으로 가면서 작은값이 있으면 올바른 위치의 왼쪽으로 삽입합니다. // 값이 왼쪽으로 끼어들게 되면 큰수들은 오른쪽으로 밀리게 됩니다. package sort; public class InsertionSort { // 삽입 정렬을 진행하는 InsertionSort 메소드를 만들었습니다. public static void InsertionSort(int[] arr) { // 정렬 알고리즘 시작 시간 기록 double 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값이 올바른 위치로 할당. } // 정렬 알고리즘 종료 시간 기록 double endTime = System.nanoTime(); // 정렬 알고리즘 수행 시간 계산 double duration = (endTime - startTime)/ 1000000; System.out.println("Insertion Sort 수행 시간: " + duration + "ns"); } }
// 병합정렬의 시간복잡도는 항상 o(n log n) 입니다. // 이는 배열을 반으로 조갠 후, 재귀적으로 정렬하고 다시 병합하는 방식으로 진행되기 때문입니다. package sort; public class MergeSort { public static void mergeSort(int[] arr) { // 정렬 알고리즘 시작 시간 기록 double 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++]; } } }
/* * QuickSort 알고리즘 * 최악의 경우 o(n^2) 인데 이는 피벗 기준으로 배열을 분할하고 정복하는 방법을 사용하기 때문에 발생합니다. * 또한 피벗을 선정하기 어려운 상황에서도 최악의 시간복잡도를 보여줍니다. * * 만일 균등하게 나누어지면 평균적으로 o(n log n)의 성능이 발생합니다. * */ package sort; public class QuickSort { // 오름차순으로 정렬 public static void quickSort(int[] arr, int low, int high) { // 정렬 알고리즘 시작 시간 기록 double startTime = System.nanoTime(); // low는 하한 인덱스, high는 상한 인덱스 if (low < high) { int pivotIndex = partition(arr, low, high); quickSort(arr, low, pivotIndex - 1); quickSort(arr, pivotIndex + 1, high); } // 정렬 알고리즘 종료 시간 기록 double endTime = System.nanoTime(); // 정렬 알고리즘 수행 시간 계산 double duration = (endTime - startTime)/1000000; 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; } }
// 시간복잡도 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) { // 정렬 알고리즘 시작 시간 기록 double 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; } } } // 정렬 알고리즘 종료 시간 기록 double endTime = System.nanoTime(); // 정렬 알고리즘 수행 시간 계산 double duration = (endTime - startTime)/1000000; System.out.println("Selection Sort 수행 시간: " + duration + "ns"); } }
// 셸 정렬의 시간복잡도는 최선, 평균, 최악의 경우 모두 o(n log n) 입니다. // 삽입 정렬의 단점을 보완하여 더 빠르게 동작하는 장점이 있기 때문에 평균적으로 좋은 성능을 보입니다. package sort; public class ShellSort { // 배열을 오름차순으로 정리하는 shellsort 메서드를 만들었습니다. public static void shellSort(int[] arr) { // 정렬 알고리즘 시작 시간 기록 double 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; } // 정렬 알고리즘 종료 시간 기록 double endTime = System.nanoTime(); // 정렬 알고리즘 수행 시간 계산 double duration = (endTime - startTime)/1000000; System.out.println("Shell Sort 수행 시간: " + duration + "ns"); } } // 셸 정렬은 삽입 정렬과 비교하여 평균적으로 좋은 성능을 보이며 빠르게 동작하는 장점이 있습니다.
case 문으로 버블정렬, 힙정렬, 삽입정렬, 합병정렬, 퀵정렬, 선택정렬, 셸정렬을 선택하여
수행시간을 계산한 값과 오름차순으로 정렬된 배열을 출력하는 코드를 만들었습니다.
배열의 크기는 [1000] 을 받았고 난수값을 만들어서 무작위로 숫자가 대입되도록 했습니다.
블로그의 정보
감성 개발자 효기
효기’s
