Hyogi's Notebook

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

활동하기