반응형

삽입 정렬(Insertion Sort)은 배열의 구간을 정한다음 원소를 비교하며 정렬을 하는 방식입니다.

1. 0 번째 인덱스의 원소와 1 번째 인덱스의 원소를 비교 합니다. (ex. 범위는 0-1 인덱스)

2. 1 번째 원소가 0 번째 원소보다 작으면 첫 번째 원소의 인덱스는 1 증가하고 두 번째 원소의 인덱스는 1 감소합니다.

3. 이런식으로 범위가 1씩 증가하며 원소를 비교한 뒤 큰 숫자의  인덱스를 1씩 늘려주고 작은 숫자의 인덱스를 숫자 만큼 감소 해주세요. 

 

아래는 위의 순서에 맞게 실행한 예제입니다.

- 배열에 저장되는 값은 [3, 6, 0, 9, 1] 입니다.

Sequence Array Arrange
1 [3, 6, 0, 9, 1] 변화 없음
2 [3, 6, 0, 9, 1] 0(a[2] -> a[0])
3(a[0] -> a[1])
6(a[1] -> a[2])
3 [0, 3, 6, 9, 1] 1(a[4] -> a[1])
3(a[1] -> a[2])
6(a[2] -> a[3])
8(a[3] -> a[4])

 

 

 

아래는 삽입 정렬을 구현한 자바 예제입니다.

?
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
<code>package algorithm;
 
import java.util.Arrays;
 
public class InsertionSort {
 
    public static void main(String[] args) {
        int[] a = { 3, 6, 0, 9, 1 };
        int[] sorted_a = insertionSort(a);
        System.out.println(Arrays.toString(sorted_a));
    }
 
    public static int[] insertionSort(int[] a) {
        int i, j;
        for (i = 0; i < a.length; i++) {
            int temp = a[i];
            int range = i-1;
            while (range >= 0 && a[range] > temp) {
                a[range+1] = a[range];
                range--;
            }
            a[range+1] = temp;
        }
        return a;
    }
}
 
</code>

 

반응형
저작자표시
반응형

버블 정렬은(Bubble Sort) 두 인접한 원소를 순차적으로 정렬하는 방법이고 2가지 순서가 있습니다.

1. 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를 ... N-1번째 원소와 N번째 원소를 비교 합니다.

2. 1회전이 끝나면 가장 큰 원소가 맨 마지막으로 이동하기 때문에 다음 회전에서의 마지막은 N-2 원소와 N-1 원소가 됩니다.

 

아래는 위의 순서에 맞게 실행한 예제입니다.

- 배열에 저장되는 값은 [3, 6, 0, 9, 1] 입니다.

Sequence Table Values Result
1 [3, 6, 0, 9, 1]  6<->0 [3, 0, 6, 9, 1]
1 [3, 0, 6, 9, 1] 9<->1 [3, 0, 6, 1, 9]
2 [3, 0, 6, 1, 9] 3<->0 [0, 3, 6, 1, 9]
3 [0, 3, 6, 1, 9] 6<->1 [0, 3, 1, 6, 9]
4 [0, 3, 1, 6, 9] 3<->1 [0, 1, 3, 6, 9]

 

 

 

아래는 선택 정렬을 구현한 자바 예제입니다.

 

?
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
<code>
package algorithm;
 
import java.util.Arrays;
 
public class BubbleSort {
 
    public static void main(String[] args) {
        int[] a = { 3, 6, 0, 9, 1 };
        int[] sorted_a = bubbleSort(a);
 
        System.out.print(Arrays.toString(a));
    }
 
    public static int[] bubbleSort(int[] a) {
        int i, j, temp;
        for (i = a.length - 1; i > 0; i--) {
            for (j = 0; j < i; j++) {
                if (a[j] > a[j + 1]) {
                    temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                }
            }
        }
        return a;
    }
 
}
 
</code>
반응형
저작자표시

'Programming > Algorithm' 카테고리의 다른 글

[자바/알고리즘]알고리즘 선택정렬  (0) 2020.08.24
[자바/알고리즘]정보처리기사 Section012 - 소인수 분해하기  (0) 2016.02.11
[자바/알고리즘]정보처리기사 Section011 - 약수 구하기  (0) 2016.02.11
[자바/알고리즘]정보처리기사 Section008 - 소수의 합 구하기  (0) 2016.02.11
[자바/알고리즘]정보처리기사 Section007 - 소수 판별  (0) 2016.02.11

+ Recent posts

티스토리툴바