정렬 알고리즘
1. 선형 검색: 이 알고리즘은 배열에서 특정 값을 찾기 위해 순차적으로 검색합니다.
public static int linearSearch(int[] arr, int x) {
int n = arr.length;
for (int i = 0; i < n; i++) {
if (arr[i] == x) {
return i;
}
}
return -1;
}
2. 이진 검색: 이 알고리즘은 정렬된 배열에서 반복적으로 검색 구간을 반으로 나누어 대상 값을 찾습니다.
public static int binarySearch(int[] arr, int x) {
int left = 0, right = arr.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == x) {
return mid;
}
if (arr[mid] < x) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
3. 버블 정렬: 이 알고리즘은 배열을 반복적으로 탐색하면서 인접한 요소를 비교하고 필요한 경우 위치를 교환하여 정렬합니다.
public static 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;
}
}
}
}
4. 선택 정렬: 이 알고리즘은 배열에서 가장 작은 값을 찾아 처음부터 차례로 정렬합니다.
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n-1; 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;
}
}
5. 삽입 정렬: 이 알고리즘은 배열을 순회하면서 각 요소를 정확한 위치에 삽입하여 최종 정렬된 배열을 만듭니다.
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = key;
}
}
6. 병합 정렬: 이 알고리즘은 배열을 두 개의 반으로 나눈 다음, 각각을 재귀적으로 정렬하고 다시 병합합니다.
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid+1, right);
merge(arr, left, mid, right);
}
}
public static void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int[] L = new int[n1];
int[] R = new int[n2];
for (int i = 0; i < n1; i++) {
L[i] = arr[left + i];
}
for (int j = 0; j < n2; j++) {
R[j] = arr[mid + 1 + j];
}
int i = 0, j = 0, k = left;
7. 퀵 정렬: 이 알고리즘은 피벗 요소를 선택하고, 배열을 피벗을 기준으로 분할하여 부분 배열을 재귀적으로 정렬합니다.
public static void quickSort(int[] arr, int left, int right) {
if (left < right) {
int pivot = partition(arr, left, right);
quickSort(arr, left, pivot-1);
quickSort(arr, pivot+1, right);
}
}
public static int partition(int[] arr, int left, int right) {
int pivot = arr[right];
int i = left - 1;
for (int j = left; j < right; j++) {
if (arr[j] <= pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i+1];
arr[i+1] = arr[right];
arr[right] = temp;
return i+1;
}
8. 계수 정렬: 이 알고리즘은 서로 다른 키 값을 가진 객체의 수를 계산하고, 출력 시퀀스에서 각 객체의 위치를 계산합니다.
public static void countingSort(int[] arr) {
int n = arr.length;
int max = Arrays.stream(arr).max().orElse(0);
int[] count = new int[max+1];
int[] output = new int[n];
for (int i = 0; i < n; i++) {
count[arr[i]]++;
}
for (int i = 1; i <= max; i++) {
count[i] += count[i-1];
}
for (int i = n-1; i >= 0; i--) {
output[count[arr[i]]-1] = arr[i];
count[arr[i]]--;
}
for (int i = 0; i < n; i++) {
arr[i] = output[i];
}
}
