삽입 정렬(순차/일반), 선택 정렬

1. 일반 삽입 정렬(Insertion Sort)

 : 이미 정렬되어 있는 배열에 추가 요소를 적절한 위치에 삽입(끼워넣기)함으로써 정렬을 수행하는 알고리즘이다.

 : 평균/최악 시간복잡도 O(n^2)으로 느린 정렬 방식이다.

 : 정렬 수행 시 추가 저장 공간이 필요하지 않는 In-Place 알고리즘이다.

 : 구현이 용이하다.

// 일반 삽입 정렬 static void insertionSort(int[] data) { int pos, tempValue; System.out.println("\n\n<일반 삽입 정렬>"); for (int i = 1; i < data.length; i++) { System.out.print(i + "회전 : "); System.out.print(Arrays.toString(data)); System.out.print(" -> "); tempValue = data[i]; pos = i; while (--pos >= 0 && tempValue < data[pos]) { data[pos + 1] = data[pos]; } data[pos + 1] = tempValue; System.out.println(Arrays.toString(data)); } }

2. 순차 삽입 정렬(Sequential Insertion Sort)

: 선택 정렬과 비교 방식은 동일하나, 자료의 교환 방식이 맞교환이 아니라 끼워넣기이다.

: 끼워넣어야 하므로 중간의 자료들을 모두 밀어내는 과정이 필요하다.

// 순차 삽입 정렬 : 비교방식은 선택정렬과 같으나, 자료 교환 방식이 맞교환이 아닌 끼워넣기. // 끼워넣기 위해 사이의 자료를 전부 다 밀어내야 한다. static void sequentialInsertionSort(int[] data) { int minIdx; int tempValue; System.out.println("<순차 삽입 정렬>"); for (int i = 0; i < data.length - 1; i++) { System.out.print((i + 1) + "회전 : "); System.out.print(Arrays.toString(data)); if (i != data.length - 2) System.out.print(" -> "); minIdx = i; for (int j = i + 1; j < data.length; j++) { if (data[j] < data[minIdx]) { minIdx = j; } } if (minIdx != i) { tempValue = data[minIdx]; while (i < minIdx) { data[minIdx] = data[--minIdx]; } data[i] = tempValue; System.out.println(Arrays.toString(data)); } } }

3. 선택 정렬 (Selection Sort)

 :  수열에서 가장 작은 데이터를 찾아 맨 앞 데이터와 교환하고, 맨 앞 데이터를 제외한 나머지 부분 수열에 대해서도 같은 과정을 반복.

 : 데이터가 n개일 때, 데이터 교환은 많아야 n-1번이고, 전체 비교횟수는 n(n-1)/2이므로 시간복잡도는 O(n^2)

// 선택 정렬 static void selectionSort(int[] data) { int minIdx; int tempValue; System.out.println("\n\n<선택 정렬>"); for (int i = 0; i < data.length - 1; i++) { System.out.print((i + 1) + "회전 : "); System.out.print(Arrays.toString(data)); System.out.print(" -> "); minIdx = i; for (int j = i + 1; j < data.length; j++) { if (data[j] < data[minIdx]) { minIdx = j; } } if (minIdx != i) { tempValue = data[i]; data[i] = data[minIdx]; data[minIdx] = tempValue; } System.out.println(Arrays.toString(data)); } }