삽입 정렬은 알고리즘에 속한다!
알고리즘이란?
컴퓨터가 따라 할 수 있도록 문제를 해결하는 절차나 방법을 자세히 설명하는 과정 따라서
함수를 절차적으로 만들면 ‘알고리즘’이다.
삽입 정렬
- 정렬되지 않은 데이터를 정렬된 부분과 비교하여 적절한 위치에 삽입하는 알고리즘이다.
- 정렬되지 않은 데이터 중 첫 번째 데이터를 정렬된 부분의 적절한 위치에 삽입하고, 두 번째 데이터를 정렬된 부분에 삽입하는 과정을 반복하여 전체 데이터를 정렬한다.
- 데이터의 개수가 작을 때 효과적이며, 시간 복잡도는 최악의 경우 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
