Bubble Sort

해당 알고리즘은 최근에는 거의 사용되지 않는 알고리즘 입니다. 하지만, 정렬 알고리즘을 배우는데 있어 제일 먼저 배우는 가장 기초적인 알고리즘이기 때문에, 공부하고 넘어가겠습니다.

거품 정렬은 정렬하는 과정에서 거품이 올라오는 것과 같은 모습이 시각적으로 보인다고 해서 지어진 이름입니다. 각각의 데이터를 비교하면서 찾기 때문에 비교 정렬이며 인덱스를 교환하는 방식으로 진행이 되기 때문에 추가적인 공간을 필요로 하지 않는 In-place-sort입니다. 이전에 다뤘던 선택 정렬과는 다르게 bubble sort는 stable sort이기도 합니다.

그러면 Sorting 하는 과정을 말씀드리겠습니다.
1. 앞에서부터 현재 원소와 바로 다음의 원소를 비교한다.
2. 현재 원소가 다음 원소보다 크면 원소를 교환한다.
3. 다음 원소로 이동하여 해당 원소와 그 다음 원소를 비교한다.
4. 만약 정렬이 되지 않고 인덱스가 넘어가 마지막 인덱스까지 닿았을 경우에는 이미 정렬이 된 배열이므로 코드의 동작을 중지한다.

public class Bubble_Sort{
	public static void bubble_sort(int[] a){
    	bubble_sort(a, a.length);
    }
    
    private static void bubble_sort(int[] a, int size){
    	
        // 배열의 크기 만큼 반복문을 돌려 비교를 진행한다.
        for(int i = 1; i < size; i++){
        	// 정렬된 배열인지 아닌지를 알아보기 위해서 사용한다.
        	boolean swapped = false;
            
            // 각 인덱스 별 앞뒤를 비교한다.
            for(int j = 0; j < size; j++){
            	if(a[j] > a[j+1]){
                swqp(a, j, j+1);
                swapped = true;
                }
                
            }
            // 만약 swapped 가 true가 아니라면 정렬이 되어 있다고 봐도 무방하다.
        	if(swapped == false) break;
        }
    }
    
    private static void swap(int[] a, int i, int j){
    	int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

이렇게 최선이나 최악이나 일단 두개의 반복문을 통해서 탐색을 들어가기 때문에 O(n^2)을 가지고 있으나, 위의 알고리즘은 최선의 경우(정렬이 되어 있는 경우)에도 같이 O(n^2)를 띄는 것을 방지하기 위해서 break;를 추가했습니다.

---

Shell Sort

Insertion Sort의 장점을 살리고 단점을 줄이기 위해서 만들어진 알고리즘으로써, 오름차순 기준으로 타켓 원소가 이전의 원소보다 작아서 모두 교환하는 최악의 경우을 줄이기 위해서 일정 간격을 두고 원소를 비교하여 위치를 대략적으로 잡아주는 방식을 선택했습니다.

Shell Sort는 Insertion Sort를 기반으로 하기 때문에 Comparison Sort이고 데이터 외의 추가적인 공간을 필요로 하지 않는 In-place sort입니다. 다만, Insertion Sort와는 다르게 일정 간격을 주기로 하여 비교 및 교환이 일어나기 때문에 구조상 Stable Sort는 아입니다.

*Shell Sort의 정렬 과정은 아래와 같습니다.
1. Gap을 설정한다.
2. 각 간격별로 분류 된 서브 리스트에 대해 삽입정렬을 한다.
3. 각 서스 리스트의 정렬이 끝나면 간격을 줄인다.
4. 간격이 1이 될 때까지 2번 과정으로 되돌아가며 반복한다.

🌟 How to set up a gap for Shell Sorting?

정답은 없습니다만, 가장 많이 다루는 것은 Knuth Sequence, Tokuda Sequence, Cicura Sequence가 있습니다. 이 중에 코드의 예시로 들 것은 Cicura Sequence입니다. (해당 시퀸스가 제일 좋은 퍼포먼스를 나타냈다고 알려져 있습니다.) 해당 시퀸스는 경험적으로 나타난 것이 때문에 아직은 긴 배열에 대해서는 나타나지 않았지만 구하는 식은 다음과 같습니다.

$h'_k = 2.25h'_{k-1} + 1$
$h'_{k-1} = 2^k + 1 , 3^k - 1$

위의 결과를 도출하기 위해서 구성하는 코드는 아래와 같습니다.

public class Shell_Sort {
	
	private final static int[] gap = 
		{ 1, 4, 10, 23, 57, 132, 301, 701, 1750, 3937, 	
		8858, 19930, 44842, 100894, 227011, 510774,
		1149241, 2585792, 5818032, 13090572, 29453787, 
		66271020, 149109795, 335497038, 754868335, 1698453753};	// 갭을 담고있는 배열	
 
	
	public static void shell_sort(int[] a) {
		shell_sort(a, a.length);
		
	}
 
	// 맨 처음 gap을 참조 할 인덱스를 구하는 메소드
	private static int getGap(int length) {
		int index = 0;
		// 최소한 부분 배열의 원소가 2개씩은 비교 되도록 나눠준다.
		int len = (int)(length / 2.25);	
		while (gap[index] < len) {
			index++;
		}
		return index;
	}
	
 	private static void shell_sort(int[] a, int size) {
		int gapIndex = getGap(size);
		
		// 갭이 1이 될 때까지 반복
		while(gapIndex >= 0) {
			int step = gap[gapIndex--];	// 현재 gap(step)
			
			
			/*
			 * --- 삽입 정렬 과정 ---
			 * 
			 * 각 부분리스트의 두 번째 원소의 인덱스 부터 순회한다.
			 * 예로들어 step이 3일 때 arr[0], arr[1], arr[2] 는 
			 * 이전 원소와 비교할 것이 없다.
			 * 그러므로 step부터 순회한다.   
			 */
			for(int i = step; i < size; i++) {
				
				/*
				 *  j는 target 원소가 되며 현재 원소(target) a[j]가 이전 원소 a[j - step]보다
				 *  작을 때 까지 반복한다.
				 */
				for (int j = i; j >= step && a[j] < a[j - step]; j -= step) {
					/*
					 *  현재(target) 원소의 인덱스(j)와 이전의 원소(j-step)의 인덱스에 있는
					 *  원소의 값을 교환한다.
					 */
					swap(a, j, j - step);
				}
			}
		}
	}
 
	private static void swap(int[] a, int i, int j) {
		int swap = a[i];
		a[i] = a[j];
		a[j] = swap;
	}
}

위의 알고리즘(Shell Sort)를 이용하면 Insertion Sort, Bubble Sort보다 속도가 빠르고 멀리 있는 원소들끼리 빠르게 비교 및 교환이 이뤄진다는 장점이 있고 일반적인 Insertion Sort에 비해 구현이 까다롭고 Gap Sequence에 영향을 많이 받으며 정렬하는 과정에서 일정한 간격을 두고 진행을 하기 때문에 Stable Sort가 아니라는 단점이 있습니다.

그래서 시간복잡도는 아래와 같습니다.

• 최선의 경우 : $T(x) = O(xlogx)$
• 최악의 경우 : $T(x) = O(x^2)$

그런데 만약 작은 단위의 정렬을 시행할 경우에는 gap이 1로 고정이 되기 때문에 일반적인 Insertion Sort와 차이점이 없게됩니다.