참고 링크
버블 정렬(Buble Sort)
- 바로 뒤의 원소와 비교해 더 크다면 뒤로감
- 구현이 쉬운 만큼 성능이 좋지 않다
- 시간복잡도 O(n^2)
def bubbleSort(x):
length = len(x)-1
for i in range(length):
for j in range(length-i):
if x[j] > x[j+1]:
x[j], x[j+1] = x[j+1], x[j]
return x
선택 정렬(Selection Sort)
- 1번부터 끝까지 훑어서 가장 작은 것을 첫 번째, 그 다음에 2번째 부터 가장 작은 게 두 번째로 정렬
- 시간복잡도 O(n^2)
def selectionSort(x):
length = len(x)
for i in range(length-1):
for j in range(i+1, length):
if x[i] > x[j]:
x[i], x[j] = x[j], x[i]
return x
삽입 정렬(Insertion Sort)
- 하나씩 삽입해 나가는 형태의 정렬방식
- 특정 값에 대해서 그 값이 맞는 위치를 찾고 나머지 한칸 씩 밀어냄
- O(n^2) 정렬 알고리즘 중에서는 가장 빠른 형태
- 시간복잡도O(n^2)
def insertSort(x):
for i in range(1, len(x)):
j = i - 1
key = x[i]
while x[j] > key and j >= 0:
x[j+1] = x[j]
j = j - 1
x[j+1] = key
return x
