Day10 자료구조 정렬의 시간복잡도

- 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 수행 시간: 300ns

Quick Sort 수행 시간: 423700ns

Quick Sort 수행 시간: 2118100ns

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

저작자표시

'Algoritum' 카테고리의 다른 글

JAVA Linked List (29)	2023.07.19
JAVA 시간복잡도와 정렬 출력프로그램 (22)	2023.07.17
Day09 자료구조 정렬 알고리즘 (16)	2023.07.15
B 트리(B-tree) - 알고리즘 (0)	2022.12.06
버블정렬(bubble sort) - 알고리즘 (1)	2022.12.05

블로그의 정보

감성 개발자 효기

효기’s

Day10 자료구조 정렬의 시간복잡도

'Algoritum' 카테고리의 다른 글

블로그의 정보

활동하기

티스토리툴바

'Algoritum' 카테고리의 다른 글

블로그의 정보

활동하기

공유하기

다른 글

티스토리툴바