기본 정렬 알고리즘: Java 코드 구현
기본 정렬 알고리즘: Java 코드 구현
선택 정렬, 버블 정렬, 삽입 정렬은 가장 기초적인 정렬 알고리즘입니다. 이 문서에서는 각 알고리즘의 핵심 원리와 함께 실제 동작하는 Java 코드를 상세한 주석과 함께 제공합니다.
테스트를 위한 전체 Java 클래스 구조
아래는 각 정렬 메서드를 테스트하기 위한 전체적인 클래스 구조입니다. 각 알고리즘 설명에 나오는 메서드들을 이 클래스 안에 포함시켜 실행할 수 있습니다.
import java.util.Arrays;
public class BasicSorting {
// 각 정렬 알고리즘 메서드가 여기에 위치합니다.
/**
* 배열을 출력하는 헬퍼 메서드
* @param arr 출력할 정수 배열
*/
public void printArray(int[] arr) {
System.out.println(Arrays.toString(arr));
}
public static void main(String[] args) {
BasicSorting sorter = new BasicSorting();
// 테스트용 배열 선언
int[] arr1 = {5, 3, 8, 1, 4};
int[] arr2 = {5, 3, 8, 1, 4};
int[] arr3 = {5, 3, 8, 1, 4};
System.out.println("--- 선택 정렬 ---");
System.out.print("정렬 전: ");
sorter.printArray(arr1);
sorter.selectionSort(arr1);
System.out.print("정렬 후: ");
sorter.printArray(arr1);
System.out.println("\n--- 버블 정렬 ---");
System.out.print("정렬 전: ");
sorter.printArray(arr2);
sorter.bubbleSort(arr2);
System.out.print("정렬 후: ");
sorter.printArray(arr2);
System.out.println("\n--- 삽입 정렬 ---");
System.out.print("정렬 전: ");
sorter.printArray(arr3);
sorter.insertionSort(arr3);
System.out.print("정렬 후: ");
sorter.printArray(arr3);
}
}1. 선택 정렬 (Selection Sort)
배열의 처음부터 끝까지 순회하면서 최솟값을 찾아 해당 순회의 시작 위치와 교환하는 방식을 반복합니다.
Java 코드
/**
* 선택 정렬
* @param arr 정렬할 정수 배열
*/
public void selectionSort(int[] arr) {
int n = arr.length;
// 배열의 크기-1 만큼 순회합니다. (마지막 요소는 자동으로 정렬됨)
for (int i = 0; i < n - 1; i++) {
// 현재 순회에서 최솟값의 인덱스를 찾습니다.
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j; // 더 작은 값을 찾으면 인덱스를 업데이트
}
}
// 찾은 최솟값을 현재 순회의 시작 위치(i)와 교환(swap)합니다.
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}코드 동작 원리
1. 바깥쪽 for 루프(변수 i)는 정렬될 위치를 0번 인덱스부터 순차적으로 지정합니다.
2. 안쪽 for 루프(변수 j)는 i+1 위치부터 배열 끝까지 탐색하며 가장 작은 값의 인덱스(minIndex)를 찾습니다.
3. 안쪽 루프가 끝나면, minIndex에 저장된 위치의 값과 i 위치의 값을 서로 교환(swap)합니다.
4. 이 과정을 i가 배열의 끝까지 갈 때까지 반복하면 전체 배열이 정렬됩니다.
2. 버블 정렬 (Bubble Sort)
인접한 두 원소를 비교하여 정렬 순서가 맞지 않으면 교환하는 과정을 배열의 끝까지 반복합니다. 한 번의 순회가 끝나면 가장 큰 원소가 맨 뒤로 이동합니다.
Java 코드
/**
* 버블 정렬
* @param arr 정렬할 정수 배열
*/
public void bubbleSort(int[] arr) {
int n = arr.length;
boolean swapped;
// 각 순회마다 가장 큰 원소가 맨 뒤로 이동하므로, n-1번 반복합니다.
for (int i = 0; i < n - 1; i++) {
swapped = false;
// 이미 정렬된 뒷부분은 제외하고 앞부분만 비교합니다.
for (int j = 0; j < n - 1 - i; j++) {
// 왼쪽 값이 오른쪽 값보다 크면 교환합니다.
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true; // 교환이 발생했음을 표시
}
}
// 최적화: 만약 한 순회 동안 교환이 한 번도 없었다면,
// 배열은 이미 정렬된 상태이므로 루프를 종료합니다.
if (!swapped) {
break;
}
}
}코드 동작 원리
1. 바깥쪽 for 루프(변수 i)는 총 순회 횟수를 제어합니다. 한 번 순회할 때마다 가장 큰 값이 제자리를 찾아가므로, 순회 범위는 하나씩 줄어듭니다.
2. 안쪽 for 루프(변수 j)는 배열의 처음부터 n-1-i 위치까지 인접한 두 원소(arr[j], arr[j+1])를 비교합니다.
3. 만약 앞의 값이 더 크면 두 값의 위치를 교환(swap)합니다.
4. 한 순회(안쪽 루프)에서 교환이 전혀 일어나지 않았다면(swapped가 false), 이미 배열이 정렬된 것이므로 바깥쪽 루프를 일찍 종료하여 효율성을 높입니다.
3. 삽입 정렬 (Insertion Sort)
두 번째 원소부터 시작하여, 각 원소를 이미 정렬된 앞부분 배열의 올바른 위치에 삽입하는 방식을 사용합니다.
Java 코드
/**
* 삽입 정렬
* @param arr 정렬할 정수 배열
*/
public void insertionSort(int[] arr) {
int n = arr.length;
// 두 번째 원소(인덱스 1)부터 시작합니다.
for (int i = 1; i < n; ++i) {
int key = arr[i]; // 현재 삽입될 값
int j = i - 1;
// key 값을 정렬된 앞부분 배열의 올바른 위치에 삽입합니다.
// key보다 큰 원소들을 한 칸씩 뒤로 이동시킵니다.
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
// 찾은 위치에 key 값을 삽입합니다.
arr[j + 1] = key;
}
}코드 동작 원리
1. for 루프(변수 i)는 1부터 시작하여 배열의 각 원소를 차례대로 선택합니다. 선택된 원소(key)를 정렬된 왼쪽 부분에 삽입하는 것이 목표입니다.
2. while 루프는 key 값과 왼쪽의 정렬된 부분의 원소들을 비교합니다.
3. 만약 key보다 큰 원소가 있다면, 그 원소를 오른쪽으로 한 칸 이동시킵니다. 이 과정을 key보다 작거나 같은 원소를 만나거나 배열의 맨 앞에 도달할 때까지 반복합니다.
4. while 루프가 끝나면 key가 들어갈 올바른 위치가 정해지며, 그 위치에 key 값을 삽입합니다.