알고리즘
[알고리즘] 버블정렬, 깊은 복사, 얕은 복사
scone
2022. 5. 14. 17:24
[버블정렬]
- 처음부터 끝까지 인접하는 인덱스의 값을 순차적으로 비교하면서 큰 숫자를 가장 끝으로 옮기는 알고리즘이다.
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]
'''깊은 복사를 했을 때는 원본 데이터가 그대로였고,
얕은 복사를 했을 때는 원본 데이터도 정렬되어있음을 알 수 있다.