Day09 자료구조 정렬 알고리즘
by 효기’s
- 정렬
일정한 기준으로 자료의 순서를 변경하는 알고리즘을 정렬(sort)이라 한다.
오름차순 = 1234589
내림차순 = 985421
O(1) - 상수 시간: 입력 크기에 관계없이 일정한 실행 시간을 갖는 알고리즘입니다. 예를 들어, 배열에서 첫 번째 요소를 반환하는 것과 같은 간단한 연산이 이에 해당합니다.
O(log n) - 로그 시간: 입력 크기의 로그에 비례하는 실행 시간을 갖는 알고리즘입니다. 이진 검색(Binary Search)과 같은 분할 정복 알고리즘이 이에 해당합니다.
O(n) - 선형 시간: 입력 크기에 비례하여 선형적으로 실행 시간이 증가하는 알고리즘입니다. 배열의 모든 요소를 한 번씩 처리하는 경우가 이에 해당합니다.
O(n log n) - 선형 로그 시간: 입력 크기에 비례하여 로그 선형적으로 실행 시간이 증가하는 알고리즘입니다. 효율적인 정렬 알고리즘인 병합 정렬(Merge Sort)과 퀵 정렬(Quick Sort)이 이에 해당합니다.
O(n^2) - 이차 시간: 입력 크기의 제곱에 비례하는 실행 시간을 갖는 알고리즘입니다. 버블 정렬(Bubble Sort)이나 선택 정렬(Selection Sort)과 같은 단순한 정렬 알고리즘이 이에 해당합니다.
O(2^n) - 지수 시간: 입력 크기에 대해 지수적으로 실행 시간이 증가하는 알고리즘입니다. 조합적인 문제나 하위 집합을 생성하는 경우가 이에 해당합니다.
O(n!) - 계승 시간: 입력 크기에 대해 팩토리얼에 비례하는 실행 시간을 갖는 알고리즘입니다. 순열 문제와 같이 모든 가능한 순서를 고려해야 하는 경우가 이에 해당합니다.
선택 정렬 (Selection Sort):
정의: 배열을 순회하면서 가장 작은 값을 선택하여 정렬된 부분과 교환하는 정렬 알고리즘입니다.
사용 방법: 배열을 순회하며 가장 작은 값을 찾아 맨 앞으로 보내는 과정을 반복합니다. 시간 복잡도는 O(n^2)입니다.
장점 : 1. 구현이 간단하고 이해하기 쉽습니다.
2. (주어진 리스트 안에서 원소들을 서로 교환하며 정렬하는 방식이므로) 추가 메모리 공간이 필요하지 않습니다.
단점 : 1. 성능이 느립니다.
2. 비교 횟수가 많습니다.
package sort;
public class SelectionSort {
public static void selectionSort(int[] arr) {
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;
}
}
}
}
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 + " "); // 결과
}
}
}
버블 정렬 (Bubble Sort):
정의: 인접한 두 원소를 비교하여 필요에 따라 위치를 교환하는 정렬 알고리즘입니다.
사용 방법: 배열을 순회하면서 인접한 원소를 비교하고 필요에 따라 위치를 교환하는 과정을 반복합니다. 시간 복잡도는 O(n^2)입니다.
장점 : 1. 구현이 간단하고 이해하기 쉽습니다.
2. 추가 메모리 공간이 거의 필요하지 않습니다.
단점 : 1. 성능이 느립니다.
2. (인접한 두 원소를 계속하여 비교하여 정렬하기 때문에) 비교 횟수가 많습니다.
package sort;
public class BubbleSort {
public static void bubbleSort(int[] arr) {
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;
}
}
}
}
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 + " "); // 결과
}
}
}
삽입 정렬 (Insertion Sort):
정의: 배열을 정렬된 부분과 비교하여 올바른 위치에 삽입하는 정렬 알고리즘입니다.
사용 방법: 배열을 순회하면서 각 원소를 정렬된 부분과 비교하여 올바른 위치에 삽입하는 과정을 반복합니다. 시간 복잡도는 O(n^2)입니다.
장점 : 1. 구현이 간단하고 이해하기 쉽습니다.
2. 추가 메모리 공간이 거의 필요하지 않습니다.
단점 : 1. 성능이 느립니다.
2. 삽입할 위치를 찾기위해 정렬된 부분을 순차적으로 비교해야 하므로 비교 횟수가 상당히 많습니다.
// 삽입 정렬은 순차적으로 배열에 우측으로 가면서 작은값이 있으면 올바른 위치의 왼쪽으로 삽입합니다.
// 값이 왼쪽으로 끼어들게 되면 큰수들은 오른쪽으로 밀리게 됩니다.
package sort;
public class InsertionSort {
// 삽입 정렬을 진행하는 InsertionSort 메소드를 만들었습니다.
public static void InsertionSort(int[] arr) {
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값이 올바른 위치로 할당.
}
}
// 메인에서는 배열의 값과 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 + " "); // 결과
}
}
}
병합 정렬 (Merge Sort):
정의: 배열을 분할하고 분할된 배열을 병합하여 정렬하는 정렬 알고리즘입니다.
사용 방법: 배열을 분할하여 각 부분 배열을 정렬하고, 정렬된 부분 배열을 병합하여 전체 배열을 정렬하는 과정을 반복합니다. 시간 복잡도는 O(n log n)입니다.
장점 : 1. 안정적인 정렬 알고리즘입니다.
2. 빠른 성능을 제공합니다.
단점 : 1. (재귀적으로 호출되는 과정에서 임시 배열이 필요하여) 추가 메모리 공간이 필요합니다.
2. 구현이 상대적으로 복잡합니다.
3. 성능이 느릴 수 있습니다.
package sort;
public class MergeSort {
public static void mergeSort(int[] arr) {
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를 통해 병합
}
// 정렬된 왼쪽 부분과 오른쪽 부분을 병합하여 하나의 배열로 합치는 메소드
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 + " "); // 결과
}
}
}
퀵 정렬 (Quick Sort):
정의: 피벗(pivot)을 기준으로 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 분할하여 정렬하는 정렬 알고리즘입니다.
사용 방법: 배열에서 피벗을 선택하고, 피벗을 기준으로 작은 값과 큰 값으로 분할하여 각 부분 배열을 정렬하는 과정을 반복합니다. 시간 복잡도는 평균적으로 O(n log n)입니다.
장점 : 1. 데이터를 바르게 분할하고 정복하기 때문에 대부분의 경우 빠른 정렬을 보여줍니다.
2. 공간 복잡도 : 추가적인 메모리를 거의 사용하지 않고 원래의 배열 내에서 정렬을 수행합니다.
3. 캐쉬 효율성 : 데이터를 분할하여 정렬하므로 캐시 메모리의 지역성을 잘 활용할 수 있습니다.
4. 불안정 정렬 : 퀵 정렬은 기본적으로 불안정한 정렬이지만 안정성을 보장하는 알고리즘보다 빠르게 동작합니다.
단점 : 1. 최악의 경우 성능은 데이터의 초기 상태와 피벗 선택에 따라 좌지우지 된다.
분할이 되지않아 최악의 경우 o(n^2)의 시간 복잡도를 갖게 될 수 있습니다.
2. 외부 정렬 문제
package sort;
public class QuickSort {
// 오름차순으로 정렬
public static void quickSort(int[] arr, int low, int high) {
// low는 하한 인덱스, high는 상한 인덱스
if (low < high) {
int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}
// 피벗 인덱스를 구하는 역할을 합니다.
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 + " "); // 결과
}
}
}
힙 정렬 (Heap Sort):
정의: 배열을 힙(heap)으로 만들고, 힙에서 가장 큰 값을 반복적으로 추출하여 정렬하는 정렬 알고리즘입니다.
사용 방법: 배열을 힙으로 만들어 최대 힙(또는 최소 힙) 구조를 구성하고, 힙에서 가장 큰 값을 추출하여 배열의 뒷부분부터 채워나가는 과정을 반복합니다. 시간 복잡도는 O(n log n)입니다.
장점 : 1. 힙 정렬은 안정적인 정렬 알고리즘입니다. 동일 값들이 있는 경우에도 원래 순서가 유지됩니다.
2. 최악, 평균, 최선의 경우 모두 o(n log n)의 시간 복잡도를 가집니다. 대부분 빠른 성능을 제공합니다.
3. 추가 메모리 사용량 : 힙 정렬은 원래의 배열 내에서 정렬을 수행하므로 추가 메모리가 필요없습니다.
따라서 공간 복잡도가 낮습니다.
4. 선택정렬보다 효율적
단점 : 1. 안정성과 관련된 오버페드 : 힙 정렬은 안정한 정렬이므로 정렬의 안정성을 보장해야 하므로 이로인해
오버헤드가 발생할 수 있습니다.
2. 상수 요소의 영향
3. 배열 외부 정렬 : 힙정렬은 주로 배열을 기반으로 하기 때문에 대량의 데이터를 정렬할 때는 외부 정렬을 고려해야
할수도 있습니다.
package sort;
public class HeapSort {
public static void heapSort(int[] arr) {
// 힙을 구성
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); // 힙 구조를 조정.
}
}
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 + " "); // 결과
}
}
}
셸 정렬 (Shell Sort):
정의: 배열을 일정한 간격으로 분할하여 각 부분 배열을 삽입 정렬하며 정렬하는 정렬 알고리즘입니다.
사용 방법: 배열을 일정한 간격으로 분할하여 부분 배열을 삽입 정렬하고, 간격을 점차 줄여가며 정렬하는 과정을 반복합니다. 시간 복잡도는 최선의 경우에 O(n log^2 n)입니다.
장점 : 1. 셸정렬은 일반적으로 삽입 정렬보다 빠른 속도를 가집니다. 데이터를 미리 정렬된 부분 리스트로 분할하여
부분적으로 정렬하므로 평균적 시간 복잡도는 o(n log n)입니다.
2. 안정적인 정렬 알고리즘입니다. 동일 값들이 있는 경우에도 원래의 순서가 유지됩니다.
3. 적은 스왑 횟수 : 삽입 정렬과 달리 쉘 정렬은 멀리 떨어진 요소끼리 비교하고 교환하기 대문에 더 적은 스왑(교환)
횟수를 필요로 합니다.
4. 추가 메모리 사용량 : 원래의 배열 내에서 정렬을 수행하므로 추가적인 메모리가 거의 필요하지 않습니다.
따라서 공간 복잡도가 작습니다.
단점 : 1. 불안정성 : 셸 정렬은 간격에 따라서 요소를 비교하고 교환하여 안정적이지 않을수 있습니다.
2. 간격 선택의 어려움 : 간격 선택에 따라 성능이 크게 달라질 수 있습니다.
3. 최선의 경우에도 성능 한계 : 최선의 경우에도 다른 정렬 알고리즘들보다 더 나은 성능을 보장하지 않습니다.
package sort;
public class ShellSort {
// 배열을 오름차순으로 정리하는 shellsort 메서드를 만들었습니다.
public static void shellSort(int[] arr) {
// 배열의 길이를 변수 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;
}
}
// 메인에 배열값과 공백을 넣어서 결과를 출력합니다.
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 + " "); // 결과
}
}
}
// 셸 정렬은 삽입 정렬과 비교하여 평균적으로 좋은 성능을 보이며 빠르게 동작하는 장점이 있습니다.'Algoritum' 카테고리의 다른 글
| JAVA 시간복잡도와 정렬 출력프로그램 (22) | 2023.07.17 |
|---|---|
| Day10 자료구조 정렬의 시간복잡도 (20) | 2023.07.17 |
| B 트리(B-tree) - 알고리즘 (0) | 2022.12.06 |
| 버블정렬(bubble sort) - 알고리즘 (1) | 2022.12.05 |
| 해싱(hashing) - 알고리즘 (2) | 2022.12.02 |
블로그의 정보
감성 개발자 효기
효기’s