[자료구조] sorting1 - bubble sort, selection sort, insertion sort (개념 및python 실습)
sorting 개념&실습(python) 시리즈😊
sorting 2 - mergesort, quicksort, heapsort
sorting 3 - counting sort, radix sort, topological sort
- 저번 시간에는 시간복잡도가 최대 인 기본 정렬 알고리즘을 알아보았습니다. 조금 더 발전된 효율적인 sorting 알고리즘을 알아봅시다.
1. Bubble Sort
- 자주 이용되지는 않음
- 이해하기 쉬움
- n, n+1 번째 index를 각각 비교하면서 설정
1st cycle
[https://dev.to/buurzx/buble-sort-4jkc]
해당 cycle 반복
-
cycle 반복때마다 맨 뒤 값은 하나씩 정렬 완료됨
-
최악의 경우 모든 item을 swap 해야함!
Code😘
lis = [9,6,7,3,5]
for m in range(len(lis)-1 , 0, -1):
for n in range(m):
if lis[n]>lis[n+1]:
temp=lis[n]
lis[n]=lis[n+1]
lis[n+1]=temp
# lis[n],lis[n+1] = lis[n+1],lis[n] #pythonic 한 코드
print(lis)
# print(lis)
print(sorted_lis==lis)
>>>
[6, 7, 3, 5, 9]
[6, 3, 5, 7, 9]
[3, 5, 6, 7, 9]
[3, 5, 6, 7, 9]
True
additional optimization
- 앞뒤 자리 비교가 있었던 index를 기억해두면 다음 패스에서는 그 자리 전까지만 정렬해도 됨
- 다시말해 바뀐 지점까지는 다시 연산을 안하도록 세팅
def bubble_sort(arr):
end = len(arr)-1
while end>0 :
last_swap = 0
for n in range(end):
if arr[n]> arr[n+1]:
temp = arr[n]
arr[n] = arr[n+1]
arr[n+1] = temp
last_swap = n
end = last_swap
Time Complexity
-> not good!
2. Selection Sort
[https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html]
- 최솟값 index 정보 저장 후 맨 앞 index와 swap
- swap 완료된 값은 제외하고 다른 값들로 순차적으로 진행
- 매 cycle마다 1번의 swap만 하면 됨
Code😘
lis = [9,6,7,3,5]
for i in range(len(lis)-1):
min_idx = i
for j in range(i+1,len(lis)):
if lis[j]<lis[min_idx]:
min_idx = j
lis[i],lis[min_idx] = lis[min_idx], lis[i]
print(lis)
print(lis==sorted_lis)
>>>
[3, 6, 7, 9, 5]
[3, 5, 7, 9, 6]
[3, 5, 6, 9, 7]
[3, 5, 6, 7, 9]
True
Time Complexity
also -> not good!
3. insertion Sort
[https://algopoolja.tistory.com/19]
- index 0 은 원래 정렬되어 있다고 가정
- index 1 부터 왼쪽에 더 큰수가 있는지를 확인
- 클경우 swap
- index 2, 3로 진행하면서 왼쪽에 더 큰수가 있을 경우 index 0 까지 swappng 가능
장점
- 필요한 아이템만 스캔하기 때문에 시간이 덜걸림
Code😘
lis = [9,6,7,3,5]
for end in range(1,len(lis)):
for i in range(end,0,-1):
if lis[i-1]>lis[i]:
lis[i-1], lis[i] = lis[i], lis[i-1]
print(lis)
print(sorted_lis==lis)
>>>
[3, 6, 7, 9, 5]
[3, 5, 7, 9, 6]
[3, 5, 6, 9, 7]
[3, 5, 6, 7, 9]
True
>>>
[6, 9, 7, 3, 5]
[6, 7, 9, 3, 5]
[6, 7, 9, 3, 5]
[6, 7, 3, 9, 5]
[6, 3, 7, 9, 5]
[3, 6, 7, 9, 5]
[3, 6, 7, 5, 9]
[3, 6, 5, 7, 9]
[3, 5, 6, 7, 9]
[3, 5, 6, 7, 9]
True
Time Complexity
- best :
- worst :
정리😘
- 잘 쓰이지는 않음
- 쉬운 알고리즘이고 sorting의 고전 알고리즘
Author And Source
이 문제에 관하여([자료구조] sorting1 - bubble sort, selection sort, insertion sort (개념 및python 실습)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@crosstar1228/자료구조-Sorting1bubble-sort-selection-sort-insertion-sort저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)