삽입정렬

문제 . N개 숫자가 입력되면 오름차순으로 선택정렬하시오.

 

입력 예시

6
13 5 11 7 23 15

 

답 : 

5 7 11 13 15 23

 

 

나의 답변

public class Main {	
	public int[] solution(int n, int[] arr) {
		for( int i=1; i<n; i++ ) {
			int temp_value = arr[i]; 
			int j; 
			for( j=i-1; j>=0; j-- ) {
				if(temp_value<arr[j]) {
					arr[j+1]=arr[j];
				} else break; 
			}
			arr[j+1]=temp_value; 
		}
		return arr;
	}
	public static void main(String[] args) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] arr = new int[n]; 
		for( int i=0; i<n; i++ ) {
			arr[i] = sc.nextInt();
		}
		for( int x : T.solution(n, arr)) {
			System.out.print(x + " ");
		}
	}
}

 

 

---

 

 

삽입정렬

1. 임시로 인덱스 1의 값을 삭제하고 이 값을 임시변수에 저장한다.
2. 공백 왼쪽값을 가져와 임시 변수 값과 비교한다.
3. 공백 왼쪽값이 임시변수값보다 크면 그 값을 오른쪽으로 시프트한다.
4. 값을 오른쪽으로 시프트했으므로 공백이 왼쪽으로 옮겨진다.
5. 임시로 삭제한 값보다 작은 값을 만나거나 배열의 왼쪽 끝에 도달해야 시프트 단계가 끝난다.
6. 임시로 제거한 값을 현재 공백에 삽입한다.

삽입정렬은 비교, 시프트, 삭제, 삽입 단계가 있다. 

• 비교는 최대 1 + 2 + ... +  N - 1 번 일어나므로 N^2 / 2 번이다.
• 시프트는 한 셀 옮기는 것을 뜻하고 한 셀 옮기면 비교가 일어나기때문에 N^2 / 2 번이다.
• 비교와 시프트는 합치면  N^2 / 2 *2 = N^2 이다.
• 삭제와 삽입은 패스스루당 한 번 일어나고 패스스스루는 총 N -1번이므로 삭제와 삽입도 N - 1번이다.
• N^2 + N - 1 + N - 1 = N^2 + 2N - 2
• 빅 오 표기법은 가장 높은 차수 N만 고려하고 상수는 제거한다.
• 따라서 시간복잡도는 O(n^2) 이다.

 

선택정렬 / 버블정렬 / 삽입정렬 비교 

 

시간복잡도는 모두 O(n^2) 이다.

최선 / 최악의 시나리오는 자주 발생하지 않으므로 평균 시나리오에 대부분은 초점을 맞추는것이 좋으나 상황에 따라 최선 / 최악의 시나리오에 초점을 맞춰야 할 수도 있다.

 

• 선택 정렬
  • 최솟값을 찾아서 맨 앞부터 채워나가는 방식
  • 전체 모든 아이템을 스캔
  • 어떤 데이터에도 동일한 시간이 소요되어 정렬과 역순의 영향이 없음
  • 대부분 역순으로 정렬된 데이터를 다룰 시 삽입정렬보다 효율적임

• 버블 정렬
  • 인접한 원소끼리 비교하여 교환하는 방식
  • 가장 비효율적이지만 단순함
• 삽입 정렬
  • 앞에서부터 차례대로 이미 정렬된 부분과 비교하여 교환하는 방식
  • 필요한 아이템만 스캔
  • 정렬이 될수록 비교적 많은 비교 및 이동 필요하지 않음
  • 거의 정렬된 데이터를 다룰 시 선택정렬보다 효율적임

 

알고리즘	최선의 시나리오	평균 시나리오	최악의 시나리오	비고
선택 정렬	N^2 / 2	N^2 / 2	N^2 / 2	교환: N | 삽입, 삭제 없음
버블 정렬	N - 1	N^2 / 2	N^2	교환: N^2 / 2 | 삽입, 삭제 없음
삽입 정렬	N	N^2 / 2	N^2	삽입: N | 교환, 삭제 없음

 

 

 

 

참고 자료 출처 : https://www.inflearn.com/course/lecture?courseSlug=%EC%9E%90%EB%B0%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%ED%85%8C%EB%8C%80%EB%B9%84&unitId=72755

https://www.youtube.com/watch?v=Bor_CRWEIXo

%EC%84%A0%ED%83%9D%EC%A0%95%EB%A0%AC-vs-%EC%82%BD%EC%9E%85%EC%A0%95%EB%A0%AC-%EC%B0%A8%EC%9D%B4-%EC%A0%9C%EB%8C%80%EB%A1%9C-%EC%95%8C%EA%B3%A0%EA%B0%80%EC%9E%90

책 <누구나 자료구조와 알고리즘>