삽입 정렬은 알고리즘에 속한다!
알고리즘이란?
컴퓨터가 따라 할 수 있도록 문제를 해결하는 절차나 방법을 자세히 설명하는 과정 따라서
함수를 절차적으로 만들면 ‘알고리즘’이다.
삽입 정렬
- 정렬되지 않은 데이터를 정렬된 부분과 비교하여 적절한 위치에 삽입하는 알고리즘이다.
- 정렬되지 않은 데이터 중 첫 번째 데이터를 정렬된 부분의 적절한 위치에 삽입하고, 두 번째 데이터를 정렬된 부분에 삽입하는 과정을 반복하여 전체 데이터를 정렬한다.
- 데이터의 개수가 작을 때 효과적이며, 시간 복잡도는 최악의 경우 O(n^2)이다.
삽입 정렬의 흐름 보기
5, 8, 2, 4, 3 수를 삽입 정렬 하면?
삽입 정렬의 회전 수는 N - 1회 돈다! 이때 N은 배열의 크기이다.
ㅤ | 1회전 | 2회전 | 3회전 | 4회전 |
1 | 5, 8 (변화 없음) | 8, 2 (5, 2, 8, 4, 3) | 8, 4 (2, 5, 4, 8, 3) | 8, 3 (2, 4, 5, 3, 8) |
2 | ㅤ | 5, 2 (2, 5, 8, 4, 3) | 5, 4 (2, 4, 5, 8, 3) | 5, 3 (2, 4, 3, 5, 8) |
3 | ㅤ | ㅤ | 2, 4 (변화 없음) | 4, 3 (2, 3, 4, 5, 8) |
4 | ㅤ | ㅤ | ㅤ | 2, 3 (변화 없음) |
결과 | 5, 8, 2, 4, 3 | 2, 5, 8, 4, 3 | 2, 4, 5, 8, 3 | 2, 3, 4, 5, 8 |
각 회차마다 배열의 위치를 조정해야 하는 횟수는 해당 회차의 인덱스에 의해 결정됩니다. 즉, 각 회차마다 ‘회전 수’만큼 배열의 요소를 확인하고 위치를 조정하게 됩니다.
삽입 정렬 알고리즘 이해
진행도 1
package ex03.test;
public class InsertionSort01 {
public static void main(String[] args) {
// 1. 배열이 5개짜리가 있다하면. 첫번째 인덱스 값과 두번째 인덱스 값을 비교하여 더 작은수를 앞의 인덱스로 이동시킨다.
int[] arr = {5, 2};
for (int i : arr) {
System.out.print(i + " ");
}
System.out.println();
int temp;
if (arr[0] > arr[1]) {
temp = arr[1];
arr[1] = arr[0];
arr[0] = temp;
}
for (int i : arr) {
System.out.print(i + " ");
}
}
}진행도 2
package ex03.test;
public class InsertionSort02 {
public static void main(String[] args) {
// 2. 배열이 5개짜리가 있다하면. 1차 과정뒤 2차 과정을 만들어보자!!
int[] arr = {5, 8, 2, 4, 3};
for (int v : arr) {
System.out.print(v + " ");
}
System.out.println();
int temp;
int i = 0;
// 1회전
if (arr[i] > arr[i + 1]) {
temp = arr[i + 1];
arr[i + 1] = arr[i];
arr[i] = temp;
}
for (int v : arr) {
System.out.print(v + " ");
}
System.out.println();
// 2회전
if (arr[i + 1] > arr[i + 2]) {
temp = arr[i + 2];
arr[i + 2] = arr[i + 1];
arr[i + 1] = temp;
}
if (arr[i] > arr[i + 1]) {
temp = arr[i + 1];
arr[i + 1] = arr[i];
arr[i] = temp;
}
for (int v : arr) {
System.out.print(v + " ");
}
System.out.println();
// 3회전
if (arr[i + 2] > arr[i + 3]) {
temp = arr[i + 3];
arr[i + 3] = arr[i + 2];
arr[i + 2] = temp;
}
if (arr[i + 1] > arr[i + 2]) {
temp = arr[i + 2];
arr[i + 2] = arr[i + 1];
arr[i + 1] = temp;
}
if (arr[i] > arr[i + 1]) {
temp = arr[i + 1];
arr[i + 1] = arr[i];
arr[i] = temp;
}
for (int v : arr) {
System.out.print(v + " ");
}
System.out.println();
}
}진행도 3
package ex03.test;
public class InsertionSort03 {
public static void main(String[] args) {
// 3. 배열이 5개짜리가 있다하면. 공통된 부분을 더 찾아보자!
int[] arr = {5, 8, 2, 4, 3};
for (int v : arr) {
System.out.print(v + " ");
}
System.out.println();
int temp;
int n1 = 0;
int n2 = 0;
int i = 0;
// 1회전
n1 = 1;
n2 = n1 - 1;
if (arr[i + n2] > arr[i + n1]) {
temp = arr[i + n1];
arr[i + n1] = arr[i + n2];
arr[i + n2] = temp;
}
for (int v : arr) {
System.out.print(v + " ");
}
System.out.println();
// 2회전
n1 = 2;
n2 = n1 - 1;
if (arr[i + n2] > arr[i + n1]) {
temp = arr[i + n1];
arr[i + n1] = arr[i + n2];
arr[i + n2] = temp;
}
n1 = n1 - 1;
n2 = n1 - 1;
if (arr[i + n2] > arr[i + n1]) {
temp = arr[i + n1];
arr[i + n1] = arr[i + n2];
arr[i + n2] = temp;
}
for (int v : arr) {
System.out.print(v + " ");
}
System.out.println();
// 3회전
n1 = 3;
n2 = n1 - 1;
if (arr[i + n2] > arr[i + n1]) {
temp = arr[i + n1];
arr[i + n1] = arr[i + n2];
arr[i + n2] = temp;
}
n1 = n1 - 1;
n2 = n1 - 1;
if (arr[i + n2] > arr[i + n1]) {
temp = arr[i + n1];
arr[i + n1] = arr[i + n2];
arr[i + n2] = temp;
}
n1 = n1 - 1;
n2 = n1 - 1;
if (arr[i + n2] > arr[i + n1]) {
temp = arr[i + n1];
arr[i + n1] = arr[i + n2];
arr[i + n2] = temp;
}
for (int v : arr) {
System.out.print(v + " ");
}
System.out.println();
// 4회전
n1 = 4;
n2 = n1 - 1;
if (arr[i + n2] > arr[i + n1]) {
temp = arr[i + n1];
arr[i + n1] = arr[i + n2];
arr[i + n2] = temp;
}
n1 = n1 - 1;
n2 = n1 - 1;
if (arr[i + n2] > arr[i + n1]) {
temp = arr[i + n1];
arr[i + n1] = arr[i + n2];
arr[i + n2] = temp;
}
n1 = n1 - 1;
n2 = n1 - 1;
if (arr[i + n2] > arr[i + n1]) {
temp = arr[i + n1];
arr[i + n1] = arr[i + n2];
arr[i + n2] = temp;
}
n1 = n1 - 1;
n2 = n1 - 1;
if (arr[i + n2] > arr[i + n1]) {
temp = arr[i + n1];
arr[i + n1] = arr[i + n2];
arr[i + n2] = temp;
}
for (int v : arr) {
System.out.print(v + " ");
}
System.out.println();
}
}삽입 정렬 완성
package ex03.test;
public class InsertionSort04 {
public static void main(String[] args) {
int[] arr = {5, 8, 2, 4, 3};
int N = arr.length;
for (int v : arr) {
System.out.print(v + " ");
}
System.out.println();
int temp;
for (int i = 1; i < N; i++) {
temp = arr[i]; // temp 에 회전 곳의 뒤의 데이터를 삽입한다.
for (int j = i - 1; j >= 0 && arr[j] > temp; j--) { // j는 앞의 수로 점점 나아가는 수로 j에 i - 1을 대입하여 j를 비교 대상의 앞에 데이터를 불러 올수 있도록 만들고
arr[j + 1] = arr[j]; // 조건 식은 j가 0보다 큰경우에만 인덱스 값이 호출되고 temp 가 arr[j]보다 커야 교환이 일어나야하므로 설정
arr[j] = temp; // 그 후 점점 아래로 비교하니깐 j를 1씩 빠지도록 만들었다.
}
}
for (int v : arr) {
System.out.print(v + " ");
}
System.out.println();
}
}출력 결과
Share article
