[정보처리기사] 주요 정렬 알고리즘의 이해 (삽입/버블/선택정렬)

내가 못찾는 것일 수도 있지만 시나공 기준으로 개정된 2020 정보처리기사에서 '주요 정렬 알고리즘'에 대한 부분은 제외된 것 같다(?) 그래도 기출도가 높았던 부분이었기에 해당 포스팅에 정리해본다.

 

 

삽입정렬

초기상태인 아래의 8,5,6,2,4를 삽입정렬을 사용해 정렬시키면 아래와 같은 과정을 거치게 된다.

 

 

1) 1회전 : 두번째 값을 첫번째 값과 비교해 첫번째 자리에 삽입, 8을 뒤로 한칸 이동

 

 

2) 2회전 : 세번째 값을 5,6과 비교해 삽입, 8을 뒤로 한칸 이동

 

 

3) 3회전 : 네번째 값을 5,6,8과 비교해 삽입, 5,6,8을 뒤로 한칸 이동

 

 

4) 4회전 : 다섯번째 값을 2,5,6,8과 비교해 삽입, 5,6,8을 뒤로 한칸 이동

 

 

 

버블정렬

초기상태인 아래의 8,5,6,2,4를 버블정렬을 사용해 정렬시키면 아래와 같은 과정을 거치게 된다.

 

1) 1회전 : 첫번째 값 8을 두번째 값인 5와 비교해 교환, 두번째 값 8을 세번째 값인 6과 비교해 교환, 세번째 값 8을 네번째 값인 2와 비교해 교환, 다섯번째 값인 4를 네번째 값인 8과 비교해 교환 (가장 큰 값이 가장 끝으로 가게 되므로 다음 회전부터는 맨 끝 값은 비교할 필요 없음)

 

 

2) 2회전 : 첫번째 값 5를 두번째 값인 6과 비교해 교환X, 두번째 값인 6을 세번째 값 2와 비교해 교환, 세번째 값인 6을 네번째 값인 4와 비교해 교환

 

 

3) 3회전 : 첫번째 값 5를 두번째 값인 2와 비교해 교환, 두번째 값인 5를 세번째 값 4와 비교해 교환

 

 

4) 4회전 : 첫번째 값 2를 두번째 값인 4와 비교해 교환X

 

 

 

선택정렬

초기상태인 아래의 8,5,6,2,4를 버블정렬을 사용해 정렬시키면 아래와 같은 과정을 거치게 된다.

 

 

1) 1회전 : 첫번째 값 8을 두번째 값 5과 비교해 교환, 첫번째 값 5를 세번째 값 6과 비교해 교환X, 첫번째 값 5를 네번째 값 2와 비교해 교환, 첫번째 값 2를 다섯번째 값 4와 비교해 교환X

 

 

2) 2회전 : 두번째 값 8을 세번째 값 6과 비교해 교환, 두번째 값 6을 네번째 값 5와 비교해 교환, 두번째 값 5를 다섯번째 값 4와 비교해 교환

 

 

3) 3회전 : 세번째 값 8을 네번째 값 6과 비교해 교환, 세번째 값 6을 다섯번째 값 5와 비교해 교환

 

 

4) 4회전 : 네번째 값 8을 다섯번째 값 6과 비교해 교환