<Algorithm>Selection, Insertion, Shell Sort

본 게시물은 영남대학교 조행래 교수님의 강의를 기반으로 작성되었습니다.

0. Java  Abstract Class

• 각 정렬마다 별도의 클래스로 작성
• 추상 클래스 사용해서 각 정렬의 클래스마다 공통적인 메서드 사용

public class AbstractSort {
	public static void sort(Comparable[] a){};
	
	//w is smaller than v -> return true!
	protected static boolean less(Comparable v, Comparable w) {
		return v.compareTo(w) < 0;
	}
	
	protected static void exch(Comparable[] a, int i , int j ) {
		Comparable t = a[i];
		a[i] = a[j];
		a[j] = t;
	}
	
	protected static void show(Comparable[] a) {
		for(int i = 0; i < a.length; i++) {
			System.out.print(a[i] + "");
			System.out.println();
		}
	}
	
	protected static boolean isSorted(Comparable[] a) {
		for(int i = 1; i < a.length; i++) {
			if(less(a[i],a[i-1])) return false;
				}
		return true;
	}
}

1. Selection Sort(선택 정렬)

• 리스트에서 최소값을 찾는다
• 이 값을 현재 위치의 값과 교환한다.
• 현재 위치를 다음으로 이동하면서 반복한다.

Java Code

public class Selection extends AbstractSort{
	public static void sort(Comparable[] a) {
    
		int N = a.length;
        
		for(int i = 0; i < N -1; i++) {
			int min = i; // 현재위치
			for(int j = i + 1; j < N; j++) {
				if(less(a[j], a[min])) 
					min = j;
			}
			exch(a, i ,min);
		}
        
		//뒤에가 false 오류발생시키는 assert
		assert isSorted(a);
	}
    
	public static void main(String[] args) {
    
		Integer[] a = {10,4,5,2,1,8,3,6};
		Selection.sort(a);
		Selection.show(a);
	}
}

2. Insertion Sort(삽입 정렬)

• 현재위치를 i라고 지정(0 < i < n) (n = 리스트의 갯수)
• i번째 원소를 0부터 i-1까지 정렬된 리스트에 추가
• i를 n-1까지 증가하면서 반복.
• 풀어서 설명하면 하나의 index 기준으로 그 전 리스트들의 원소들을 일일히 비교하면서 정렬
• 만약 기준 index의 값이 가장 작은 값이면(0~i-1)리스트 모든값과 비교를 진행->최악

Java Code

public class Insertion extends AbstractSort{

	public static void sort(Comparable[] a) {
    
		int N = a.length;
        
		for(int i = 1; i < N; i++) {
			for(int j = i; j > 0 && less(a[j],a[j-1]); j--) {
				exch(a,j,j-1);
			}
		}
        
		assert isSorted(a);
	}
    
	public static void main(String[] args) {
    
		Integer[] a = {3,1,2};
		Insertion.sort(a);
		Insertion.show(a);
	}

}

3. Shell Sort

• 삽입 정렬의 문제점(=한칸만 움직인다는 점)을 보완하는 정렬
• h개 만큼 떨어진 원소들과 비교 후 자리 바꿈
  ->한번의 교환 연산으로 h만큼 이동 가능
• h - sorted array : h번째 항목들은 정렬된 배열
• h를 구하는 방법은 강의내용과 구글링의 내용이 살짝 다른데 h가 어떤값이든 원리는 동일하다.
• h는 간단하게 array.length() / 2 로 설정
• 만약 짝수가 안 나오면 반올림 해서 h설정(ex : 2.5->3)

Java Code

public class Shell extends AbstractSort{
	public static void sort(Comparable[] a) {
    
		int N = a.length;
		int h = 1;
        
		while(h < N/3) h = 3*h +1;
		
		while(h >= 1) {
			for(int i = h; i < N; i++) {
				for(int j = i; j >= h && less(a[j],a[j-h]); j -= h) {
					exch(a,j,j-h);
				}
			}
			h /= 3;
		}
		assert isSorted(a);
	}
    
	public static void main(String[] args) {
    
		Integer[] a = {10,4,5,2,1,8,3,6};
		Selection.sort(a);
		Selection.show(a);
	}

}