제자리 정렬 (in-place sort) - 데이터에 필요한 공간을 제외하고 추가적인 공간이 필요없음을 의미
선택 정렬, 버블 정렬보다 비교적 빠르지만 마찬가지로 배열이 클수록 효율이 떨어짐
선택 정렬과 비슷하지만 선택 정렬은 배열의 모든 값을 탐색해 최소값을 구한 후 정렬하는 방식이지만 삽입 정렬은 데이터의 앞쪽을 탐색하며 자신의 위치를 찾아 정렬함
삽입 정렬 방법
배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입함으로써 정렬을 완성시킴
자신의 위치를 찾는 방법은 arr[i - 1] <= X < arr[i] 가 만족하는 위치가 있다면 해당 위치에 X값을 삽입함
삽입될 위치의 뒤 인덱스들을 하나씩 뒤로 미뤄 X가 들어갈 공간을 만들어줌
성능
시간복잡도 최악의 경우 : O(n^2) - 배열의 데이터가 모두 역순일 때 (5, 4, 3, 2, 1) - 5, 4, 3, 2, 1의 예시에서보면 4와 5를 비교, 3과 4, 5비교, 2와 3, 4, 5 순으로 비교하게 되는데 비교횟수를 수식으로 나타내면 1 + 2 + 3 + 4 + ... + (n-1) 이 되므로 1/2n(n-1) 이 되어 n^2이 된다.
최선의 경우 : O(n) - 배열의 데이터가 모두 정렬되어 있을 때 (1, 2, 3, 4, 5) - 삽입 정렬은 앞쪽부터 정렬되기 때문에 정렬하려는 값 X가 바로 앞 데이터보다 클 경우 모든 앞쪽 데이터들을 확인할 필요가 없으므로 다음 데이터로 넘어가서 다시 비교하게 된다. 따라서, 이미 정렬이 된 상태인 경우 n번만 반복한 후 종료된다.
구현
기본 구현 [InsertionBasic.java]
package Sort.Insertion;
public class InsertionBasic {
public static void sort(int[] arr, boolean isDescending) {
// 현재값을 저장하기 위한 변수
int tmp = 0;
// 비교 대상의 인덱스 변수
int compareIndex = 0;
for(int i=1; i<arr.length; i++) {
// 현재값 저장
tmp = arr[i];
// 현재값 바로 앞 인덱스값 저장
compareIndex = i - 1;
// 앞쪽 데이터들이 현재값보다 작을때까지 반복
// 앞쪽 데이터들을 뒤로 당기는 과정
while(compareIndex >= 0 && !isSortTwoElements(arr[compareIndex], tmp, isDescending)) {
arr[compareIndex + 1] = arr[compareIndex];
compareIndex--;
}
// 빈 공간에 데이터 저장
arr[compareIndex + 1] = tmp;
}
}
/**
*
* @param cmp1 비교할 값
* @param cmp2 비교할 값
* @param isDescending 내림차순 및 오름차순 선택
* @return 내림차순의 경우 cmp1이 작을 경우 false, 그렇지 않으면 true
* 오름차순의 경우 cmp1이 작을 경우 true, 그렇지 않으면 false
*/
private static boolean isSortTwoElements(int cmp1, int cmp2, boolean isDescending) {
// 내림차순일 경우
if (isDescending) {
if (cmp1 < cmp2) {
return false;
}
else {
return true;
}
}
// 오름차순일 경우
else {
if (cmp1 < cmp2) {
return true;
}
else {
return false;
}
}
}
}
테스트
package Sort.Insertion;
public class InsertionBasicMain {
private static final int MAX_COUNT = 30;
public static void main(String[] args) {
int[] arr = new int[MAX_COUNT];
for (int i = 0; i < MAX_COUNT; i++) {
// 0 ~ MAX_COUNT 범위내의 난수를 생성
arr[i] = (int) (Math.random() * MAX_COUNT);
}
System.out.println("정렬 전 데이터");
for(int i : arr) {
System.out.print(i + " ");
}
System.out.println();
int[] ascInsertionTestArray = arr.clone();
System.out.println("정렬 후 데이터 (오름차순)");
InsertionBasic.sort(ascInsertionTestArray, false);
for(int i : ascInsertionTestArray) {
System.out.print(i + " ");
}
System.out.println();
int[] descInsertionTestArray = arr.clone();
System.out.println("정렬 후 데이터 (내림차순)");
InsertionBasic.sort(descInsertionTestArray, true);
for(int i : descInsertionTestArray) {
System.out.print(i + " ");
}
System.out.println();
}
}
결과
클래스 정렬을 위한 구현 [InsertionAdvanced.java]
package Sort.Insertion;
import java.util.Comparator;
public class InsertionAdvanced {
public static <T> void sort(T[] arr) {
T tmp = null;
int compareIndex = 0;
for(int i=1; i<arr.length; i++) {
tmp = arr[i];
compareIndex = i - 1;
while(compareIndex >= 0 && ((Comparable<? super T>)arr[compareIndex]).compareTo(tmp) > 0) {
arr[compareIndex + 1] = arr[compareIndex];
compareIndex--;
}
arr[compareIndex + 1] = tmp;
}
}
public static <T> void sort(T[] arr, Comparator<? super T> comp) {
T tmp = null;
int compareIndex = 0;
for(int i=1; i<arr.length; i++) {
tmp = arr[i];
compareIndex = i - 1;
while (compareIndex >= 0 && comp.compare(arr[compareIndex], tmp) > 0) {
arr[compareIndex + 1] = arr[compareIndex];
compareIndex--;
}
arr[compareIndex + 1] = tmp;
}
}
}
테스트
package Sort.Insertion;
import Sort.Selection.SelectionAdvanced;
import java.util.Comparator;
public class InsertionAdvancedMain {
private static final int MAX_COUNT = 30;
public static void main(String[] args) {
Integer[] arr = new Integer[MAX_COUNT];
for (int i = 0; i < MAX_COUNT; i++) {
// 0 ~ MAX_COUNT 범위내의 난수를 생성
arr[i] = (int) (Math.random() * MAX_COUNT);
}
System.out.println("정렬 전 데이터");
for(int i : arr) {
System.out.print(i + " ");
}
System.out.println();
Integer[] ascInsertionTestArray = arr.clone();
System.out.println("정렬 후 데이터 (오름차순)");
InsertionAdvanced.sort(ascInsertionTestArray);
for(int i : ascInsertionTestArray) {
System.out.print(i + " ");
}
System.out.println();
System.out.println();
class Student {
String name;
int age;
public Student(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public String toString() {
return "name='" + name + '\'' +
", age=" + age;
}
}
Student[] students = new Student[5];
students[0] = new Student("아이언맨", 11);
students[1] = new Student("헐크", 4);
students[2] = new Student("토르", 15);
students[3] = new Student("블랙위도우", 13);
students[4] = new Student("캡틴", 4);
System.out.println("클래스 정렬 전 데이터");
for (int i=0; i<students.length; i ++) {
System.out.println(students[i]);
}
System.out.println();
System.out.println("클래스 정렬 후 데이터 (나이 내림차순)");
InsertionAdvanced.sort(students, new Comparator<Student>() {
@Override
public int compare(Student o1, Student o2) {
if (o1.age < o2.age) {
return 1;
}
else if (o1.age == o2.age) {
return 0;
}
else {
return -1;
}
}
});
for (int i=0; i<students.length; i ++) {
System.out.println(students[i]);
}
}
}
