삽입정렬 (Insertion Sort)

시간복잡도

최선 O(n) : 이미 정렬되어 있는 경우 한번만 탐색함

최악 O(n^2) : 역으로 정렬되어 있는 경우

개념

첫번째 숫자를 넣고 정렬되었다고 간주한 후, 그 다음 숫자부터 정렬된 배열과 비교하며 삽입과정을 반복해 완성한다.

로직

1. 1번째 값은 무조건 정렬된 배열에 넣고 다음 인덱스부터 비교를 시작한다

2. 2번째 값부터는 정렬된 배열에서의 자신의 위치를 탐색한다.

3. 탐색된 위치에 현재 값을 넣는다(삽입)

4. 1 ~ 3을 반복한다.

JAVA 소스

System.setIn(new FileInputStream("C:\\sample_input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine().trim());
		
		List sortedList = new ArrayList();
		
		
		for(int i=0; i<N; i++){
			int offset = Integer.parseInt(br.readLine().trim());
			
			if(i == 0){	// 처음에는 무조건 sortedList에 add한다
				sortedList.add(i, offset);
			}else{
				
				boolean isInsert = false;
				
				// sortedList를 돌면서 현재 offset 보다 큰 수가 있다면 그 앞에 offset을 추가한다
				for(int j=0; j<sortedList.size(); j++){
					int offsetJ = sortedList.get(j);
					if(offset <offsetJ){
						sortedList.add(j, offset);
						isInsert = true;
						break;
					}
				}
				
				// 한번도 추가되지 않았다면, 현재 가장 큰 수이므로 맨 뒤에 추가한다
				if(!isInsert){
					sortedList.add(offset);
				}
			}
			
		}
		
		for(int i=0; i<N; i++){
			System.out.println(sortedList.get(i));
		}

N : 배열의 크기

다음 라인부터 1라인에 하나의 값이 Input으로 주어짐