단순 삽입 정렬(straight insertion sort)
선택한 요소를 그보다 더 앞쪽의 알맞은 위치에 삽입하는 작업을 반복하는 정렬 알고리즘
- 아직 정렬되지 않은 부분의 첫 번째 요소를 정렬한 부분의 알맞은 위치에 삽입
for (int i = 1; i < n; i++) {
// tmp <- a[i]
// a[0], ..., a[i-1]의 알맞은 곳에 tmp 삽입
int j = i;
int tmp = a[i];
// 정렬된 열의 왼쪽 끝에 도달하거나, tmp보다 작거나 같은 key를 갖는 항목 a[j-1]을 발견할때까지 반복
while(j > 0 && a[j-1] > tmp) {
a[j] = a[j-1];
j--;
}
a[j] = tmp;
}
단순 삽입 정렬
package ch06_4;
import java.util.Scanner;
// 단순 삽입 정렬
public class Ex01_insertionSort {
// 단순 삽입 정렬
static void insertionSort(int[] a, int n) {
for (int i = 1; i < n; i++) {
int j;
int temp = a[i];
for (j = i; j > 0 && a[j - 1] > temp; j--) {
a[j] = a[j - 1];
}
a[j] = temp;
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("단순 삽입 정렬");
System.out.print("요솟수: ");
int nx = scanner.nextInt();
int[] x = new int[nx];
for (int i = 0; i < nx; i++) {
System.out.print("x[" + i + "]: ");
x[i] = scanner.nextInt();
}
insertionSort(x, nx); // 배열 x를 단순 삽입 정렬
System.out.println("오름차순으로 정렬했습니다.");
for (int i = 0; i < nx; i++) {
System.out.println("x[" + i + "] = " + x[i]);
}
}
}
단순 정렬의 시간 복잡도
세 가지 단순 정렬(버블, 선택, 삽입)의 시간 복잡도는 모두 O(n^2)으로 효율이 좋지 않음
단순 선택 정렬(교환 과정을 자세히 출력)
package ch06_4;
import java.util.Scanner;
// 단순 선택 정렬(교환 과정을 자세히 출력)
public class Ex02_selectionSortEx {
// a[idx1]과 a[idx2]의 값을 교환
static void swap(int[] a, int idx1, int idx2) {
int t = a[idx1];
a[idx1] = a[idx2];
a[idx2] = t;
}
// 단순 선택 정렬
static void selectionSort(int[] a, int n) {
for (int i = 0; i < n - 1; i++) {
int min = i; // 아직 정렬되지 않은 부분에서 가장 작은 요소의 인덱스를 저장
for (int j = i + 1; j < n; j++) {
if (a[j] < a[min]) {
min = j;
}
}
for (int j = 0; j < n; j++) {
// 바꿀 요소는 +, 위치는 *
System.out.print((j == i) ? " * " : (j == min) ? " + " : " ");
}
System.out.println();
for (int j = 0; j < n; j++) {
System.out.printf("%3d ", a[j]);
}
System.out.println("\\n");
swap(a, i, min); // 아직 정렬되지 않은 부분의 첫 요소와 가장 작은 요소를 교환
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("단순 선택 정렬");
System.out.print("요솟수: ");
int nx = scanner.nextInt();
int[] x = new int[nx];
for (int i = 0; i < nx; i++) {
System.out.print("x[" + i + "]: ");
x[i] = scanner.nextInt();
}
selectionSort(x, nx); // 배열 x를 단순 선택 정렬
System.out.println("오름차 순으로 정렬했습니다.");
for (int i = 0; i < nx; i++) {
System.out.println("x[" + i + "] = " + x[i]);
}
}
}
/*
단순 선택 정렬
요솟수: 4
x[0]: 2
x[1]: 9
x[2]: 6
x[3]: 1
* +
2 9 6 1
* +
1 9 6 2
*
1 2 6 9
오름차 순으로 정렬했습니다.
x[0] = 1
x[1] = 2
x[2] = 6
x[3] = 9
*/
단순 삽입 정렬(삽입 과정을 자세히 출력)
package ch06_4;
import java.util.Scanner;
// 단순 삽입 정렬(삽입 과정을 자세히 출력)
public class Ex03_insertionSortEx {
// 단순 삽입 정렬
static void insertionSort(int[] a, int n) {
for (int i = 1; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.printf("%3d ", a[j]);
}
System.out.println();
int j;
int temp = a[i];
for (j = i; j > 0 && a[j - 1] > temp; j--) {
a[j] = a[j - 1];
}
a[j] = temp;
System.out.print(" ".repeat(4 * j));
System.out.print(i != j ? "^-" : " ");
System.out.print("-".repeat(4 * (i - j)));
System.out.println("+");
System.out.printf("a[%d]의 %d을/를 a[%d]의 위치에 삽입하였습니다.\\n\\n", i, temp, j);
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("단순 삽입 정렬");
System.out.print("요솟수: ");
int nx = scanner.nextInt();
int[] x = new int[nx];
for (int i = 0; i < nx; i++) {
System.out.print("x[" + i + "]: ");
x[i] = scanner.nextInt();
}
insertionSort(x, nx); // 배열 x를 단순 삽입 정렬
System.out.println("오름차순으로 정렬했습니다.");
for (int i = 0; i < nx; i++) {
System.out.println("x[" + i + "] = " + x[i]);
}
}
}
/*
단순 삽입 정렬
요솟수: 4
x[0]: 6
x[1]: 4
x[2]: 8
x[3]: 2
6 4 8 2
^-----+
a[1]의 4을/를 a[0]의 위치에 삽입하였습니다.
4 6 8 2
+
a[2]의 8을/를 a[2]의 위치에 삽입하였습니다.
4 6 8 2
^-------------+
a[3]의 2을/를 a[0]의 위치에 삽입하였습니다.
오름차순으로 정렬했습니다.
x[0] = 2
x[1] = 4
x[2] = 6
x[3] = 8
*/
단순 삽입 정렬(보초법: 배열의 맨 앞 요소는 비어있음)
package ch06_4;
import java.util.Scanner;
// 단순 삽입 정렬(보초법: 배열의 맨 앞 요소는 비어있음)
public class Ex04_insertionSortCen {
// 단순 삽입 정렬
static void insertionSort(int[] a, int n) {
for (int i = 2; i < n; i++) {
int temp = a[0] = a[i];
int j = i;
for (; a[j - 1] > temp; j--) {
a[j] = a[j - 1];
}
if (j > 0) {
a[j] = temp;
}
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("단순 삽입 정렬");
System.out.print("요솟수: ");
int nx = scanner.nextInt();
int[] x = new int[nx + 1]; // 여분으로 1개 더 생성
for (int i = 1; i <= nx; i++) { // x[1] ~ x[nx]에 입력받음
System.out.print("x[" + i + "]: ");
x[i] = scanner.nextInt();
}
insertionSort(x, nx + 1); // 배열 x를 단순 삽입 정렬
System.out.println("오름차순으로 정렬하였습니다.");
for (int i = 1; i <= nx; i++) {
System.out.println("x[" + i + "] = " + x[i]);
}
}
}
이진 삽입 정렬
package ch06_4;
import java.util.Scanner;
// 이진 삽입 정렬
public class Ex05_binInsertionSort {
// 이진 삽입 정렬
static void binInsertionSort(int[] a, int n) {
for (int i = 1; i < n; i++) {
int key = a[i];
int first = 0; // 검색범위 맨 앞의 인덱스
int last = i - 1; // 검색번위 맨 끝의 인덱스
int center; // 검색범위 중앙의 인덱스
int insertion; // 삽입하는 위치의 인덱스
do {
center = (first + last) / 2;
// 검색 성공
if (a[center] == key) {
break;
} else if (a[center] < key) {
first = center + 1;
} else {
last = center - 1;
}
} while (first <= last);
insertion = (first <= last) ? center + 1 : last + 1;
for (int j = i; j > insertion; j--) {
a[j] = a[j - 1];
}
a[insertion] = key;
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("이진 삽입 정렬");
System.out.print("요솟수: ");
int nx = scanner.nextInt();
int[] x = new int[nx];
for (int i = 0; i < nx; i++) {
System.out.print("x[" + i + "]: ");
x[i] = scanner.nextInt();
}
binInsertionSort(x, nx); // 배열 x를 이진삽입정렬
System.out.println("오름차순으로 정렬하였습니다.");
for (int i = 0; i < nx; i++)
System.out.println("x[" + i + "] ＝ " + x[i]);
}
}'공부기록 > 알고리즘' 카테고리의 다른 글
| Chapter 06-3. 정렬 알고리즘_단순 선택 정렬 (0) | 2024.08.16 |
|---|---|
| Chapter 06-2. 정렬 알고리즘_버블 정렬 (0) | 2024.08.16 |
| Chapter 06-1. 정렬 알고리즘_정렬 알고리즘이란 (0) | 2024.08.16 |
| Chapter 05-4. 재귀 알고리즘_8퀸 문제 (0) | 2024.08.11 |
| Chapter 05-3. 재귀 알고리즘_하노이의 탑 (0) | 2024.08.11 |
댓글