Bubble Sort

참고 문헌

< C언어로 쉽게 풀어쓴 자료구조 내용 >

< 윤성우의 열혈 자료구조 내용 >

< 쉽게 배우는 알고리즘 내용  >

 

구현 version1

정렬 방식은 오름 차순으로 한다.

버블 정렬은 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면

서로 교환하는 비교-교환 과정을 리스트의 왼쪽 끝에서 시작하여 오른쪽 끝까지 진행한다.

이러한 리스트의 비교-교환 과정(스캔)이 한 번 완료되면 가장 큰 레코드가 리스트의 오른쪽 끝으로 이동한다.

이러한 비교-교환 과정은 전체 숫자가 정렬될 때까지 계속 된다.

정렬이 안된 오른쪽 리스트를 한 번 스캔하면, 오른쪽 리스트의 오른쪽 끝에 가장 큰 레코드가 위치하게 되고, 오른쪽 리스트는 추가된 레코드를 포함하여 정렬된 상태가 된다.

이러한 스캔 과정을 정렬이 안 된 왼쪽 리스트에서 반복하여 적용하면 정렬이 완료된다.

리스트 {5,3,8,1,2,7} 를 버블 정렬하는 첫 번째 스캔 과정은 아래의 [그림 1]을 보자.

 

[그림 1 : 버블 정렬의 한 번의 스캔 과정]

위의 [그림 1]은 버블 정렬의 한 번의 스캔 과정을 도식화 한 것.

먼저 5와 3을 비교하면, 5가 더 크므로 서로 교환하고

다음으로 5와 8을 비교하게 되면 8이 더 크므로 교환 없이 다음 단계로 진행한다.

이러한 과정이 반복되면 8이 가장 리스트의 오른쪽 끝으로 이동하게 된다.

이미 자기 위치에 자리 잡은 8을 제외한 나머지 왼쪽 리스트를 대상으로 이 과정을 반복한다.

한 번의 스캔에 의해 가장 큰 레코드가 리스트의 오른쪽 끝으로 이동하게 된다.

이러한 반복 과정이 왼쪽 리스트가 정렬이 완료될 때까지 수행되어 전체 리스트가 정렬되는

과정은 아래 [그림 2]를 보자.

[그림 2 : 버블 정렬의 전체 정렬 과정 ]

버블 정렬 알고리즘 의사 코드

알고리즘 설명

먼저, 하나의 스캔은 j = 0부터 j = i - 1까지 반복하는 루프로 구성되고,

j번째 요소와 j+1번째 요소를 비교하여 크기순으로 되어 있지 않으면 교환한다.

i는 하나의 스캔이 끝날 때마다 1씩 감소한다.

이런 스캔 과정이 n-1번 되풀이되면 정렬이 끝나게 된다.

 

프로그램 실행결과

소스 파일

main.c

0.00MB

 

구현 version2

Bubble Sort의 원리는 
인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환하는 비교-교환 과정을 리스트의 왼쪽 끝에서 시작하여 오른쪽 끝까지 진행한다.
이러한 리스트의 비교-교환 과정(스캔)이 한번 완료되면 가장 큰 레코드가 리스트의 오른쪽 끝으로 이동된다.
이러한 비교-교환과정은 전체 숫자가 정렬될 때까지 계속된다.
정렬이 안 된 오른쪽 리스트를 한 번 스캔하면 오른쪽 리스트의 오른쪽 끝에 가장 큰 레코드가 위치하게 되고,
오른쪽 리스트는 추가된 레코드를 포함하여 정렬된 상태가 된다.
이러한 스캔과정을 정렬이 안된 왼쪽 리스트에서 반복하여 적용하면 정렬이 완료된다.

예시
                 5 3 8 1 2 7 <= 초기상태
                 5 3 8 1 2 7 <= 5와 3을 교환
                 3 5 8 1 2 7 <= 교환 없음
                 3 5 8 1 2 7 <= 8과 1을 교환
                 3 5 1 8 2 7 <= 8과 2를 교환
                 3 5 1 2 8 7 <= 8과 7을 교환
                 3 5 1 2 7 8 <= 하나의 스캔 완료.
먼저, 5와 3을 비교하면 5가 더 크므로 서로 교환하고, 다음으로 5와 8을 비교하게 되면 8이 더 크므로 교환 없이
다음 단계로 진행한다. 이러한 과정이 반복되면 8이 가장 리스트의 오른쪽 끝으로 이동하게 된다.
이미 자기 위치에 자리 잡은 8을 제외한 나머지 왼쪽 리스트를 대상으로 이 과정을 반복한다.
한 번의 스캔에 의해 가장 큰 레코드가 리스트의 오른쪽 끝으로 이동하게 된다. 이러한 반복 과정이 왼쪽 리스트가
정렬이 완료될 때까지 수행되어 전체 리스트가 정렬된다. 아래는 전체 리스트가 정렬되는 과정이다.
               3 5 1 2 7 8 <= 스캔 1
               3 1 2 5 7 8 <= 스캔 2
               1 2 3 5 7 8 <= 스캔 3
               1 2 3 5 7 8 <= 스캔 4
               1 2 3 5 7 8 <= 스캔 5
               1 2 3 5 7 8 <= 스캔 완료

프로그램 실행결과

소스 파일

main.c

0.00MB

 

구현 version3

버블정렬도 선택정렬처럼 제일 큰 원소를 끝자리로 옮기는 작업을 반복하는 정렬.

다만 가장 큰 원소를 오른쪽으로 옮기는 방법이 다를 뿐이다.

 

아래는 버블정렬 알고리즘 의사코드

위의 알고리즘 설명

알고리즘은 2개의 루프로 존재.

첫 번째 for루프인 알파는 선택정렬의 for루프와 역할이 똑같다.

루프를 돌 때마다 제일 큰 원소를 맨 오른쪽으로 보내고 정렬할 배열의 크기를 하나씩 줄인다.

그 밑쪽의 for루프인 베타가 하는 역할은 가장 큰 원소를 맨 오른쪽으로 보내는 것이다.

이 부분이 선택 정렬과 차이가 있다.

버블정렬은 왼쪽부터 이웃한 수를 비교하면서 순서가 제대로

되어 있지 않으면 하나하나 바꾸어 나간다.

 

위에서 진행한 버블정렬 알고리즘은 알고리즘이 수행을 시작할 때나,

중간에 배열이 이미 정렬이 되어 있는 상태라도 계속 끝까지 무의미한 순환을 계속한다.

이를 위해서 위의 알고리즘에 한가지 장치를 하는 방법이 있다.

아래의 알고리즘을 보자.

위의 알고리즘 설명

프로그램 실행결과

소스 파일

main.c

0.00MB