- 버블정렬 (Bubble Sort)
O(n^2) - 선택정렬 (Selection Sort)
O(n^2) - 삽입정렬 (Insert Sort)
O(n^2) - 퀵정렬 (Quick Sort)
O(n log n) - 병합정렬 (Merge Sort)
O(n log n) - 계수정렬 (Counting Sort)
O(n+K)
1. 버블 정렬 ( Bubble Sort )
- 버블 정렬 ( Bubble Sort )
인접한 두 요소를 검사해 정렬하는 알고리즘 (선택 정렬과 유사함)
인접한 2개의 레코드를 비교해 크기가 순서대로 되있지 않으면 서로 교환한다작동방식
- 배열의 첫 번째 요소부터 인접한 요소와 비교를 시작
- 인접요소 비교 및 교환 현재 요소가 인접한 요소보다 크면 두 요소의 위치를 교환
- 배열의 끝까지 진행
- 배열의 시작 부터 다시 비교,교환을 반복 (이미 정렬된 요소는 제외)
- 더 이상 교환이 필요 없을 때 까지 반복
public class BubbleSort { void bubbleSort(int arr[]) { int n = arr.length; for (int i = 0; i < n-1; i++) for (int j = 0; j < n-i-1; j++) if (arr[j] > arr[j+1]) { // 요소들의 위치 교환 int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } // 배열 출력용 유틸리티 메소드 void printArray(int arr[]) { int n = arr.length; for (int i=0; i<n; ++i) System.out.print(arr[i] + " "); System.out.println(); } // 메인 메소드로 실행 public static void main(String args[]) { BubbleSort ob = new BubbleSort(); int arr[] = {64, 34, 25, 12, 22, 11, 90}; ob.bubbleSort(arr); System.out.println("정렬된 배열:"); ob.printArray(arr); } }시간/공간 복잡도
- 최선의 경우 :
O(n)(이미 정렬된 경우)- 평균 및 최악의 경우 :
O(n^2)- 공간 복잡도 :
O(1): 버블 정렬은 추가적인 저장공간을 필요로 하지 않음장/단점
장점 :
- 구현이 매우 간단함 ,
- 추가적인 메모리 필요 없음
단점 :
- 평균적이고 최악의 경우 시간 복잡도가
O(n^2)으로 비효율적임,- 대규모 데이터셋에 부적합
2. 선택 정렬 ( Selection Sort )
- 선택 정렬 ( Selection Sort )
전체 목록에서 최소값을 찾아 해당 위치와 교환하는 알고리즘
전체 배열에서 최소값을 찾고, 이를 정렬되지 않은 부분의 첫 번째 위치와 교환함작동방식
- 배열의 전체 범위가 정렬대상
- 현재 정렬되지 않은 부분에서 최소값을 찾음
- 찾은 최소값을 정렬되지 않은 부분의 첫 번째 위치와 교환
- 정렬된 요소를 제외하고, 나머지 부분에 대해 같은 과정 반복
- 배열이 완전히 정렬 될 때까지 반복
public class SelectionSort { void selectionSort(int arr[]) { int n = arr.length; // 하나씩 이동하며 정렬되지 않은 부분을 처리 for (int i = 0; i < n-1; i++) { // 최소값을 찾기 위해 i번째 요소를 초기 최소값으로 설정 int min_idx = i; for (int j = i+1; j < n; j++) if (arr[j] < arr[min_idx]) min_idx = j; // 찾은 최소값을 정렬되지 않은 부분의 첫 번째 요소와 교환 int temp = arr[min_idx]; arr[min_idx] = arr[i]; arr[i] = temp; } } // 배열 출력용 유틸리티 메소드 void printArray(int arr[]) { int n = arr.length; for (int i=0; i<n; ++i) System.out.print(arr[i] + " "); System.out.println(); } // 메인 메소드로 실행 public static void main(String args[]) { SelectionSort ob = new SelectionSort(); int arr[] = {64, 25, 12, 22, 11}; ob.selectionSort(arr); System.out.println("정렬된 배열:"); ob.printArray(arr); } }시간/공간 복잡도
- 최선, 평균, 최악의 경우 :
O(n^2)- 공간 복잡도 :
O(1): 선택 정렬은 추가적인 저장공간 불필요장/단점
장점 :
- 구현이 간단하고 이해하기 귀움
- 메모리 사용이 적음
단점 :
- 시간 복잡도가
O(n^2)이므로 데이터의 양이 많음 비효율적- 안정적인 정렬 방식이 아님 ( 동일한값을 가진 요소의 상대적인 순서가 바뀔 수있음)
3. 삽입 정렬 ( Insert Sort )
- 삽입 정렬 ( Insert Sort )
각 요소를이미 정렬된 배열 부분에 올바른 위치에 삽입하는 알고리즘
각 반복에서 요소는 정렬된 부분에 삽입되어 정렬된 배열을 확장함작동방식
- 배열의 두 번째 요소부터 시작 ( 첫 번째 요소는 이미 정렬된 것으로 간주함 )
- 현재 요소를 정렬된 부분의 올바른 위치에 삽입
- 현재 요소보다 큰 모든 요소를 오른쪽으로 이동
- 현재 요소를 정렬된 부분에 삽입
- 다음 요소로 이동해 반복
public class InsertionSort { void insertionSort(int arr[]) { int n = arr.length; for (int i = 1; i < n; ++i) { int key = arr[i]; int j = i - 1; // 정렬된 부분에 key를 삽입할 위치 찾기 while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = key; } } // 배열 출력용 유틸리티 메소드 void printArray(int arr[]) { for (int i = 0; i < arr.length; ++i) System.out.print(arr[i] + " "); System.out.println(); } // 메인 메소드로 실행 public static void main(String args[]) { InsertionSort ob = new InsertionSort(); int arr[] = {12, 11, 13, 5, 6}; ob.insertionSort(arr); System.out.println("정렬된 배열:"); ob.printArray(arr); } }시간/공간 복잡도
- 최선의 경우 :
O(n)(이미 정렬 된 경우)- 평균 및 최악의 경우 :
O(n^2)- 공간 복잡도 :
O(1): 삽입 정렬은 추가적인 저장공간 불필요장/단점
장점 :
- 구현이 간단하고 작은 데이터셋에 효율적
- 안정적인(
stable) 정렬 방식단점 :
- 평균적이고 최악의 경우 시간 복잡도가
O(n^2)으로 비효율적- 데이터셋이 클 경우 다른 고급 정렬 알고리즘에 비해 느림
4. 퀵 정렬 ( Quick Sort )
- 퀵 정렬 ( Quick Sort )
피벗을 기준으로 하여 큰 값과 작은 값의 배열을 분할, 각 부분을 재귀적으로 정렬하는 알고리즘
인접한 2개의 레코드를 비교해 크기가 순서대로 되있지 않을시 서로 교환작동방식
- 배열애서 '피벗' 요소를 선택 ( 일반적으로 첫 번째, 마지막, 중간값 등을 사용 )
- 피벗보다 작은 요소와 큰 요소를 분할
- 분할된 각 부분에 대해 재귀적으로 동일한 과정 반복
- 더 이상 분할할 수 없을 때까지 반복
public class QuickSort { /* 배열 arr의 left부터 right까지를 정렬하는 함수 */ void quickSort(int arr[], int left, int right) { if (left < right) { // 분할(partition) 과정을 통해, pivot의 최종 위치인 partitionIndex를 구한다. int partitionIndex = partition(arr, left, right); // pivot의 왼쪽 부분 배열 정렬 quickSort(arr, left, partitionIndex - 1); // pivot의 오른쪽 부분 배열 정렬 quickSort(arr, partitionIndex + 1, right); } } /* 배열을 pivot을 기준으로 분할하고, pivot의 최종 위치를 반환하는 함수 */ int partition(int arr[], int left, int right) { int pivot = arr[right]; // 배열의 맨 오른쪽 요소를 pivot으로 선택 int i = (left - 1); // i는 pivot보다 작은 요소의 마지막 인덱스를 추적 for (int j = left; j < right; j++) { // 현재 요소가 pivot보다 작거나 같으면, i를 증가시키고 arr[i]와 arr[j]를 교환 if (arr[j] <= pivot) { i++; // arr[i]와 arr[j] 교환 int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } // pivot을 올바른 위치로 이동 int temp = arr[i + 1]; arr[i + 1] = arr[right]; arr[right] = temp; return i + 1; // pivot의 최종 위치 반환 } // 배열을 출력하는 함수 static void printArray(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[] = {10, 7, 8, 9, 1, 5}; int n = arr.length; QuickSort ob = new QuickSort(); ob.quickSort(arr, 0, n-1); System.out.println("정렬된 배열: "); printArray(arr); } }시간/공간 복잡도
- 최선의 경우 :
O(n log n)- 평균의 경우 :
O(n log n)- 최악의 경우 :
O(n^2)- 공간 복잡도 : 재귀 호출의 깊이에 의해 결정
장/단점
장점 :
- 높은 효율성 : 평균적으로
O(n log n)의 시간복잡도를 가짐, 매우빠름- 내부 정렬방식:
- 추가 메모리 사용량 적음 : 퀵 정렬은
in-place정렬 알고리즘으로, 분할 정복 방식이기 때문에 추가적인 메로리 요구량이 적음- 최적화 용이 : 피벗 선택 방식을 최적화해 최악의 경우를 방지하고 평균적인 성능을 개선할 수 있음 예를 들어
중간값의 중간값(Median of Median)알고리즘을 사용해 피벗을 선택하면 최악의 시간 복잡도를O(n log n)으로 제한할 수 있음단점 :
- 최악의 경우 시간복잡도 : 잘못된 피벗 선택으로 인해 배열이 균등하게 분할되지 않으면 최악의 경우 시간복잡도가
O(n^2)까지 증가할 수있음 이는 배열이 이미 정렬되어 있거나 거의 정렬된 경우 발생함- 불안정 정렬: 같은 값의 요소가 원래의 순서를 유지하지 않을 수 있음 이는 데이터의 상대적인 순서가 중요한 경우 문제가 될 수 있음
- 재귀 호출의 오버헤드 : 대규모 데이터 세트에 대해 깊은 재귀 호출이 발생할 수있음 이로 인해 스택오버플로를 일으킬 위험이있음 이를 방지하기 위해 재귀 호출 대신 반복문을 사용하는 하이브리드 접근방식을 취할 수 있음
5. 병합 정렬 ( Merge Sort )
- 병합 정렬 ( Merge Sort )
두 개의 부분으로 분할한 뒤 각각을 정렬하여 다시 병합하는 분할 정복 알고리즘
분할 정복 방식을 통해 전체 배열을 재귀적으로 정렬작동방식
- 배열을 반으로 나눔(분할)
- 각 부분을 재귀적으로 정렬
- 두 부분을 다시 하나로병합
- 배열이 하나의 요소만을가질때까지 분할을 반복 ( 분할된 배열이 하나의 요소를가지면정렬된 것으로 간주)
public class MergeSort { // 주어진 배열을 병합 정렬하는 메소드 void mergeSort(int arr[], int l, int r) { if (l < r) { // 중간 지점 찾기 int m = l + (r - l) / 2; // 첫 번째와 두 번째 절반을 정렬 mergeSort(arr, l, m); mergeSort(arr, m + 1, r); // 병합 merge(arr, l, m, r); } } // 두 부분 배열을 병합하는 메소드 void merge(int arr[], int l, int m, int r) { // 크기 계산 int n1 = m - l + 1; int n2 = r - m; // 임시 배열 생성 int L[] = new int[n1]; int R[] = new int[n2]; // 데이터 복사 for (int i = 0; i < n1; ++i) L[i] = arr[l + i]; for (int j = 0; j < n2; ++j) R[j] = arr[m + 1 + j]; // 병합 int i = 0, j = 0; int k = l; while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; } // 남은 요소 복사 while (i < n1) { arr[k] = L[i]; i++; k++; } while (j < n2) { arr[k] = R[j]; j++; k++; } } // 배열 출력용 유틸리티 메소드 void printArray(int arr[]) { for (int i = 0; i < arr.length; ++i) System.out.print(arr[i] + " "); System.out.println(); } // 메인 메소드로 실행 public static void main(String args[]) { MergeSort ob = new MergeSort(); int arr[] = {12, 11, 13, 5, 6, 7}; ob.mergeSort(arr, 0, arr.length - 1); System.out.println("정렬된 배열:"); ob.printArray(arr); } }시간/공간 복잡도
최선의 경우 :
O(n log n)
평균의 경우 :O(n log n)
최악의 경우 :O(n log n)
공간 복잡도 :O(n): 병합 과정에서 임시배열을 사용하기 떄문에장/단점
장점 :
- 크기에 상관없이 시간복잡도가
O(n log n)로 안정적- 큰 데이터셋에 효율적이며,안정적인(
stable) 정렬 방식단점 :
- 추가적인 메모리 공간(임시 배열)을 필요로함
In-place정렬이 아님
6. 계수 정렬 ( Counting Sort )
- 계수 정렬 ( Counting Sort )
비교를 하지 않고 정렬을 수행하는 알고리즘으로, 정수나 정수로 표현될 수 있는 객체들을 정렬할 때 사용됨,
각 요소의 출현 횟수를 세어, 그 횟수를 바탕으로 전체 배열을 정렬함작동방식
- 입력 배열에서 최소값과 최대값을 찾음
- 최소값과 최대값의 범위에 해당하는 크기의 계수 배열(count array)을 생성하고, 모든 값을 0으로 초기화
- 입력 배열을 순회하면서 각 요소가 나타난 횟수를 계수 배열에 기록
- 계수 배열을 순회하면서, 각 요소의 누적 합을 계산합니다. 이는 해당 요소의 최종 위치를 결정하는 데 사용
- 누적 합을 바탕으로 입력 배열의 요소를 결과 배열에 올바른 위치에 배치
- 예시
정렬하려는 배열 : [ 4, 2, 2, 8, 3, 3, 1 ]
- 카운팅 배열 초기화 : 숫자의 범위가 1~8이라 가정할 때 크기가 8인 카운팅 배열을 0으로 초기화
- 카운팅 배열 채우기 :입력 배열을 탐색하며 각 숫자가 등장하는 횟수를 카운팅배열에 기록
- 누적 카운트 계산 : 카운팅배열의 각 요소를 그 이전 요소들의 합으로 업데이트
- 결과 배열 생성 : 입력배열을 다시 탐색하면서 각 숫자를 카운팅 배열에 따라 결과 배열에 올바르게 배치
public class CountingSort { void sort(int arr[]) { int n = arr.length; // 배열 arr에서 최대값 찾기 int max = arr[0]; for (int i = 1; i < n; i++) { if (arr[i] > max) max = arr[i]; } // 카운트 배열(count array) 초기화 int[] count = new int[max + 1]; // arr[]의 각 숫자의 발생 횟수 세기 for (int i = 0; i < n; i++) { count[arr[i]]++; } // 카운트 배열 변경: 각 값의 실제 위치를 반영 for (int i = 1; i <= max; i++) { count[i] += count[i - 1]; } // 결과 배열(result array) 초기화 int[] output = new int[n]; // 결과 배열 채우기 for (int i = n - 1; i >= 0; i--) { output[count[arr[i]] - 1] = arr[i]; count[arr[i]]--; } // arr[]를 정렬된 배열로 복사 for (int i = 0; i < n; i++) { arr[i] = output[i]; } } // 배열 출력 메소드 static void printArray(int arr[]) { for (int i : arr) System.out.print(i + " "); System.out.println(); } // 메인 메소드 public static void main(String args[]) { CountingSort ob = new CountingSort(); int arr[] = {4, 2, 2, 8, 3, 3, 1}; System.out.println("Original Array:"); printArray(arr); ob.sort(arr); System.out.println("Sorted Array:"); printArray(arr); } }시간/공간 복잡도
시간 복잡도 :
O(N+K): N = 입력배열의 크기 , K = 입력 배열 내의 값 중 최댓값
공간복잡도 :O(K): K = 계수 배열을 저장하기 위한공간장/단점
장점 :
- 비교를 하지 않고 정렬 수행하여, 작은 범위의 정수에 대해선 매우 빠른 속도를 제공
- 안정적인(
stable) 정렬 방식단점 :
- K의 값이 큰경우 많은 메모리를 필요함 (데이터의 범위가 넓을수록 공간복잡도 증가)
- 정수나정수로 변활할 수 있는 데이터만 사용할 수 있음
LMR