🏷️ 버블 정렬
import java.util.Arrays;
import java.util.Scanner;
public class BubbleSort {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] nums = new int[n];
// 배열에 수 받기
for (int i = 0; i < n; i++) {
nums[i] = scanner.nextInt();
}
nums = bubbleSort(nums);
// 출력
System.out.println(Arrays.toString(nums));
}
private static int[] bubbleSort(int[] nums) {
int n = nums.length;
// 버블 정렬
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (nums[j] > nums[j + 1]) {
int temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
}
}
}
return nums;
}
}
🏷️ 선택 정렬
import java.util.Arrays;
import java.util.Scanner;
public class SelectSort {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] nums = new int[n];
// 문자열 숫자를 배열에 저장
for (int i = 0; i < n; i++) {
nums[i] = sc.nextInt();
}
nums = selectionSort(nums);
// 출력
System.out.println(Arrays.toString(nums));
}
private static int[] selectionSort(int[] nums) {
int n = nums.length;
// 선택 정렬 구현
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++) {
if (nums[j] < nums[minIdx]) {
minIdx = j;
}
}
// 작은 숫자를 순서대로 찾아서 앞에서 부터 채우기
int temp = nums[i];
nums[i] = nums[minIdx];
nums[minIdx] = temp;
}
return nums;
}
}
🏷️ 삽입 정렬
import java.util.Arrays;
import java.util.Scanner;
public class InsertionSort {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] nums = new int[n];
// 배열에 숫자 받기
for (int i = 0; i < n; i++) {
nums[i] = sc.nextInt();
}
nums = insertionSort(nums);
System.out.println(Arrays.toString(nums));
}
private static int[] insertionSort(int[] nums) {
int n = nums.length;
// 두 번째 수부터 앞에서 비교하며 뒤로 선택한 숫자가 아닌 수를 미룸
for (int i = 1; i < n; i++) {
int target = nums[i];
int j = i - 1;
// 타겟보다 크기 전까지 반복
while (j >= 0 && nums[j] > target) {
nums[j + 1] = nums[j]; // 원소를 뒤로 미룸
j--;
}
nums[j + 1] = target;
}
return nums;
}
}
🏷️ 퀵 정렬
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
public class QuickSort {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] nums = new int[n];
// 배열 받기
for (int i = 0; i < n; i++) {
nums[i] = sc.nextInt();
}
Integer[] numsObj = Arrays.stream(nums).boxed().toArray(Integer[]::new);
// 퀵 정렬
nums = quickSort(nums, 0, n - 1);
System.out.println(Arrays.toString(nums));
}
private static int[] quickSort(int[] nums, int start, int end) {
if (start >= end) return nums;
// 피벗 위치 바꾸고 피벗 idx 반환
int pivotIdx = partition(nums, start, end);
quickSort(nums, start, pivotIdx - 1); // 왼쪽 부분 정렬
quickSort(nums, pivotIdx + 1, end); // 오른쪽 부분 정렬
return nums;
}
private static int partition(int[] nums, int start, int end) {
int pivot = nums[start]; // 맨 왼쪽을 피벗으로 설정
int left = start + 1, right = end;
// 선택한 피벗을 중심으로 좌우로 나누어 정렬
while (left <= right) {
// pivot보다 큰값 찾기
while (left <= end && nums[left] < pivot) left++;
// pivot보다 적은값 찾기
while (right > start && nums[right] > pivot) right--;
if (left < right) {
// 왼쪽 오른쪽 찾은 값에 따른 교체
swap(nums, left, right);
}
}
swap(nums, start, right); // pivot 제자리에 놓기
return right;
}
// 배열 안의 두 수를 바꾸는 함수
private static void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
✅ 리스트로 보기 편한 버전
private static List<Integer> quickSort(List<Integer> nums) {
int numsLen = nums.size();
if (numsLen <= 1) return nums;
// 가운대 원소를 pivot으로 설정
int pivot = nums.get(numsLen / 2);
List<Integer> left = new ArrayList<>();
List<Integer> right = new ArrayList<>();
// 나머지를 pivot 기준으로 분리
for (int i = 0; i < numsLen; i++) {
int val = nums.get(i);
if (i == nums.size() / 2) continue; // pivot 제외
if (val <= pivot) left.add(val);
else right.add(val);
}
// 재귀 후 합치기
List<Integer> sortedLeft = quickSort(left);
List<Integer> sortedRight = quickSort(right);
List<Integer> result = new ArrayList<>();
result.addAll(sortedLeft);
result.add(pivot);
result.addAll(sortedRight);
return result;
}
🏷️ 병합 정렬
import java.util.Arrays;
import java.util.Scanner;
public class MargeSort {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] nums = new int[n];
// 배열 입력받기
for (int i = 0; i < n; i++) {
nums[i] = sc.nextInt();
}
// 출력
System.out.println(Arrays.toString(mergeSort(nums, 0, n - 1)));
}
// 병합 정렬 로직
private static int[] mergeSort(int[] nums, int start, int end) {
// start가 end보다 크거나 같을 경우 -1 반환
if (start >= end) return nums;
// 중앙 구하기
int mid = (start + end) / 2;
// 왼쪽 정렬
mergeSort(nums, start, mid);
// 오른쪽 정렬
mergeSort(nums, mid + 1, end);
// 병합
merge(nums, start, mid, end);
return nums;
}
// 병합 로직
private static void merge(int[] nums, int start, int mid, int end) {
// 병합전 정렬할 수를 담을 배열 생성
int[] temp = new int[end - start + 1];
// 인쪽, 오른쪽 포인터 및 temp를 가르킬 idx 선언
int left = start, right = mid + 1, idx = 0;
// 정렬 시작
while (left <= mid && right <= end) {
if (nums[left] <= nums[right]) {
temp[idx++] = nums[left++];
} else {
temp[idx++] = nums[right++];
}
}
// 왼쪽 혹은 오른쪽이 조건으로인해 위의 로직이 끝나면 나머지 수를 temp에 옮기는 로직
while (left <= mid) temp[idx++] = nums[left++];
while (right <= end) temp[idx++] = nums[right++];
// 정렬한 숫자를 저장
for (int i = 0; i < temp.length; i++) nums[start + i] = temp[i];
}
}