2019.07.03 TIL
(TIL은 스스로 이해한 것을 바탕으로 정리한 것으로 오류가 있을 수 있습니다)
# 질문에 답하기
정렬 O(n2) - 그나마 제일 좋은것은 insertion이 제일 좋다.
- 버블솔트
- 삽입정렬
- 선택정렬
1. 버블 솔트
- 일반적으로 for문이 2개면 n2이다.
def bubble_sort(arr):
n = len(arr)
for i in range(n-1):
for j in range(n-1-i):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
if __name__ == "__main__":
arr = [7, 2, 5, 12, 6]
bubble_sort(arr)
print(arr)
2. 삽입 정렬
- [5, 2, 6, 1, 8]
- 첫 번째 인덱스는 지나가고 2번 째 인덱스부터 temp에 넣어서 그 숫자를 첫 번째 인덱스부터 비교한다.
- i를 temp에 넣고, j는 i-1부터 인덱스를 줄여가며 temp와 비교한다. i의 앞쪽은 정렬되어 있을 것이기 때문에 그 해당 위치에 insert를 하는 것이기 때문에 insertion이다.
- insertion은 끝까지 다 비교하지 않아도 되기 때문에 bubble_sort보다 더 효율적이다.
while문을 통한 구현
def insertion_sort(arr):
n = len(arr)
for i in range(1, n):
temp = arr[i]
j = i - 1
while j!=-1:
if arr[j] > temp:
arr[j+1] = arr[j]
j-=1
else:
break
arr[j+1] = temp
if __name__ == "__main__":
arr = [7, 2, 5, 12, 6]
insertion_sort(arr)
print(arr)
for문을 통한 구현
def insertion_sort(li):
n=len(li)
temp=None
for i in range(1, n):
temp=li[i]
for j in range(i-1, -2, -1): #-2까지 해야지 -1까지 된다.
if j==-1:
break
if li[j] > temp:
li[j+1]=li[j]
else:
break
li[j+1]=temp
if __name__ == "__main__":
arr = [7, 2, 5, 12, 6]
insertion_sort(arr)
print(arr)
선택 정렬(selection)
- 첫 번째 인덱스에 적합한 가장 작은 값을 선택한다.
- 그리고 해당 인덱스를 첫 번째 인덱스와 바꾼다.
- i를 0부터 시작해서 일단 첫 번째 인덱스를 가장 작은 값으로 가정하고 시작
- 바깥 포문은 제일 마지막꺼 전 까지만 돌면 되므로 n-2까지
- 안 쪽 포문은 i+1부터 n-1(끝까지)
def selection_sort(arr):
n = len(arr)
for i in range(0, n-1):
min_idx = i
for j in range(i+1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
if __name__ == "__main__":
arr = [7, 2, 5, 12, 6]
selection_sort(arr)
print(arr)