정보처리기능사 실기 기출유형#11 - 정렬 알고리즘 버블정렬

DAT AWKWARD PONY SMILE THO :)

정보처리기능사 실기 기출유형#11 - 정렬 알고리즘 버블정렬

1. 정렬?

- 숫자들이 있는 배열을 입력받고 작은 순서부터 정렬하는 오름차순 정렬을 시키거나 큰 순서부터 정렬하는 내림차순 정렬을 시킨다.

2. 정렬하는 방법

- 다양한 정렬 방법 즉, 정렬 알고리즘 이 존재할 수 있음 지금까지 파악된 유형만 3개.

1) 선택정렬

2) 버블정렬

3) 최대값 최소값 이용.

3. 선택정렬 알고리즘

- 선택정렬 알고리즘은 원소들을 비교해서 교환하는 방식의 알고리즘이다.

1번째 2번째

1번째 3번째

1번째 4번째

2번째 3번째

2번째 4번째

3번째 4번째

* 중요한점은 루프마다 비교횟수 -1씩 줄어든다는 것, 시작 인덱스는 루프마다 +1이후 고정

* 교환시 임시변수 K에 자료보존하고 교환시키면 됨.

4. 버블정렬 알고리즘

- 버블 정렬 알고리즘은 사실상 선택정렬 알고리즘과도 비슷한데, 비교-교환하는 방식이

오직 이웃끼리 한다는게 다른점이다.

1번째 2번째

2번째 3번째

3번째 4번째

1번째 2번째

2번째 3번째

1번째 2번째

* 중요한점은 루프마다 비교횟수 -1씩 줄어든다는 것, 시작 인덱스는 루프마다 초기화후 1씩 증가.

* 교환시 임시변수 K에 자료보존하고 교환시키면 됨.

* 가끔보면 FLAG 세워서 끝인덱스까지 가지않고도 불필요한 추가 연산을 하지않도록 하는것도 볼수있다.

예를 들어 첫번째 루프 비교에서 교환이 한번도 일어나지 않으면 FLAG = 1을 세우고 루프를 일찍 탈출하게 하는것이다. 실제로 실험해보면 버블정렬에서 루프에서 한번도 교환이 일어나지 않으면 그 시점에서 배열은 이미 정렬된거라고 볼 수있다.

5. 최대값 최소값 POS 이용 정렬 알고리즘

- 사실 배열정렬이 아니라 그냥 오름차순 순서대로 "출력"만 하면 되는 경우 비교-교환이 아닌, 최소값에 최대값을 넣고 전수비교를 시작해 통해 최소값과 최소값이 들어있는 배열(POS)를 구해서 표기한후 해당 자리 POS에 다시는 최소값이 될 수 없도록 배열(POS) = 최대값으로 최대값을 넣은후 "제거"하고 루프를 반복하는 식으로 진행한다. 

1번째 MIN

2번째 MIN

3번째 MIN

4번째 MIN

가장작은값 3번 출력!

3번원소 = MAX;

1번째 MIN

2번째 MIN

3번째 MIN

4번째 MIN

...

반복

이렇게 쓰고나니 좀 복잡해 보이는데, 정렬 알고리즘의 핵심은 단 하나다.

"비교와 교환" 그 방식에 있어서 선택정렬, 버블정렬로 나뉘는건데 침착하게 생각하면 어려울것도 없는 유형.