[정보처리기사][알고리즘][자료구조] 버블정렬3

Q. 버블 정렬 기법을 응용하여 한 번은 왼쪽에서 오른쪽으로 진행하면서 최대값을 우측으로 보내고, 한 번은 오른쪽에서 왼쪽으로 진행하면서 최소값을 좌측으로 보내는 방법을 반복하면서 정렬하는 순서도를 작성하시오.

1. 자료가 저장될 배열 D를 선언한다.

 

2. 정렬할 자료가 10개라고 가정했으므로 N을 10으로 초기화한다.

 

3. 자료의 왼쪽 첫 번째 위치는 1이므로 Left를 1로 초기화한다.

 

4. 자료의 오른쪽 마지막 위치는 정렬할 자료의 개수와 같으므로 Right를 N으로 초기화한다.

 

5. Left가 Right보다 작으면 다음 회전을 수행한다.

 

1) No일 경우, 6으로 간다.

 

2) Yes일 경우, 첫 번째 반복문은 왼쪽에서 오른쪽으로 진행하며 정렬하는 과정이다. 반복변수 i가 Left에서 Right-1이 될때까지 1씩 증가하면서 반복한다.

 

A. 자료의 대소를 비교한다. 첫번째 반복문에서 자기 자싱을 그 다음 자료와 비교한다는 것을 생각한다.

 

A) Yes일 경우, buf에 D(i)을 입력한다.

 

a. D(i)에 D(i+1)을 입력한다.

 

b. D(i+1)에 buf를 입력한다.

 

c. 자료 교환이 수행될때마다 현재의 위치를 Shift에 저장한다.

 

B) No일 경우, 다음 반복을 진행한다.

 

3) 반복이 종료되면, 다음 정렬의 시작 위치를 지정한다. 다음 정렬의 시작 위치는 마지막으로 자료교환이 수행된 시점부터라는 것을 생각한다.

 

4) 두 번째 반복문은 오른쪽에서 왼쪽으로 진행하며 정렬하는 과정이다. 반복변수가 i가 Right에서 Left+1이 될때까지 -1씩 증가하면서 반복한다.

 

A. 자료의 대소를 비교한다. 두 번째 반복문에서는 자기 자신을 그 이전 자료와 비교한다는 것을 생각한다.

 

A) Yes일 경우, buf에 D(i-1)을 입력한다.

 

a. D(i-1)에 D(i)를 입력한다.

 

b. D(i)에 buf를 입력한다.

 

c. 자료의 교환이 수행될때마다 현재 위치를 Shift에 저장한다.

 

B) No일 경우, 다음 반복을 진행한다.

 

5) 다음 전렬의 시작 위치를 저장한다. 다음 정렬의 시작 위치는 마지막으로 자료 교환이 수행된 시점부터라는 것을 생각한다. 그리고 5번으로 간다.

 

6. D에 저장된 값을 출력하고 끝낸다.

 

 

해당 글은 제가 만든 어플을 기준으로 작성하였습니다.

더 많은 자료는 알고리즘 어플을 이용해주세요.