[알고리즘] 선택정렬, 삽입정렬, 쉘 정렬

(추상클래스 AbstractSort)

public abstract class AbstractSort {
	public static void sort(Comparable[] a) {};
	
	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;
	}
}

 

 

-선택정렬

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);
		}
	}
	public static void main(String[] args) {
		Integer [] a = {10,9,8,7,5,4,3,2,1};
		Selection.sort(a);
		Selection.show(a);
	}
}

 

 

-삽입정렬

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);
			}
		}
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Integer [] a = {10,9,8,7,5,4,3,2,1};
		Selection.sort(a);
		Selection.show(a);
	}

}

 

 

-쉘 정렬

삽입정렬의 문제점을 해소함.

(삽입정렬은 현재 값을 바로 앞의 원소와 비교하기 때문에, 가장 작은 값이 마지막에 저장된 경우에 맨 앞까지 이동하는데 n-1번의 교환연산이 발생하여 정렬시간이 길어짐)

 

h-수열을 사용하는데,

일반적으로 사용하는 효율적인 h수열 생성방법은 (3배 곱하고 1 더하기)임.

==> 1 4 13 40 121 . . .

 

이제 이 수열을 가지고..

121칸 떨어진 원소들끼리 삽입정렬 => 40칸 떨어진 원소들끼리 삽입정렬 => 13칸 떨어진 원소들끼리 삽입정렬

=> 4칸 떨어진 원소들끼리 삽입정렬 =>1칸 떨어진 원소들끼리 삽입정렬 

순으로 정렬을 진행함.

 

그럼 뒤에있는 원소가 제일 작은 값일때도 금방 앞으로 보낼 수 있게 된다.

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;
		}
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Integer [] a = {10,9,8,7,5,4,3,2,1};
		Selection.sort(a);
		Selection.show(a);
		
	}

}

---

-선형 정렬

public class Counting {

	public static int[] sort(int[] A, int K) {
		int i,N=A.length;
		int[] C = new int[K],B=new int[K];
		
		for(i=0;i<N;i++) C[A[i]]++; //각 숫자의 개수 세기
		for(i=1;i<K;i++) C[i]+=C[i-1]; //누적합 계산
		for(i=N-1;i>=0;i--) //원 배열을 뒤에서부터 순회하며 해당값을 C배열에서 찾고, 그 값-1 위치에 해당값 저장
			B[--C[A[i]]] = A[i];
		
		return B;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] a = {10,9,8,7,5,4,3,2,1};
		int[] B= Counting.sort(a, 11);

		for(int i=0;i<B.length;i++) {
			System.out.print(B[i]+" ");
		}
		System.out.println();
	}

}

각 숫자의 개수를 세어 배열에 저장.

=> 이 배열을 누적합으로 다시 저장(해당 숫자의 저장위치 인덱스가 됨)

 

새로운 배열 B에 정렬한 값을 저장할건데,

원본배열의 뒤에서부터 순회 시작.

누적합배열[원본배열값] 값에서 1감소시킨것이 원본값 저장할 인덱스.

 

왜 원본배열의 뒤에서부터 순회를 하는가?

같은 숫자가 여러개 있는 상황에서, 해당 숫자를 저장할 인덱스 범위가 정해져 있을텐데,

그 범위에서 맨 뒤부터 값을 채워나가기 때문에 

원본배열을 뒤에서부터 순회를 시작해야 stable한 정렬을 할 수 있음.

 

 

..

.

오늘따라 글이 참 두서없지만 

기록하기위해 적었으니 글은 보지 말아주세요.