버블정렬..그건 또 무엇일까
[출처] 제로베이스
버블정렬을 말 그대로 정렬을 하는 것
인접한 인덱스의 값을 비교하여 큰 수와 작은 수를 앞뒤로 바꾸며 순서를 정렬하는 것 이다.
위의 사진의 경우는 10과 2를 비교했을 때 10이 더 크기 때문에 자리르 바꾸고,
10과 7을 또 비교해서 10이 뒤로가고 10과 21을 비교했을 때 21이 더 크기 때문에 그 자리에서
21과 0을 비교해서 0이 앞으로가고 그 다음 2번째 인덱스부터 똑같이 반복하여 최종적으로
[0,2,7,10,21] 의 순서가 된다.
이 알고리즘이 버블정렬이다.
실제로 컴퓨터공학 가장 기초단계에 배우는 필수개념이라고 알고있는데,
데이터 취업스쿨에서도 배우는 것을 보니 굉장히 중요한 개념이 맞구나 하는 생각이 든다.
먼저 간단한 실습예제 하나를 풀어보았다.
실습1
nums = [10,2,7,21,0]
print(f'not sorted nums: {nums}')
length = len(nums) -1
for i in range(length):
for j in range(length - i):
if nums[j] > nums[j+1]:
nums[j], nums[j+1] = nums[j+1] , nums[j] # 좀 더 쉬운 자리바꾸는 방법
print(f'sorted nums: {nums}')
결과)
not sorted nums: [10, 2, 7, 21, 0]
sorted nums: [0, 2, 7, 10, 21]실습2
이번 실습에서는 깊은복사와 얕은복사에 대해서도 함께 비교해서 보여주고자 한다.
(1) 얕은복사의 경우
[모듈]
def bubbleSort(ns):
length = len(ns) -1
for i in range(length):
for j in range(length - i):
if ns[j] > ns[j +1]:
ns[j], ns[j+1] = ns[j+1], ns[j]
return ns[실행코드]
import random as rd
import sortMod as sm
students = []
for i in range(20):
students.append(rd.randint(170,185))
print(f'students: {students}')
sortedStudents = sm.bubbleSort(students)
print(f'students: {students}')
print(f'sortedStudents: {sortedStudents}')
결과)
students: [178, 177, 178, 179, 185, 171, 176, 179, 176, 172, 176, 175, 184, 181, 176, 179, 177, 175, 173, 177]
students: [171, 172, 173, 175, 175, 176, 176, 176, 176, 177, 177, 177, 178, 178, 179, 179, 179, 181, 184, 185]
sortedStudents: [171, 172, 173, 175, 175, 176, 176, 176, 176, 177, 177, 177, 178, 178, 179, 179, 179, 181, 184, 185]1번째 students 에는 정렬이 되기 전의 값이 들어있고, 2번째 students 에는 정렬 후의 모습이다. 결국 2번째 students 와 sortedStudents 의 값이 같다는 것을 알 수 있기 때문에 굳이 sortedStudents 라는 변수를 생성하지 않아도 students 만으로도 알 수 있어서 저런 경우를 얕은 복사라도 한다. 원본데이터 자체를 변형하여 사용하고 있는 셈이다.
그런데 때때로 원본을 건드리면 안 되는 작업이 더 많기 때문에 깊은 복사를 통해 원본데이터를 유지하면서 쓰는 방법도 알아보자.
(2) 깊은복사의 경우
[모듈]
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
[실행코드]
import random as rd
import sortMod as sm
students = []
for i in range(20):
students.append(rd.randint(170,185))
print(f'students: {students}')
sortedStudents = sm.bubbleSort(students)
print(f'students: {students}')
print(f'sortedStudents: {sortedStudents}')
결과)
students: [171, 179, 179, 185, 171, 183, 170, 177, 182, 173, 172, 185, 173, 171, 181, 179, 174, 183, 177, 175]
students: [171, 179, 179, 185, 171, 183, 170, 177, 182, 173, 172, 185, 173, 171, 181, 179, 174, 183, 177, 175]
sortedStudents: [170, 171, 171, 171, 172, 173, 173, 174, 175, 177, 177, 179, 179, 179, 181, 182, 183, 183, 185, 185]위의 결과를 보면 2번째 students 의 값이 변하지 않고 유지되고 있는 것을 볼 수 있다.
sortedStudents 의 값만 정렬되어 나타난다. 이는 함수속 students 는 여전히 ns 로 들어가지만 ns 자체를 쓰지 않고 cns 로 ns 를 copy하여 cns 의 값을 return 받고 있기 때문에
원본자체는 건드리지 않을 수 있는 것 이다.
와.........................엄청 복잡한 것 같으면서도 굉장히 안전한 방법이라 꼭 외워둬야겠다는 생각이 든다.
일 할 때, 알고 있으면 굉장한 도움이 될 것 같고 센스있는 인재로 보일 수 있을 것 같다
ㅋㅋㅋㅋㅋㅋㅋㅋㅋ (외워야지..)
이번 알고리즘도 유용했다.
그러나, 코딩은 손코딩이고 반복학습만이 살 길 이다.
