1. 선택 정렬 (Selection Sort)
선택 정렬은 가장 간단 하면서 비효율적인 정렬 알고리즘이다.
1. 배열에서 최소값(또는 최대값)을 찾는다.
2. 최소값(또는 최대값)을 배열의 맨 앞의 원소와 교환한다.
3. 정렬된 부분의 배열을 제외하고 나머지 배열에서 위 과정을 반복한다.
자바로 구현하기
import java.util.Scanner;
public class SelectionSort {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int num = Integer.parseInt(scanner.nextLine());
int[] arr = new int[num];
for (int i = 0; i < num; i++) {
arr[i] = scanner.nextInt();
}
print(arr);
sort(arr);
print(arr);
}
public static void sort(int[] arr){
int n = arr.length;
for (int i = 0; i < n; i++) {
int minIndex = i;
for (int j = i+1; j < n; j++) {
if(arr[minIndex] > arr[j]){
minIndex = j;
}
}
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
private static void print(int[] arr) {
System.out.print(">>");
for (int i : arr) {
System.out.print(i+" ");
}
System.out.println();
}
}
시간복잡도
외부 루프는 n번 반복하고, 내부 루프는 각 외부 루프에 대해 n-i번 반복한다.
따라서 비교 횟수는 (n-1) + (n-2) + ... + 1 = n(n-1)/2 이고
시간복잡도는 최선, 평균, 최악의 경우 모두 O(n^2)이다.
2. 삽입 정렬 (Insertion Sort)
삽입 정렬은 정렬되지 않은 부분과 정렬된 부분으로 나누어 진행하는 알고리즘이다.
1. 배열의 첫 번째 원소를 정렬된 부분으로 간주한다.
2. 정렬되지 않은 부분에서 하나의 원소를 선택하여 정렬된 부분의 올바른 위치에 삽입한다.
3. 이를 배열의 끝까지 반복하여 정령을 완성한다.
자바로 구현하기
import java.util.Scanner;
public class InsertionSort {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int num = Integer.parseInt(scanner.nextLine());
int[] arr = new int[num];
for (int i = 0; i < num; i++) {
arr[i] = scanner.nextInt();
}
print(arr);
sort(arr);
}
public static void sort(int[] arr){
int n = arr.length;
for (int i = 1; i < n; i++) {
int select = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > select) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = select;
print(arr);
}
}
public static void print(int[] arr){
System.out.print(">>");
for (int i : arr) {
System.out.print(i+" ");
}
System.out.println();
}
}
실행 결과
시간복잡도
최선의 경우 (정렬된 배열이 주어질 때) : O(n)
최악의 경우 (역으로 정렬된 배열이 주어질 때) : O(n^2)
평균 : O(n^2)
3. 버블 정렬 ( Bubble Sort)
1. 배열의 첫 번째 원소부터 마지막 원소까지 반복하면서 인접한 두 원소를 비교한다.
2. 만약 현재 원소가 다음 원소보다 크다면, 두 원소의 위치를 서로 교환한다.
3. 한 번의 반복이 끝나면 가장 큰 원소가 배열의 마지막으로 이동한다.
4. 위의 과정을 반복한다.
자바로 구현하기
import java.util.Scanner;
public class BubbleSort {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int num = Integer.parseInt(scanner.nextLine());
int[] arr = new int[num];
for (int i = 0; i < num; i++) {
arr[i] = scanner.nextInt();
}
sort(arr);
}
public static void sort(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;
}
print(arr, i);
}
}
}
public static void print(int[] arr, int ord){
System.out.print(ord + "번째 루프 >>");
for (int i : arr) {
System.out.print(i+" ");
}
System.out.println();
}
}
실행 결과
시간복잡도
최선의 경우 (이미 정렬된 배열의 경우) : O(n)
최악 및 평균의 경우 : O(n^2)
4. 합병 정렬 (Merge Sort)
합병 정렬은 분할 정복(divide and conquer) 알고리즘 중 하나이다.
배열을 반으로 나눈 후 각각의 배열을 재귀적으로 정렬한 후, 정렬된 부분 배열을 합쳐 전체 배열을 정렬하는 방식을 사용한다.
1. 분할(Divide) : 정렬되지 않은 배열을 반으로 나눈다.
2. 정복(Conquer) : 각각의 하위 배열에 대해 재귀적으로 합병 정렬을 수행한다.
3. 합병(Merge) : 정렬된 두 하위 배열을 합병하여 하나의 정렬된 배열로 만든다.
자바로 구현하기
import java.util.Arrays;
import java.util.Scanner;
public class MergeSort {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int num = Integer.parseInt(scanner.nextLine());
int[] arr = new int[num];
for (int i = 0; i < num; i++) {
arr[i] = scanner.nextInt();
}
sort(arr, 0, arr.length - 1);
}
public static void sort(int[] arr, int start, int end) {
if (start == end) {
return;
}
sort(arr, start, (start + end) / 2);
sort(arr, (start + end) / 2 + 1, end);
merge(arr, start, end);
}
private static void merge(int[] arr, int start, int end) {
int[] front = Arrays.copyOfRange(arr, start, (start + end) / 2 + 1);
int[] back = Arrays.copyOfRange(arr, (start + end) / 2 + 1, end + 1);
print(front, 0, front.length - 1, "front");
print(back, 0, back.length -1, "back");
int frontIndex = 0;
int backIndex = 0;
int sortArrIndex = start;
while (frontIndex < front.length && backIndex < back.length) {
if (front[frontIndex] < back[backIndex]) {
arr[sortArrIndex++] = front[frontIndex++];
} else {
arr[sortArrIndex++] = back[backIndex++];
}
}
while(frontIndex < front.length){
arr[sortArrIndex++] = front[frontIndex++];
}
while(backIndex < back.length){
arr[sortArrIndex++] = back[backIndex++];
}
print(arr, start, end, "merge");
}
public static void print(int[] arr, int start, int end, String str){
System.out.print(str + " >>");
while (start <= end) {
System.out.print(" " + arr[start++]);
}
System.out.println();
}
}
실행 결과
시간복잡도
합병 정렬의 시간 복잡도는 최선, 최악의 경우 모두 O(n logn)이다.
- 분할 하는 과정에서는 상수 시간이 소요되므로 O(1)
- 두 하위 배열을 합병하는 과정에서 O(n)
재귀 호출을 통해 배열을 계속해서 반으로 나누게 되므로, log n단계 만큼 수행하게 되고 총 시간 복잡도는 O(n log n)이 계산된다.
5. 퀵 정렬 (Quick Sort)
퀵 정렬은 분할 정복(divide and conquer) 알고리즘 중 하나이다.
평균적으로 매우 빠른 정렬 알고리즘이다.
특정 원소를 기준(pivot)으로 선택하고, 피봇 보다 작은 원소는 왼쪽으로, 큰 원소는 오른쪽으로 분할하여 정렬하는 방식을 사용한다.
1. 피봇 선택 : 배열에서 임의의 원소를 선택하거나, 중간 원소를 선택하는 등의 방법으로 피봇을 선택한다.
2. 파티션 : 피봇을 기준으로 배열을 두 그룹으로 분할한다. 피봇보다 작은 원소는 왼쪽으로, 큰 원소는 오른쪽으로 이동시킨다.
3. 재귀 호출 : 분할된 두 그룹에 대해 재귀적으로 퀵 정렬을 수행한다.
5. 정렬 완료 : 각 재귀 호출이 완료되면 전체 배열이 정렬된다.
자바로 구현하기
import java.util.Scanner;
public class QuickSort {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int num = Integer.parseInt(scanner.nextLine());
int[] arr = new int[num];
for (int i = 0; i < num; i++) {
arr[i] = scanner.nextInt();
}
sort(arr, 0, arr.length - 1);
print(arr, 0, arr.length - 1);
}
public static void sort(int[] arr, int start, int end){
if(start >= end){
return;
}
int pivotIndex = partition(arr, start, end);
sort(arr, start, pivotIndex -1);
sort(arr, pivotIndex + 1, end);
}
private static int partition(int[] arr, int start, int end) {
int pivotIndex = end;
int index = start;
print(arr, start, end);
for (int i = 0; i < end - start; i++) {
if (arr[index] > arr[pivotIndex]) {
int temp = arr[pivotIndex];
arr[pivotIndex] = arr[index];
arr[index] = arr[pivotIndex - 1];
arr[pivotIndex - 1] = temp;
pivotIndex--;
} else {
index++;
}
}
return pivotIndex;
}
private static void print(int[] arr, int start, int end){
System.out.print(">> ");
for (int i = start; i <= end; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
시간복잡도
최선의 경우(피봇이 항상 중간값을 선택하는 경우) : O(n logn)
최악의 경우(이미 정렬된 배열에서 첫 번째 원소를 피봇으로 선택하는 경우) : O(n^2)
평균적인 경우 : O(n logn)
Java에서의 정렬
Java에서 정렬과 관련된 메서드는 무엇이 있을까?
배열 정렬 → Arrays.sort()
Dual-Pivot Quicksort 알고리즘을 통해 정렬한다.
One-Pivot Quicksort보다 빠르기 때문에 최악의 경우에도 O(n logn)의 시간복잡도를 가진다.
시간 복잡도 : O(n logn)
최악의 경우 : O(n logn)
리스트 정렬 → Collections.sort()
Tim sort 알고리즘을 통해 정렬한다.
시간 복잡도 : O(n logn)
최악의 경우 : O(n logn)
정렬 기준 → Comparator 인터페이스
객체의 정렬 기준을 제공하기 위한 함수형 인터페이스이다.
추상메서드인 int compare(T o1, T o2)를 오버라이딩 해서 Arrays.sort()와 Collections.sort()에 파라미터로 넘겨주면
정렬 기준을 사용자화 할 수 있다.
Arrays.sort(arr, (o1, o2) -> Integer.compare(o1, o2));'자료구조&알고리즘' 카테고리의 다른 글
| [자료구조] Hash, Hash Map (0) | 2024.01.08 |
|---|---|
| [JAVA] Stack이란? (0) | 2023.04.07 |
| [백준 1874번] 스택 수열 (메모리 초과 +StringBuilder) - java/자바 (0) | 2022.07.28 |