[정보처리기사 알고리즘] 버블정렬

이번년도의 목표 정보처리기사 취득하기

실기가 20일 남짓 남았다. 

알고리즘을 이해하기 위해 블로그에 정리해본다.

 

동작 설명

어언 10년전 고등학교때 배운 알고리즘중에 유일하게 기억에 남는 알고리즘.

선생님이 '마치 거품이 올라가는것같은 모양을해서 버블정렬'이다 라고 해서 아재개그 하시는줄 알고 속으로 웃었는데

알고보니 정말 이름의 유래였다.

선생님 보고계시다면 죄송합니다. 그때 공부 열심히 안해서 지금까지도 버블정렬을 공부하고 있네요.

 

어쨌든 버블정렬에 대한 기본 아이디어를 이해해보자.

첫번째 단계, 전체 데이터 N개 가운데 가장 큰 데이터가 가장 오른쪽(N번째 위치)에 오도록 한다. 이를 위해서 먼저, 가장 왼쪽의 데이터(1번째 데이터)와 이 데이터의 바로 오른쪽의 데이터(2번째 데이터)를 비교하여, 큰 데이터가 오른쪽(2번째 위치)에 위치하도록 한다....

이런 비교 및 교환 작업을 더이상 할 수 없을 때까지 반복한다....

 

이고잉님이 그러셨죠. 100마디 설명보다 한장의 그림이 더 이해가 빠를수 있다고.

그림으로 봅시다.

 

패턴을 살펴보자면..

외부 반복문은 버블정렬의 단계를 타타낸다. (i는 4까지)

단계가 늘어날수록 내부 반복문은 1씩 증가하여 줄어든다. (5 - i)

선택정렬과의 다른점은.. 기준이되는 숫자가 없고 내부에서 하나씩 증가한다는 점이다..

 

 

 

 

 

 

 

 

 

 

 

 

 

순서도는 1부터 시작이지만.. 배열은 인덱스가 0번부터 시작이므로,

내부 반복문에서 elementLength - i가 아닌 (i + 1)을 빼줬다.

그래서.. 총 반복은 0, 1, 2, 3회 실행하게 되고..

j는

0회 5 - (0 + 1) = 4번인덱스에 도달할때 끝남

1회 5 - (1 + 1) = 3번 인덱스에 도달할때 끝남

2회 5 - (2 + 1) = 2번 인덱스에 도달할때 끝남

 

처럼 순서도 대로 구현할 수 있었다..