Algorithm - Sort Algorithm

삽입 정렬

• 두 번째 자료부터 시작하여 그 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고지정한 자리에 자료를 삽입하여 정렬하는 알고리즘이다.

• 즉, 두 번째 자료는 첫 번째 자료, 세 번째 자료는 두 번째와 첫 번째 자료, 네 번째 자료는 세 번째, 두 번째, 첫 번째 자료와 비교한 후 자료가 삽입될 위치를 찾는다.

• 자료가 삽입될 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 자료를 한 칸씩 뒤로 이동시킨다.

• 처음 Key 값은 두 번째 자료부터 시작한다.

 public static int[] solution(int n, int[] arr) {
	for ( int i=1; i<n; i++ ) {
		int key = arr[i];
		int j = i - 1;
		while ( j >= 0 && arr[j] > key) {
			arr[j + 1] = arr[j];
			j --;
		}
		arr[j + 1] = key;
	}
	return arr;
}

선택 정렬

• 첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고,

• 두 번째 자료를 세 번째 자료부터 마지막 자료까지와 차례대로 비교하여,

• 그 중 가장 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬을 수행한다.

 public static int[] solution(int n, int[] arr) {
	for ( int i=0; i<n-1; i++ ) {
		int min = Integer.MAX_VALUE;
		int minIdx = -1;
		for ( int j=i+1; j<n; j++ ) {
			if ( min > arr[j] ) {
				min = arr[j];
				minIdx = j;
			}
		}
		if ( arr[i] > min ) {
			int tmp = arr[i];
			arr[i] = arr[minIdx];
			arr[minIdx] = tmp;
		}
	}
	return arr;
}

버블 정렬

• 0 ~ 5, 0 ~ 4, 0 ~ 3, 0 ~ 2, 0 ~ 1 이렇게 순차적으로 가면서, 바로 뒤 자료와 비교하며 계속해서 정렬하는 방법이다.

• 버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, … 이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬한다.

• 1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외되고,

• 2회전을 수행하고 나면 끝에서 두 번째 자료까지는 정렬에서 제외된다.

• 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.

 public static int[] solution(int n, int[] arr) {
	while ( n > 0 ) {
		for ( int i=0; i<n-1; i++ ) {
			if ( arr[i] > arr[i+1] ) {
				int tmp = arr[i];
				arr[i] = arr[i+1];
				arr[i+1] = tmp;
			}
		}
		n--;
	}
	return arr;
}