[알고리듬] #73 버블 정렬

[key word] 거품 정렬, 셔플링, 오름차순, 내림차순, 플랙 소트

파이썬 실습창을 열 수 있습니다.실습창 열기

 

버블 정렬

 

1. 정렬의 개념

정렬(sort)은 항목(item)들을 체계적(오름차순 또는 내림차순 등) 으로   정리하는 과정을 일컫는 말입니다.

정렬을 하면 다음과 같은 장점이 있습니다.

• 검색(search)을 효율적으로 할 수 있다.
• 일련의 아이템에 대한 병합(merge)을 효율적으로 할 수 있다.
• 정의된 순서로 데이터 처리를 할 수 있다.

파이썬 시스템에는 정렬 함수와 정렬 메소드가 준비되어 있어서 매우 쉽게 사용할 수 있습니다.

a=[1,5,2,4,3]    # 원시 데이터
b=sorted(a)      # 정렬 함수(a를 정렬하여 b에 바인딩, out-place sort)
print(a)         # 원시 데이터 그대로 출력
print(b)         # 정렬된 데이터 출력 

a.sort()         # 정렬 메소드, a 자신을 정렬(in-place sort)
print(a)

'''
출력 결과입니다.
[1, 5, 2, 4, 3]  <--- a의 원시 데이터
[1, 2, 3, 4, 5]  <--- b
[1, 2, 3, 4, 5]  <--- a
'''

 

정렬 알고리듬(sort algorithm)은 30가지 이상 연구되어 있습니다.

가장 빠른 것으로 알려져서 많아 사용하는 방법은 퀵 소트(quick sort)입니다.

파이썬에서 제공하는 sort도 퀵 소트입니다.

우리는 다음에 quick sort 자체를 공부합니다. 

 

정렬의 반대로 특정 데이터셋을 임의의 순서로 항목을 재정렬하는 것을 셔플링(shuffling)이라고 합니다.

import random      # 셔플 메소드는 random 모듈에 있습니다.
a=[1,2,3,4,5]      # a는 정렬되어 있습니다.
random.shuffle(a)  # a를 마구잡이로 섞습니다.
print(a)

'''
[4, 5, 1, 2, 3]   <--- 실행할 때마다 다릅니다.
'''

- 오름차순 정렬(ascending sort, 악센딩 소트): 점점 큰 순서로 정렬하는 것

- 내림차순 정렬(descending sort, 디센딩 소트): 점점 작은 순으로 정렬하는 것

 

2. 버블 정렬의 학습 이유

버블 정렬(bubble sort)은 기본적인 정렬 알고리듬입니다.

코드는 간단하지만 실행 속도가 늦습니다. 

거의 사용하지 않지만 대부분 정렬이 된 데이터 등에서는 효과적일 수 있습니다.

 

우리가 버블 정렬을 공부하려는 목적은 정렬의 구체적 방법, 리스트의 사용법 등을 익히는 것입니다.

또, 기사, 기능사, 임용고사 등에 출제 되기도 하기 때문입니다.

 

3. 버블 정렬 방법

리스트에 1, 5, 2, 4, 3이 있습니다.

오름차순 정렬하려고 합니다.

• 단계 1
  - 1과 5를 비교하여 오른쪽에 큰 수가 오도록 교환(지금은 교환 없음)
  - 5와 2를 비교하여 오른쪽에 큰 수가 오도록 교환(교환함)
  - 바뀌어 있는 5와 4 비교(교환)
  - 바뀌어 있는 5와 3 비교(교환)
  결국 전체에서 최대값이 가장 오른쪽에 오게됨.
• 단계 2
  다시 처음부터 위와 같이 진행하는데 마지막 앞까지 진행
  4개 중에서 최대값이 4번째에 오게됨.
• 단계 3
  다시 처음부터 3번째까지 진행
  3개 중에서 최대값 3번째에 오게됨
• 단계 4
  다시 처음부터 2번째까지 진행
  2개 중에서 최대값 2번째에 오게됨
• 마지막 1개는 그냥 둠(최소값이므로 1번째에 둠)

원리를 이해하셨지요?

이렇게 하면 오름차순 정렬이 되겠지요?

 

4, 코딩하기

코딩하였습니다.

a=[1,5,2,4,3]                          # data set
n=len(a)                               # data 개수
for i in range(n-1):                   # 단계(단계는 data 개수 보다 1이 작다)
    for j in range(n-1-i):             # 마지막이 단계마다 당겨진다.
        if a[j]>a[j+1]:                # 왼쪽이 오른쪽 보다 크면
            a[j],a[j+1]=a[j+1],a[j]    # 왼쪽과 오른쪽을 교환한다.
print(a) 

'''
결과입니다.
[1, 2, 3, 4, 5]

4번 줄을 이해하세요.
i(단계)가 크지면 마지막은 줄어듭니다.

내림차순 정렬은 
5번의 부등호를 반대로 하여 작은 값을 오른쪽으로 보냅니다.
'''

 

5. 방법의 개선

정렬을 진행하는 도중에 정렬이 완료되는 경우가 많습니다(통계적으로 50%).

예를 들어, 1, 2, 3, 5, 4 이면 한 단계만 거치면 전체가 정렬됩니다.

이러한 경우 나머지 과정을 생략하고 출력할 수는 없을까요?

정렬이 완료된 것을 어떻게 알 수 있지요?

한 단계를 마쳤는데 교환한 적이 없으면 정렬이 완료된 것입니다. 

 

다음과 같이 코딩을 수정하면 실행 시간이 통계적으로 반으로 줄어듭니다.

a=[1,5,2,4,3]
n=len(a)
for i in range(n-1):
    flag=1                 # 단계가 시작할 때 교환이 없다고 가정함
    for j in range(n-1-i):
        if a[j]>a[j+1]:
            a[j],a[j+1]=a[j+1],a[j]
            flag=0         # 교환이 있으면 flag이 0으로 바뀜    
    if flag:break          # flag이 1인 상태이면 교환이 없음을 의미하므로 종료   
print(a) 

'''
flag은 임의의 변수입니다.
그러나 이러한 경우 일반적으로 flag이라는 변수를 사용합니다.
그래서 이 방법을 flag sort라고도 합니다.
'''

 

두개의 수를 연속하여 비교하는 모습을 그림으로 그리면 거품을 닮았다고 하여 거품(bubble) 정렬이라 이름하였습니다.

수고하셨습니다.

안녕!