1.
삽입 정렬 이란?
•
삽입 정렬은 두 번째 인덱스부터 시작
•
해당 인덱스 앞에 있는 데이터부터 비교해서 key 값이 더 작으면, B 값을 뒤 인덱스로 복사
•
이를 key값이 더 큰 데이터를 만날때까지 반복, 그리고 큰 데이터를 만난 위치 바로 뒤에 key값을 이동
2.
어떻게 코드로 만들까?(결국 프로그래밍으로 일반화할 수 있도록 만드는 것)
알고리즘 연습 방법에 기반해서 단계별로 생각해봅시다.
연습해보기 1
•
데이터가 두 개일 떄 동작하는 삽입 정렬 알고리즘을 함수로 만들어보기.
연습해보기 2
•
데이터가 세 개일 떄 동작하는 삽입 정렬 알고리즘을 함수로 만들어보기.
연습해보기 3
•
데이터가 네 개일 때 동작하는 삽입 정렬 알고리즘을 함수로 만들어보기.
•
데이터가 네 개 일때(데이터 갯수에 따라 복잡도가 떨어지는 것은 아니므로, 네 개로 바로 로직을 이해해보자.)
◦
예 : dataList = [9,3,2,5]
▪
처음 한번 실행하면 key 값은 9, 인덱스(0) -1 은 0보다 작으므로 끝 : [9,3,2,5]
▪
두 번째 실행하면, key 값은 3, 9 보다 3이 작으므로 자리 바꾸고, 끝 : [3,9,2,5]
▪
세 번째 실행하면, key 값은 2,9 보다 2가 작으므로 자리 바꾸고, 다시 3보다 2가 작으므로 끝 : [2,3,9,5]
▪
네 번쨰 실행하면, key 값은 5,9 보다 5가 작으므로 자리 바꾸고, 3보다는 5가 크므로 끝 : [2,3,5,9]
3.
알고리즘 구현
import java.util.ArrayList;
import java.util.Collections;
public class Insertionsort {
public ArrayList<Integer> sort(ArrayList<Integer> dataList){
for(int index = 0; index < dataList.size()-1;index++)
{
for(int index2 = index+1;index2>0;index2--)
{
if(dataList.get(index2)<dataList.get(index2-1))
{
Collections.swap(dataList,index2,index2-1);
}else {
break;
}
}
}
return dataList;
}
}
Java
복사
4.
알고리즘 분석
•
반복문이 두 개 O()
◦
최악의 경우, n(n-1)/2
•
완전 정렬이 되어 있는 상태라면 최선은 O(n)