버블 정렬(BubbleSort) O(n^2)
가장 큰걸 뒤로 보내자
def bubblesort(lst):
iters = len(lst)-1
for iter in range(iters):
wall=iters-iter
for cur in range(wall):
if lst[cur]>lst[cur+1]:
lst[cur] , lst[cur + 1] = lst[cur+1],lst[cur]
print(lst)
lst = [4, 6, 2, 9, 1]
bubblesort(lst)[4, 6, 2, 9, 1] # 정렬되지 않은 배열
1단계 : [4, 6, 2, 9, 1]
4와 6을 비교합니다!
4 < 6 이면 그대로 둡니다.
2단계 : [4, 6, 2, 9, 1]
6과 2를 비교합니다!
6 > 2 이므로 둘을 변경합니다!
[4, 2, 6, 9, 1] 이렇게요!
3단계 : [4, 2, 6, 9, 1]
6과 9를 비교합니다!
6 < 9 이면 그대로 둡니다.
4단계 : [4, 2, 6, 9, 1]
9와 1를 비교합니다!
9 > 1 이므로 둘을 변경합니다!
[4, 2, 6, 1, 9] 이렇게요!
자, 그러면 이제 한 바퀴를 돌렸죠?
이 과정에서 가장 큰 숫자인 9가 맨 뒤로 왔습니다.
큰 게 나오면 둘의 자리를 변경했으니 가장 맨 뒤에 갔다는 소리입니다!
그러면, 맨 뒷자리를 제외하고 다시 한 번 돌리면 됩니다!
5단계 : [4, 2, 6, 1, 9]
4와 2을 비교합니다!
4 > 2 이므로 둘을 변경합니다.
[2, 4, 6, 1, 9] 이렇게요!
6단계 : [2, 4, 6, 1, 9]
4와 6을 비교합니다!
4 < 6 이면 그대로 둡니다.
7단계 : [2, 4, 6, 1, 9]
6와 1을 비교합니다!
6 > 1 이므로 둘을 변경합니다!
[2, 4, 1, 6, 9] 이렇게요!
그러면 이제 두 번째로 큰 숫자인 6이 맨 뒤에서 두번쨰로 왔습니다!
여기까지만 비교하시면 됩니다. 6과 9을 비교할 필요는 없습니다.
다시 한 번 가볼게요!
8단계 : [2, 4, 1, 6, 9]
2와 4을 비교합니다!
2 < 4 이면 그대로 둡니다.
9단계 : [2, 4, 1, 6, 9]
4와 1을 비교합니다!
4 > 1 이므로 둘을 변경합니다!
[2, 1, 4, 6, 9] 이렇게요!
자, 이제 세 번쨰로 큰 숫자인 4가 맨 뒤에서 세번째로 왔습니다!
마지막 비교만 하면 됩니다!
10단계 : [2, 1, 4, 6, 9]
2와 1을 비교합니다!
2 > 1 이므로 둘을 변경합니다!
[1, 2, 4, 6, 9] 이렇게요!선택 정렬(SelectionSort)
가장 작은걸 앞으로 보내자
def selectionsort(lst):
iters = len(lst)-1
for iter in range(iters):
minimum=iter #가장작은값으로 가정
for cur in range(iter+1,len(lst)):
if lst[cur]<lst[minimum]:
minimum=cur
if minimum!=iter: #가정한값이 가장작은값이 아니라 바꼈을경우
lst[iter],lst[minimum]=lst[minimum],lst[iter]
print(lst)
lst = [4, 6, 2, 9, 1]
selectionsort(lst)[4, 6, 2, 9, 1] # 정렬되지 않은 배열
1단계 : [4, 6, 2, 9, 1]
4와 6과 2와 9와 1을 차례차례 비교합니다.
그 중 가장 작은 1과 맨 앞 자리인 4를 교체합니다!
[1, 6, 2, 9, 4] 이렇게요!
자, 그러면 이제 가장 작은 숫자인 1이 맨 앞으로 왔습니다.
가장 작은 걸 가장 맨 앞으로 옮기기로 했으니까요!
그러면, 맨 앞자리를 제외하고 다시 한 번 반복하면 됩니다.
2단계 : [1, 6, 2, 9, 4]
6과 2와 9와 4를 차례차례 비교합니다.
그 중 가장 작은 2와 두번째 앞 자리인 6을 교체합니다!
[1, 2, 6, 9, 4] 이렇게요!
3단계 : [1, 2, 6, 9, 4]
6과 9와 4를 차례차례 비교합니다.
그 중 가장 작은 4와 세번째 앞 자리인 6을 교체합니다!
[1, 2, 4, 9, 6] 이렇게요!
4단계 : [1, 2, 4, 9, 6]
9와 6을 비교합니다!
그 중 가장 작은 6과 네번째 앞 자리인 9을 교체합니다!
[1, 2, 4, 6, 9] 이렇게요!
버블 정렬보다 훨씬 더 적은 비교를 하는 것 같지만,
실제로는 각 배열을 계속해서 탐색하는 방식이라 2중 반복문을 사용해야 합니다!삽입 정렬(InsertionSort)
def insertionsort(lst):
for cur in range(1,len(lst)):
for delta in range(1,cur+1):
cmp = cur - delta
if lst[cmp]>lst[cmp+1]:
lst[cmp],lst[cmp+1]=lst[cmp+1],lst[cmp]
print(lst)
else:
break
return lst[4, 6, 2, 9, 1] # 정렬되지 않은 배열
1단계 : [4, 6, 2, 9, 1]
4는 현재 정렬되어 있는 부대원입니다.
그럼 이제 새로운 신병인 6을 받습니다.
4, 6 이 되는데 4 < 6 이므로 그대로 냅둡니다.
[4, 6, 2, 9, 1] 이렇게요!
자, 그러면 이제 한 바퀴를 돌렸죠?
이 과정에서 새로운 부대원인 4, 6은 현재 정렬된 상태입니다!
이처럼, 삽입 정렬은 한 바퀴가 돌 때마다 정렬된 상태가 됩니다.
끝까지 한 번 반복해볼게요!
2단계 : [4, 6, 2, 9, 1]
4, 6 은 현재 정렬되어 있는 부대원입니다.
그럼 이제 새로운 신병인 2를 받습니다.
4, 6, 2 가 되는데 6 > 2 이므로 둘을 변경합니다!
4, 2, 6 가 되는데 4 > 2 이므로 둘을 변경합니다!
[2, 4, 6, 9, 1] 이렇게요!
3단계 : [2, 4, 6, 9, 1]
2, 4, 6 은 현재 정렬되어 있는 부대원입니다.
그럼 이제 새로운 신병인 9를 받습니다.
2, 4, 6, 9 가 되는데 6 < 9 이므로 그대로 냅둡니다.
[2, 4, 6, 9, 1] 이렇게요!
4단계 : [2, 4, 6, 9, 1]
2, 4, 6, 9 은 현재 정렬되어 있는 부대원입니다.
그럼 이제 새로운 신병인 1을 받습니다.
2, 4, 6, 9, 1 가 되는데 9 > 1 이므로 둘을 변경합니다!
2, 4, 6, 1, 9 가 되는데 6 > 1 이므로 둘을 변경합니다!
2, 4, 1, 6, 9 가 되는데 4 > 1 이므로 둘을 변경합니다!
2, 1, 4, 6, 9 가 되는데 2 > 1 이므로 둘을 변경합니다!
[1, 2, 4, 6, 9] 이렇게요!