기본 정렬 알고리즘
- 버블 정렬
- 삽입 정렬
- 선택 정렬
- 합병 정렬
버블 정렬
인접한 두개의 원소를 비교하는 정렬.
인접해서 비교하기 때문에 가장 큰 원소는 배열의 마지막에 위치하게 된다.
각 회전마다 배열에서 제외되는 요소가 배열의 뒤에서부터 추가된다.
시간복잡도는 O(n^2)
private static void bubbleSort(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
for (int j = 0; j < a.length - i - 1; j++) {
if (a[j] > a[j + 1]) {
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}
삽입 정렬
두번째 원소부터 앞의 원소와 비교하는 정렬.
앞의 원소들을 차례대로 비교하며 삽입 될 위치에 원소를 넣고 뒤의 원소를 한칸씩 뒤로 보낸다.
시간복잡도는 O(n), 역순으로 정렬된 배열이라면 O(n^2)
private static void insertionSort(int[] a) {
for (int i = 1; i < a.length; i++) {
int num = a[i]; //비교할 원소
int j = i - 1; //앞의 원소
while (j >= 0 && num < a[j]) { //앞의 원소가 더 크다면 바꿔준다
a[j + 1] = a[j];
j--;
}
a[j + 1] = num;
}
}
선택 정렬
첫번째 원소를 두번째부터 마지막까지 비교하며 최소값을 첫번째 위치에,
두번째 원소를 세번째부터 마지막까지 비교하며 최소값을 두번째 위치에 ....
이런 식으로 위치는 정해져 있으며 어떤 원소를 넣을지 찾는 정렬 방법.
불안정 정렬에 속한다.
시간복잡도는 O(n^2)
private static void selectionSort(int[] a) {
for (int i = 0; i < a.length; i++) {
int now = i; //전환할 인덱스
for (int j = i + 1; j < a.length; j++) {
if (a[j] < a[now]) //최소값이 담긴 인덱스 찾기
now = j;
}
int temp = a[now];
a[now] = a[i];
a[i] = temp;
}
}
병합 정렬
분할 정복 알고리즘.
divide and conquer의 과정을 거친다.
배열의 크기가 1이 될 때까지 나누고, 합치는 과정.
추가 메모리를 사용한다는 특징이 있다.
시간복잡도는 O(nlogn)
private static void mergeSort(int[] a, int left, int right) {
//main 함수 호출 부분
//mergeSort(arr, 0, arr.length - 1);
if (left < right) {
int mid = (left + right) / 2;
mergeSort(a, left, mid);
mergeSort(a, mid + 1, right);
merge(a, left, mid, right);
}
}
private static void merge(int[] a, int left, int mid, int right) {
int[] temp = a.clone();
int i = left; //왼쪽 배열의 시작 인덱스
int j = mid + 1; //오른쪽 배열의 시작 인덱스
int idx = left; //정렬된 값을 넣을 위치 인덱스
//왼쪽 배열과 오른쪽 배열 비교하며 작은 원소부터 추가
while (i <= mid && j <= right) {
if (temp[i] < temp[j]) {
a[idx++] = temp[i++];
} else {
a[idx++] = temp[j++];
}
}
if (mid < i) { //오른쪽 남은 배열 채우기
for (int k = j; k <= right; k++) {
a[idx++] = temp[k];
}
} else { //왼쪽 남은 배열 채우기
for (int k = i; k <= mid; k++) {
a[idx++] = temp[k];
}
}
}'CS > Algorithm' 카테고리의 다른 글
| [알고리즘 정리] 그래프 (Graph)와 Floyd warshall 알고리즘 (0) | 2022.12.19 |
|---|
