AniBumiRami의 블로그

본 포스팅은 나름대로의 노하우로 직접 풀이하는 것이므로 타 교재나 동영상과는 다소 다를 수 있음을 미리 말씀 드립니다.

알고리즘 풀이 2탄 버블정렬

우선 버블정렬이 무엇인지 부터 알아봐야겠죠..?

제 블로그에 버블정렬에 대해서 설명 올려놨습니다.

아래 링크를 참고 하세요

http://doanpapa.tistory.com/32

그럼 바로 문제를 보겠습니다.

<처리조건>

1. 본 문제에서는 플래그를 사용하여 임의의 회전 작업시 교환이 발생하지 않을 경우, 정렬이 완료된 상태로 간주하고 작업을 종료시킨다.

2. 배열의 크기가 10일 경우 배열의 요소는 1부터 10까지 구성되는 것으로 한다. 예를 들어, A 라는 배열의 크기가 10일 경우 A(10)으로 표시되고, 배열 요소는 A(1) 부터 A(10)으로 구현된다고 가정한다.

※ 변수 확인

전체적인 알고리즘을 먼저 보고 각 변수가 하는 일을 파악합니다.

N : 증가하지 않고 마지막에 어떤 변수와 (N-1)을 비교하는 것을 보아 각 단계의 버블정렬이 최대 9번이 일어남

S : 각 단계가 끝날때마다 1씩 증가함으로 몇 회차의 단계인지 확인하는 변수

FLAG : 데이터의 교환이 발생하지 않을 경우 작업을 종료 시킬 변수

J : A(J) 로 보아 배열의 순번

TM : 데이터의 교환이 일어날 시 임시로 값을 저장하는 변수

※ 풀이

1. 변수에 값 할당 파트

N : 임의의 데이터를 10개 입력 하여 각 단계당 버블정렬 작업을 해야 할 횟수를 N이라는 변수에 입력

S : 반복문을 돌기 위한 초기 변수 (초기값 0)

FLAG : 교환작업이 일어나면 FLAG 의 값이 변경 (초기값 0)

S 값을 1씩 증가하며 반복문 시작

J : 배열의 순번 (초기값 0)

① : 순번이 증가 되어야 함 J = J + 1

2. 버블정렬 작업 파트

이웃한 두 수를 비교 : A(J) > A(J+1) ②

만약 앞의 수가 크다면 두 수의 교환 작업, 뒤의 수가 크다면 교환작업 없음

교환작업 : 

임시 변수에 앞의 수를 입력 후 TM = A(J)

앞의 자리에 작은 뒤의 수를 입력 A(J) = A(J+1) ③

뒤의 자리에 임시 변수에 입력했던 큰 수를 입력 A(J+1) = TM

교환 작업이 일어났으니 FLAG 의 값을 변경 : FLAG = 1 ④

J >= (N-S) : 총 10개의 데이터의 비교 작업이 다 끝났는지 확인

J는 현재 비교하고 있는 순번이고 총 N개의 데이터 중 S 단계 만큼 뺀 수보다 클 경우 각 단계에서의 버블정렬 비교 작업이 끝난다.

각 단계에서의 비교가 끝날 때 까지 (J 의 값이 N-S 보다 크거나 같은 경우) 각 단계의 버블정렬 작업을 반복한다.

각 단계가 끝났는지 확인 : S ⑤ >= (N-1) 

S는 단계의 횟수이며 총 N개의 수 -1 만큼의 단계가 진행되면 더이상 진행 할 단계가 없으므로 바로 STOP 으로 이동

각 단계가 끝나지 않았으면 FLAG = 0 인지 확인

FLAG = 0 이라는 의미는 각 단계에서 데이터 교환작업이 일어나지 않았음을 의미

교환 작업이 일어나지 않았다는 말은 단계가 끝나기도 전에 정렬이 마무리 되었다는 말이고 그렇다면 바로 STOP 으로 이동

FLAG 가 0이 아니라는 말은 교환 작업이 일어났으므로 단계의 회수인 S 를 1 증가 후 버블정렬 반복 다시 시작

이 때 FLAG 는 0으로 초기화 함

S가 N-1 단계만큼 진행되면 각 단계가 끝났으므로 STOP 으로 이동

※ 정답

① J = J + 1

② A(J+1)

③ A(J) = A(J+1)

④ FLAG = 1

⑤ S

※ 디버그

문제를 푸는 중간에 중요 변수를 알고리즘 흐름 대로 디버그 하는 습괍을 들여야 완벽히 문제를 맞출 수 있습니다.

임의의 10개의 데이터를 예시로 입력하여 디버그를 실시 합니다.

임의의 수 : 27, 18, 3, 22, 16, 8, 4, 9, 10, 15

이상으로 버블정렬 풀이를 마칩니다.

풀이가 필요한 유형이 있거나 질문이 있을 시 댓글 주세요~

이상 도안짱이었습니다~

버블정렬이란~?

버블정렬이란 서로 이웃 된 데이터를 비교하여 큰 수를 뒤로 보내며 정렬하는 방식

간단하게 예를 들어서 바로 설명 할게요

※ 입력받은 수 : 15, 11, 1, 8, 5

○ 1단계 

앞에서부터 이웃 된 2자리의 데이터를 비교하여 높은 수를 뒤로 보낸다.

이웃 된 수의 비교를 처음부터 끝까지 한번씩 비교하여 정렬한다.

○ 2단계

1단계의 결과값으로 다시 처음부터 끝까지 이웃 된 수의 비교를 하여 정렬한다.

○ 3단계

정렬이 완료 될 때까지 반복한다.

위와 같이 모든 정렬이 완료 될 때까지 단계를 늘려가면서 반복하면 됩니다~

이상 도안짱 이었습니다~