정렬 1 - 선택 정렬, 버블 정렬, 삽입 정렬
29 Oct 2019선택 정렬(Selection Sort)
선택 정렬은 리스트에서 가장 작거나 큰 항목을 찾아서 찾아서 첫 번째 항목과 위치를 바꾼다. 그 다음은 해당 항목을 찾아 두번째 항목과 바꾸며 리스트의 끝까지 과정을 반복한다. 선택 정렬은 이미 정렬되어 있는 경우에도 시간 복잡도는 O(n²)이다.
예제
def selection_sort(seq):
length = len(seq)
for i in range(length-1):
min_j = i
for j in range(i+1, length):
if seq[min_j] > seq[j]:
min_j = j
seq[i], seq[min_j] = seq[min_j], seq[i]
return seq
버블 정렬(Bubble Sort)
버블 정렬은 인접한 두 항목을 비교하며 정렬한다. 시간 복잡도는 선택 정렬과 마찬가지로 O(n²)으로 구현은 간단하지만 매우 비효율적인 알고리즘이다.
예제
def bubble_sort(seq):
length = len(seq) - 1
for num in range(length, 0, -1) :
for i in range(num):
if seq[i] > seq[i+1]:
seq[i], seq[i+1] = seq[i+1], seq[i]
return seq
def bubble_sort2(seq):
length = len(seq) - 1
for i in range(length):
for j in range(length-i):
if seq[j] > seq[j+1]:
seq[j], seq[j+1] = seq[j+1], seq[j]
return seq
삽입 정렬(Insertion Sort)
삽입 정렬은 첫번째 항목을 두번째 항목과 비교한 후 정렬한다. 그 이후의 값은 정렬된 부분에 크기를 비교하여 삽입한다. 최선의 경우 시간 복잡도는 O(n)이고 평균과 최악의 경우는 O(n²)이다. 데이터 크기가 작거나 리스트가 이미 정려로디어 있으면 고급 알고리즘보다 성능이 더 좋을 수 있다.
예제
def insertion_sort(seq):
for i in range(1, len(seq)):
j = i
while j > 0 and seq[j-1] > seq[j]:
seq[j-1], seq[j] = seq[j], seq[j-1]
j -= 1
return seq
참조
모두의 알고리즘 with 파이썬