[알고리즘] 버블정렬, 깊은 복사, 얕은 복사

[버블정렬]

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

---

1. 다음과 같은 리스트가 있다고 하자.

[ 10, 2, 7, 21, 0 ]

 

2. 10과 2를 비교하여, 10이 더 크므로 자리를 바꾼다.

[ 2, 10, 7, 21, 0 ]

 

3. 10과 7를 비교하여, 10이 더 크므로 자리를 바꾼다.

[ 2, 7, 10, 21, 0 ]

 

4. 10과 21을 비교하여, 21이 더 크므로 자리를 바꾸지 않고 이제 21과 0을 비교하여 자리를 옮긴다.

[ 2, 7, 10, 0, 21 ]

 

5. 다시 앞에서부터 2와 7을 비교한다...

 

5. 다음이 한 사이클이다.

이를 리스트의 요소 갯수만큼 반복하면 모든 값들이 정렬 되어있을 것이다.

 

6. 단, 다음 사이클을 돌릴 때는 이미 정렬 시켜놓은 (위의 사이클에서는 21) 은 굳이 비교할 필요 없기 때문에 사이클이 한번 돌 때마다, 1개씩 덜 비교한다.

---

• 버블 소트 코드
  그리고 아래 코드에서는 구현 안했는데, flag라는 변수를 만들어 첫번 째 for문 마다 True 값을 넣고, 두 번째 for문 에서 자리가 바뀔 때마다 False 값을 넣겠끔 만들어, flag 가 True 일 경우 함수를 종료시킨다면. 탐색 시간이 보다 단축되지 않을까.

def bubblesort(datas):
    for i in range(len(datas)):
        for j in range(len(datas)-i-1):        # i는 0부터 시작하기 때문에 1을 더 빼주게 되었다.
            if datas[j] > datas[j+1]:          # 만약 1을 더 빼주지 않으면 j+1이 나중에 리스트 범위를 초과하게 된다.
                datas[j], datas[j+1] = datas[j+1], datas[j]
                print(datas)

datas = [10,2,7,21,3,0]
bubblesort(datas)
print(datas)

''' 어떻게 정렬이 되어가는지 과정
[2, 10, 7, 21, 3, 0]              ... 2와 10이 바뀌었다.
[2, 7, 10, 21, 3, 0]              ... 7과 10이 바뀌었다.
[2, 7, 10, 3, 21, 0]              ... 3과 21이 바뀌었다.
[2, 7, 10, 3, 0, 21]              ... 0과 21이 바뀌었다.    *( 이제 21을 더 이상 비교할 필요 없다. )
[2, 7, 3, 10, 0, 21]              ... 3과 10이 바뀌었다.
[2, 7, 3, 0, 10, 21]              ... 0과 10이 바뀌었다.    *( 이제 10을 더 이상 비교할 필요 없다. )
[2, 3, 7, 0, 10, 21]              ... 3과 7이 바뀌었다.
[2, 3, 0, 7, 10, 21]              ... 0과 7이 바뀌었다.     *( 이제 7을 더 이상 비교할 필요 없다. )
[2, 0, 3, 7, 10, 21]              ... 0과 3이 바뀌었다.     *( 이제 3을 더 이상 비교할 필요 없다. )
[0, 2, 3, 7, 10, 21]              ... 0과 2가 바뀌었다.     *( 이제 2를 더 이상 비교할 필요 없다. )
[0, 2, 3, 7, 10, 21]              ... 정렬 종료
'''

---

[실습1] 학생들 키를 받아 이를 버블 정렬 해 봅시다. 

def bubble(datas):
    for i in range(len(datas)):
        for j in range(len(datas)-i-1):
            if datas[j] > datas[j+1]:
                datas[j],datas[j+1] = datas[j+1],datas[j]

import random
students = [random.choice(range(170,185)) for _ in range(20)]
print(f'학생들 키 : {students}')
bubble(students)
print(f'정렬한 학생들 키 : {students}')

'''
학생들 키 : [183, 182, 184, 170, 182, 177, 170, 182, 175, 177, 172, 171, 180, 177, 181, 170, 180, 182, 
184, 171]
정렬한 학생들 키 : [170, 170, 170, 171, 171, 172, 175, 177, 177, 177, 180, 180, 181, 182, 182, 182, 182, 183, 184, 184]
'''

하면서 알게 된건데

random.sample(seq,뽑을 갯수) 는 중복을 허용하지 않네요.

중복을 허용하여 여러번 뽑기 위해서는 random.choice(seq) 또는 random.randint(시작, 끝)를 여러번 해주어야합니다.

 

---

[실습2] 실습1에서 정렬 되기 전 데이터와 정렬된 후의 데이터 둘다 갖고 싶을 때

• 깊은 복사를 해서 정렬시켜보자.

import random
import copy
def bubble(datas, deepCopy = True):          # 매개 변수를 하나 더 줬다.

    if deepCopy:
        copydatas = copy.copy(datas)         # 깊은 복사
    else : copydatas = datas                 # 얕은 복사

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

students = [random.choice(range(170,185)) for _ in range(20)]
print(f'깊은 복사 ver. : \n{bubble(students,deepCopy=True)}')
print(f'원본 데이터 : \n{students}')
print()

print(f'얕은 복사 ver. : \n{bubble(students,deepCopy=False)}')
print(f'원본 데이터 : \n{students}')

'''
깊은 복사 ver. : 
[170, 171, 171, 172, 172, 174, 174, 176, 177, 178, 178, 178, 179, 179, 181, 183, 183, 183, 184, 184]   
원본 데이터 :
[178, 176, 172, 177, 184, 172, 174, 179, 183, 183, 171, 178, 171, 170, 184, 174, 181, 179, 178, 183]   

얕은 복사 ver. :
[170, 171, 171, 172, 172, 174, 174, 176, 177, 178, 178, 178, 179, 179, 181, 183, 183, 183, 184, 184]   
원본 데이터 :
[170, 171, 171, 172, 172, 174, 174, 176, 177, 178, 178, 178, 179, 179, 181, 183, 183, 183, 184, 184]   
'''

깊은 복사를 했을 때는 원본 데이터가 그대로였고,

얕은 복사를 했을 때는 원본 데이터도 정렬되어있음을 알 수 있다.