버블 정렬(Bubble Sort)(파이썬)

 

 

 

버블 정렬

---

 

 

 

 

버블 정렬(Bubble Sort)

버블정렬이란 두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘을 말한다. 물론 정렬의 원칙에 따라서는 버블정렬을 내림차순으로 구현할 수도 있고, 오름차순으로 구현할 수도 있다. 

 

버블정렬(Bubble Sort) 알고리즘 원리 

앞뒤에 데이터를 계속 비교해서 데이터를 정리한다는 버블 정렬의 개념은 이해하기 편하다. 그러나 실제로 코드로 구현할 때는 막힐 수도 있다. 따라서 버블정렬의 예시를 통해 실제 어떤 원리를 통해서 정렬이 되는지 알아보고자 한다. 

 

적용 횟수	데이터의 형태	교환이 발생 여부	총 교환 횟수
원본 데이터	1, 9, 3, 2	0회	0회
1회 버블 정렬 로직 적용	1, 3, 2, 9	2회	2회
2회 버블 정렬 로직 적용	1, 2, 3, 9	1회	3회

 

• 버블 정렬의 원리 상세 설명
  • 1회 로직 적용시 발생하는 일
    • 시작하는 인접한 데이터는 1과 9 비교가 이루어진다. 그러나 이 부분은 정렬이 된 상태이기 때문에 아무런 일이 발생하지 않는다.
    • 다음 인접한 데이터는 9와 3이다. 이 9는 3보다 크기 때문에 뒤로 가야 하고, 1회 교환이 발생하였다. 
    • 다음 인접한 데이터는 9와 2이다. 동일한 이유로 교환이 1회 발생하며 9는 맨 뒤로 가게 된다.
    • 따라서 1회 로직에서는 총 2회의 교환이 이루어졌다.
  • 2회 로직 적용시 발생하는 일 상세 설명
    • 데이터는 현재 1, 3, 2, 9이고 시작하는 인접한 데이터는 1과 3이다. 그러나 이 부분에서는 정리할 필요가 없기 때문에 아무런 일이 발생하지 않는다.
    • 다음 인접한 데이터는 3과 2이이다. 여기서도 3은 2보다 큰 수이기 때문에 1회 교환이 발생한다. 
    • 다음 인접한 데이터는 3과 9인데, 이 부분에서는 아무런 일이 발생하지 않기에 교환횟수는 0회 이다. 
    • 따라서 2회 로직 적용시 기록되는 교환횟수는 1회가 된다. 

 

이 원리를 차근찬근 이해하고 위에 있는 그림 예시를 보면, 버블정렬 알고리즘의 원리를 완벽하게 이해하는데 도움이 될 것이다. 알고리즘의 핵심은 항상 효율적이고 논리적으로 구성하는데 있다. 따라서 버블 정렬를 코드로 구현할 때 반드시 알아두어야 할 원리를 집약하면 아래와 같다. 

 

• 버블 정렬의 원리 요약
  • 원리1. 총 비교 횟수는 데이터 길이 -1 회 발생한다. 
  • 원리2. 맨 뒤에 있는 수는 이미 정렬이 완료된 수이기에 다음 로직 적용시 제외 시켜서 반복문을 구성한다. 
  • 원리3. 정렬이 끝난 경우 무한 Loop를 돌지 않기 위해 확인할 수 있는 변수를 활용한다. 
  • 원리4. 총 몇 번 교환이 이루어졌는지 파악할 수 있도록 교환이 이루어졌을 때 데이터로 기록한다. 

 

 

 

처음부터 끝까지 인접하는 인덱스의 값을 순차적으로 비교하면서 큰 숫자를 가장 끝으로 옮기는 알고리즘이다.

 

nums = [10, 2, 7, 21, 0]

length = len(nums) - 1 # 총 비교 횟수는 데이터 길이보다 1회 작게 이루어져야 함
for i in range(length):
    for j in range(length-i): # 정리된 데이터는 반복할 필요가 없기 때문에 i회를 제외 시킨다
        if nums[j] > nums[j+1]: # 버블 정렬을 오름차순 혹은 내림차순으로 결정할 수 있는 영역
        ## 순서를 바꿔 준 뒤에 교환이 이뤄졌음을 알린다.
            temp = nums[j]
            nums[j] = nums[j+1]
            nums[j+1] = temp

        print(nums)
    print()

print(f'sorted nums: {nums}')

 

 

 

새 학년이 되어 학급에 20명의 새로운 학생들이 모였다. 학생들을 키 순서로 줄 세워 보자. 학생들의 키는 random 모듈을 이용해서 170 ~ 185사이로 생성한다

import sortMod as sm
import random as rd

students = []

for i in range(20):
    students.append(rd.randint(170, 185))

print(f'students: {students}')
print(f'students length: {len(students)}')

# 얕은 복사
# sortedStudents = sm.bubbleSort(students, deepCopy=False)
# print(f'students: {students}')
# print(f'sortedStudents: {sortedStudents}')

# 깊은 복사
sortedStudents = sm.bubbleSort(students)
print(f'students: {students}')
print(f'sortedStudents: {sortedStudents}')

import copy

def bubbleSort(ns, deepCopy = True):

    if deepCopy:
        cns = copy.copy(ns)
    else:
        cns = ns

    length = len(cns) - 1
    for i in range(length):
        for j in range(length - i):
            if cns[j] > cns[j + 1]:
                cns[j], cns[j + 1] = cns[j + 1], cns[j]

    return cns

students: [178, 184, 177, 171, 175, 178, 173, 175, 180, 171, 182, 178, 175, 183, 176, 180, 172, 175, 182, 185]
students length: 20
students: [178, 184, 177, 171, 175, 178, 173, 175, 180, 171, 182, 178, 175, 183, 176, 180, 172, 175, 182, 185]
sortedStudents: [171, 171, 172, 173, 175, 175, 175, 175, 176, 177, 178, 178, 178, 180, 180, 182, 182, 183, 184, 185]