[알고리즘] 안정 정렬 (Stable Sort)

버블정렬, 삽입정렬, 퀵정렬, 선택정렬 등 정렬 알고리즘은 정렬의 안정성에 따라서 안정 정렬과 불안정 정렬로 나뉜다.

 

그 중 안정 정렬을 먼저 정리하려고 한다.

 

안정 정렬

안정 정렬이란 정렬 전 동일한 키 값의 요소 순서가 정렬 후 유지가 되는 정렬 알고리즘을 안정 정렬이라고 한다.

 

예시로

 

[3, 2, 1, 5, 7, 5] 배열이 있다고 가정한다.

 

이를 오름차순으로 정렬한다고 할때

 

[1, 2, 3, 5, 5, 7]이 된다면 안정 정렬

[1, 2, 3, 5, 5, 7]이 될 수 있다면 불안정 정렬이다.

 

안정 정렬에 해당하는 정렬

• 버블 정렬 (Bubble Sort)
• 삽입 정렬 (Insertion Sort)
• 병합 정렬 (Merge Sort)

 

정렬 과정을 볼 수 있는 참고 사이트 : https://visualgo.net/ko/sorting

VisuAlgo - Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix)

 

버블 정렬 (Bubble Sort)

버블 정렬은 매 회마다 0 인덱스 부터 시작하며 그 다음 인덱스 값과 비교하면서 거품처럼 순차적으로 정렬하는 알고리즘이다.

1회전이 끝나면 맨 마지막 요소가 확정되고, 2회전이 끝나면 맨 마지막 -1 의요소, 3회전은 마지막 -2 요소.. 의 순서로

오른쪽부터 정렬되는 방식이다.

 

구현이 간단하다는 장점이 있지만, 시간복잡도가 높아서 잘 쓰이지 않는다고 한다.

 

버블정렬 시간 복잡도

BEST : O(n²)

WORST : O(n²)

AVG : O(n²)

 

버블정렬 구현

 

import java.util.Arrays;

public class bubble {
	public static void main(String[] args) {
		int[] array = {3, 1, 2, 7, 12, 5};
		
		array = bubble_sort(array);
		
		System.out.println(Arrays.toString(array));
	}

	public static int[] bubble_sort(int[] array) {
		int size = array.length;
		int temp;
		
		for(int i=0; i<size-1; i++) {
			for(int j=1; j<size-i; j++) {
				if(array[j-1] > array[j]) {
					//swap
					temp = array[j];
					array[j] = array[j-1];
					array[j-1] = temp;
				}
			}
		}
		
		return array;
	}
	
}

 

 

삽입 정렬 (Insertion Sort)

 

삽입 정렬은 1 인덱스부터 시작해서 순차적으로 해당 인덱스의 숫자 왼쪽 값들과 비교해 올바른 위치에 삽입하는 정렬 알고리즘이다.

 

삽입 정렬 시간복잡도

BEST : O(n)

WORST : O(n²)

AVG : O(n²)

삽입 정렬 구현

import java.util.Arrays;

public class insertion {
	public static void main(String[] args) {
		int[] array = {3, 1, 2, 7, 12, 5, 8};
		
		array = insert_sort(array);
		
		System.out.println(Arrays.toString(array));
	}

	public static int[] insert_sort(int[] array) {
		for(int i=1; i<array.length; i++) {
			for(int j=0; j<i; j++) {
				if(array[i] < array[j]) {
					insert_idx(array, i, j);
				}
			}
		}
			
		return array;
	}
	
	public static void insert_idx(int[] array, int target_idx, int insert_idx) {
		int insert_value = array[target_idx];
		
		for(int i=target_idx; i>insert_idx; i--) {
			array[i] = array[i-1];
		}
		
		array[insert_idx] = insert_value;
	}
	
}

 

 

병합 정렬 (Merge Sort)

병합 정렬 (합병 정렬)은 요소들을 가장 작은 크기로 분할(Divide)한 뒤 토너먼트처럼 둘 씩 결합(Combine)하면서 정렬하는 분할 정복 기법(Divide and conquer)을 사용하는 알고리즘이다.

 

병합 정렬 시간 복잡도

BEST : O(nlogn)

WORST : O(nlogn)

AVG : O(nlogn)

병합 정렬 구현

import java.util.Arrays;

public class merge {
	public static void main(String[] args) {
		int[] array = {3, 1, 2, 7, 12, 5, 8};
		
		merge_sort(array, 0, array.length-1);
		
		System.out.println(Arrays.toString(array));
	}

	public static void merge_sort(int[] array, int start, int end) {
		if(start < end) {	//배열의 요소가 2개 이상이면
			//반으로 나눌 인덱스
			int middle = (start + end) / 2;	
			
			//앞부분 병합 정렬
			merge_sort(array, start, middle);
			
			//뒷부분 병합 정렬
			merge_sort(array, middle+1, end);
			
			//Merge하면서 정렬하는 로직
			merge_logic(array, start, middle, end);
		}
	}
	
	public static void merge_logic(int[] array, int start, int middle, int end) {
		int[] tempArr = new int[(end-start) + 1];
		int l = start;
		int r = middle+1;
		int idx = 0;
		
		if(end - start < 2) {	//요소 2개 짜리면 단순비교
			if(array[start] > array[end]) {
				tempArr[0] = array[end];
				tempArr[1] = array[start];
			} else {
				tempArr[0] = array[start];
				tempArr[1] = array[end];
			}
		} else {
			while(l <= middle && r <= end) {
				if(array[l] < array[r]) {
					tempArr[idx] = array[l];
					l++;
				} else {
					tempArr[idx] = array[r];
					r++;
				}
				idx++;
			}
			
            //넣고 남은 요소들은 그대로 넣어줌. 왼쪽 오른쪽 둘중 하나는 무조건 비워지기 때문에
			while (l <= middle) {
				tempArr[idx++] = array[l++];
	        }

	        while (r <= end) {
	        	tempArr[idx++] = array[r++];
	        }
		}
		
		idx = 0;
		for(int i=start; i<=end; i++) {
			array[i] = tempArr[idx++];
		}
	}
}