[자바] 정렬 알고리즘 - 삽입 정렬

삽입 정렬(Insertion Sort)

- 선택, 버블 정렬은 무조건 위치를 바꾸지만 이것은 필요할때만 위치를 바꾼다

- 즉 삽입정렬은 이미 정렬되어있다고 가정하는데 정렬할때의 좌측은 이미 정렬이 되어있어 내가 선택한 값과 비교를 통해 알맞은 위치에 삽입을 한다는 것이다. (비교하는 꼴은 내가 선택한 값과 정렬이 되어있는 것의 오른쪽 부터 비교해 값이 더 크다면 삽입할위치를 계속찾는것이다. 이때 내가 선택한 값에 정렬이 되어있던 것의 작은 값을 차례대로 넣는 과정을 거친다.)

 

삽입정렬 사진

 

 

public class Insertion_Sort {
	
	public static void sort(int []a){
		for(int i=1;i<a.length;i++) {
			int target=a[i];
			int j=i-1;
			//자바의 &&연산자는 먼저 fasle가 되는 것을 좌측에 놔야 에러가 안생김.
			while(j>=0&&target<a[j]) {
				a[j+1]=a[j];
				j--;
			}
			a[j+1]=target;
		}
	}
	
	public static void swap(int []a, int i, int j) 
	{
		int temp=a[i];
		a[i]=a[j];
		a[j]=temp;
	}

}

 

장점

거의 정렬 된 경우 매우 효율적(N2의 빅오를 가지는 알고리즘 중 효울적)이다. 즉, 최선의 경우 O(N)의 시간복잡도를 갖는다.

 

 

단점

- 역순에 가까울 수록 매우 비효율적이다. 즉, 최악의 경우 O(N2)의 시간 복잡도를 갖는다.

- 데이터의 상태에 따라서 성능 편차가 매우 크다.