버블 정렬

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

잘 사용되지 않는다. 하지만, 이해하기 쉬워서 정렬의 입문으로 잘 활용된다. - 잘 사용되지 않는 이유는? → BIG O 때문이다! → 배열의 원소가 N개 있다고 하면, 한번 비교 할 때 총 N - 1번 비교해야 된다. 따라서, 전체 원소 개수가 N 개 있다고 하면, BIG O 는 N^2 이므로 굉장히 비효율적이다.

TIP : 인접한 인덱스끼리 위치 바꾸기

# 원론적인 두 위치의 값을 바꾸는 방법
temp = nums[j]
nums[j] = nums[j+1]
nums[j+1] = temp


# 편리하게 바꾸는 방법
nums[j], nums[j+1] = nums[j+1], nums[j]
Python
복사

# 버블정렬 알고리즘을 사용해서 정렬하자
nums = [10,2,7,21,0]
print(f'not sorted nums : {nums}')

length = len(nums) - 1 # 마지막 인덱스 : 4
for i in range(length): # 전체 원소의 개수 - 1만큼 반복
    for j in range(length - i): # 원소별 대소비교 횟수가 1씩 줄어든다. 
        if nums[j] > nums[j+1]: # 다음 인덱스의 값이 더 작으면
            # 두 위치의 값을 바꾸는 방법
            nums[j],nums[j+1] = nums[j+1], nums[j]

print(f'sorted nums: {nums}')
Python
복사

모듈 사용해서 버블 정렬 실습하기

# 버블 정렬 함수 만들기
# bubble.py
def bubbleSort(ns): # '키'값을 담고 있는 숫자 리스트가 들어올 것

    length = len(ns) - 1 # 마지막 값의 인덱스 저장
    for i in range(length): # 전체원소의 개수 - 1만큼 반복
        for j in range(length - i):
            if ns[j] > ns[j+1]:
                ns[j], ns[j+1] = ns[j+1],ns[j]


    return ns
Python
복사

import random
import bubble as bb

students = []

for i in range(20): # 170 ~ 185 사이의 정수 추출 20회 반복 
    students.append(random.randint(170,185))

print(students)

sorted_students = bb.bubbleSort(students)
print(sorted_students)
Python
복사

알고 넘어가야 할 점

•

얕은 복사

위의 경우, students 와 sorted_students가 모두 순서가 바뀐 결과를 확인할 수 있다. 그 이유는 결국 함수 내에서 활용되는 students 가 변했기 때문이다. 이를 얕은 복사라고 한다.

•

깊은 복사

그렇다면, 기존의 원본 객체에는 변화가 없게 하려면, 함수 내 default값을 지정해주면 된다.

→ import copy 로 copy 라이브러리를 불러오고

→ deepCopy=True 를 함수 인자에서 지정해주자.

→ 함수 내 조건에서

import copy

def bubbleSort(ns, deepCopy=True): # 기본값으로 깊은 복사를 설정해놓고
		
		if deepCopy: # if 절을 이용해서 깊은 복사/ 얇은 복사를 설정할 수 있다. 
				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 ns
Python
복사

# 실행파일에서 기본값으로 함수를 수행하면, 원본 객체는 변하지 않은 것을 확인할 수 있다. 
sorted_students = bb.bubbleSort(students)
Python
복사

# 버블 정렬 함수 만들기
# bubble.py
import copy
def bubbleSort(ns,asc=True): # '키'값을 담고 있는 숫자 리스트가 들어올 것

    c_ns = copy.copy(ns)

    length = len(c_ns) - 1 # 마지막 원소에 해당하는 인덱스 저장
    for i in range(length): # 전체 아이템의 개수 - 1번만 버블 정렬을 수행한다.
        for j in range(length - i): # 각 아이템마다 크기를 비교하는 횟수는 앞의 몇번째 순서냐에 따라 다르다.
            # 오름차순 정렬

            if asc:
                if c_ns[j] > c_ns[j+1]:
                    c_ns[j], c_ns[j+1] = c_ns[j+1],c_ns[j]
            else:
                if c_ns[j] < c_ns[j+1]:
                    c_ns[j], c_ns[j+1] = c_ns[j+1],c_ns[j]

            print(f'ns : {c_ns}')
        print()
    return c_ns
Python
복사

# 알파벳과 숫자로 이루어진 리스트를 순위 알고리즘을 이용해서 정렬하자.
# 알파벳은 아스키 코드를 이용한다.
import bubble
import random

nums = random.sample(range(1,20),10)
print(f'not sorted nums : {nums}')

result = bubble.bubbleSort(nums)
print(f'sorted nums by asc: {result}')

result2 = bubble.bubbleSort(nums,False)
print(f'sorted nums by desc: {result2}')
Python
복사