2주차 알고리즘 주차(3)
🐭 이번 주는 뭐 했어?
정렬
알고리즘의 가장 중요한 주제인 정렬은 데이터를 순서대로 나열하는 방법을 의미합니다 정렬은 이진 탐색을 가능하게도 하고, 데이터를 조금 더 효율적으로 탐색할 수 있게 만들기 때문입니다 이번 포스팅에서는 정렬의 종류에는 어떤 것들이 있고 정렬마다 구현하는 방법에 대해 알아보겠습니다
버블 정렬
버블 정렬은 첫 번째 자료와 두 번째 자료와 검사해 조건에 맞게 위치를 변경하고 또 두 번째와 세 번째 자료와 검사하는 식으로 마지막까지 하나씩 교환하면서 자료를 정렬하는 방식입니다
버블 정렬 예시
[3,1,2,4] <= 정렬되지 않은 배열
1단계: [3,1,2,4]
1과 3을 비교하고 1 < 3 이기 때문에 1을 앞으로 보냅니다
[1,3,2,4]
2단계 : [1,3,2,4]
3과 2를 비교하고 2 < 3 이기 때문에 2를 앞으로 보냅니다
[1,2,3,4]
3단계 : [1,2,3,4]
3과 4를 비교하면 3 < 4 이기 때문에 그대로 둡니다
결과 : [1,2,3,4]
def bubblesort(lst):
# 최댓값을 구하는 알고리즘을 len(lst) - 1 만큼 반복한다.
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]
return lst
선택 정렬
선택 정렬은 모든 자료를 검사해 가장 작은 값을 찾고 맨 앞으로 보냅니다 그 담으로 작은 숫자를 찾고 가장 작은 값의 뒤로 옮깁니다 이 작업을 계속해 마지막으로 남은 자료까지 앞에 놔두면 작은 순서대로 자료가 완성됩니다
선택 정렬 예시
[3,1,2,4] <= 정렬되지 않은 배열
1단계: [3,1,2,4]
4개를 확인해 1이 제일 작은 것을 확인하고 1과 맨 앞자리 3과 교체합니다
[1,3,2,4]
2단계: [1,3,2,4]
맨 앞자리를 제외하고 나머지 3개를 확인해 가장 작은 값을 확인해 2와 그 다음 자리와
교체합니다
[1,2,3,4]
결과: [1,2,3,4]
def selectionsort(lst):
iters = len(lst) - 1
for iter in range(iters):
minimun = iter
for cur in range(iter + 1, len(lst)):
if lst[cur] < lst[minimun]:
minimun = cur
if minimun != iter:
lst[minimun], lst[iter] = lst[iter], lst[minimun]
return lst
삽입 정렬
삽입 정렬은 모든 상태를 확인하지 않고 미리 정렬된 자료는 놔두고 변경이 필요한 자료만 비교해 필요할 때만 값을 비교해 위치를 변경하므로 더 효율적인 방식으로 사용 가능**합니다
삽입 정렬 예시
[3,1,2,4] <= 정렬되지 않은 배열
1단계: [3,1,2,4]
3이 정렬된 자료이고 그다음 자료를 확인합니다 1 < 3 이기 때문에 1을 앞으로 보냅니다
2단계: [1,3,2,4]
1,3이 정렬된 자료이고 그다음 자료 2를 확인합니다 2 < 3 이기 때문에 2를 앞으로 보냅니다
그렇지만 1 < 2 이기 때문에 놔둡니다
결과: [1,2,3,4]
정렬된 자료이기 때문에 더 이상 진행하지 않습니다
def insertionsort(lst):
# 0번째 요소는 이미 정렬되어있으니, 1번째 ~ lst(len)-1 번째를 정렬하면 된다.
for cur in range(1, len(lst)):
# 비교지점이 cur-1 ~ 0(=cur-cur)까지 내려간다.
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]
else:
break
return lst
def insertionsort_2(lst):
for idx in range(1, len(lst)):
val = lst[idx]
cmp = idx - 1
while lst[cmp] > val and cmp >= 0:
lst[cmp + 1] = lst[cmp]
cmp -= 1
lst[cmp + 1] = val
return lst
퀵소트
퀵소트는 분할 정복을 통해 주어진 배열을 정렬하는 알고리즘입니다 특정 기준을 잡고 기준보다
작은 값과 큰 값을 나누고 그사이에 기준에 맞게 이동시켜 정렬된 자료로 만듭니다
def quicksort(lst, start, end):
def partition(part, ps, pe):
pivot = part[pe]
i = ps - 1
for j in range(ps, pe):
if part[j] <= pivot:
i += 1
part[i], part[j] = part[j], part[i]
part[i + 1], part[pe] = part[pe], part[i + 1]
return i + 1
if start >= end:
return None
p = partition(lst, start, end)
quicksort(lst, start, p - 1)
quicksort(lst, p + 1, end)
return lst
Author And Source
이 문제에 관하여(2주차 알고리즘 주차(3)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jiho3894/항해99-2주차-알고리즘-주차3저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)