[자료구조, Java] Insertion Sort(삽입 정렬)

Insertion Sort(삽입 정렬)

출처 : 위키백과

• 시간복잡도 : O(n^2)
• 앞에서 부터 차례대로 이미 정렬된 배열 부분과 비교하여, 알맞는 대소관계의 위치에 위치하여 정렬
• 장점 : 쉬운 구현
• 단점 : 배열이 길어질수록 

java 구현

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

public class Insertion_Sort { //난수 생성 메소드 public int[] make_rnd(int size){ //중복값 제거를 위하여 Set으로 값 관리 Set rnd = new HashSet(); int rnd_list[] = new int[size]; for(int i = 0;size>i;i++){ //1~99사이의 난수값 생성 int tmp = (int) (Math.random() * 99)+1; rnd.add(tmp); //중복값 생성시 다시 생성 if (rnd.size() == i + 1) i--; else rnd_list[i]=tmp; } System.out.println("원본 배열 생성"); array_print(rnd_list, size); return rnd_list; } //배열 출력 메소드 public void array_print(int rnd_list[],int size){ System.out.print("[ "); for(int i=0;size>i;i++){ System.out.print(rnd_list[i]+ " "); } System.out.println("]"); } public static void main(String args[]){ int size = 10; Insertion_Sort sort= new Insertion_Sort(); int rnd_list[] = sort.make_rnd(size); //버블정렬 i = 차수 for (int i = 1; size > i; i++) { //j비교 위치 for (int j = 0; i > j; j++) { //2개 값 비교하여 정렬 if(rnd_list[j]>rnd_list[i]){ int tmp[] = new int[size]; System.arraycopy(rnd_list, 0, tmp, 0, j); tmp[j]=rnd_list[i]; System.arraycopy(rnd_list, j, tmp, j+1, i-j); System.arraycopy(rnd_list, i+1, tmp, i+1, size-(i+1)); rnd_list = tmp; break; } } System.out.println(i+"차 정렬"); sort.array_print(rnd_list, size); } } }

원본 배열 생성 [ 64 95 54 82 18 69 43 7 68 29 ]
1차 정렬 [ 64 95 54 82 18 69 43 7 68 29 ]
2차 정렬 [ 54 64 95 82 18 69 43 7 68 29 ]
3차 정렬 [ 54 64 82 95 18 69 43 7 68 29 ]
4차 정렬 [ 18 54 64 82 95 69 43 7 68 29 ]
5차 정렬 [ 18 54 64 69 82 95 43 7 68 29 ]
6차 정렬 [ 18 43 54 64 69 82 95 7 68 29 ]
7차 정렬 [ 7 18 43 54 64 69 82 95 68 29 ]
8차 정렬 [ 7 18 43 54 64 68 69 82 95 29 ]
9차 정렬 [ 7 18 29 43 54 64 68 69 82 95 ]