유랑하는 개발자

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

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

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

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

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

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

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

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;
	}
}

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

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

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

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

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

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

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;
	}

}

선택 정렬(Selection Sort)는 제자리 정렬의 알고리즘이며 3가지 순서가 있습니다.

1. 주어진 배열 값들 중에서 최소값을 찾습니다.

2. 그 최소값을 실행 순서의 값과 교체를 합니다.

3. 그렇게 첫 번째, 두 번째...마지막 -1회 까지 1, 2번 과정을 진행 합니다.

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

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

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

package algorithm;

public class SelectionSort {

	public static void main(String[] args) {
		int[] a = { 3, 6, 0, 9, 1 };
		int[] sorted_a = selectionSort(a);
		System.out.print(Arrays.toString(a)
	}

	public static int[] selectionSort(int[] a) {
		int i, j;
		int temp;
		for (i = 0; i <= a.length - 1; i++) {
			for (j = 0; j <= a.length - 1; j++) {
				if (a[i] < a[j]) {
					temp = a[i];
					a[i] = a[j];
					a[j] = temp;
				}
			}
		}
		return a;
	}

}