정렬 알고리즘 (버블정렬, 카운팅 정렬, 선택정렬) - 파이썬 예시코드

 

 

버블정렬

인접한 숫자를 비교하여 큰 숫자를 뒤로 (혹은 앞으로) 보내는 정렬

 

arr = [3, 4, 1, 5, 1]

#리스트 전체 for문 돌리는 횟수
for i in range(len(arr), 0, -1):
    # 도는 범위를 전체길이의 1씩 감수시키며 둘씩 비교
    for j in range(1, i):
        if arr[j - 1] > arr[j]:
            arr[j - 1], arr[j] = arr[j], arr[j - 1]
print(arr)

 

 

 

카운팅 정렬

카운트 배열을 만들어, 리스트 안에 존재하는 숫자를 카운트하고 이를 이용하여 정렬

K = 5 # 숫자범위
A = [0, 5, 1, 2, 4, 3, 2, 1]
B = [0] * len(A)

#카운팅 배열 만들기
cnt = [0] * (K + 1)

# 리스트에 해당하는 수가 있을 때 카운팅 배열 1씩 증가
for val in A:
    cnt[val] += 1

#카운팅 배열의 누적합 구하기
for i in range(1, K + 1):
    cnt[i] += cnt[i - 1]

#누적합에서 1씩 줄이고, 해당하는 숫자 리스트 B에 추가
for i in range(len(A) - 1, -1, -1):
    cnt[A[i]] -= 1
    B[cnt[A[i]]] = A[i]

print(A)
print(B)

 

 

선택정렬

최솟값을 찾아 제일 앞에 차곡차곡 배열

arr = [9, 2, 10, 2, 5]

for i in range(len(arr) - 1):
    # 비교대상이 되는 값
    min_idx = i
    for j in range(i + 1, len(arr)):
        #최솟값을 찾는 식
        if arr[min_idx] > arr[j]:
            min_idx = j
    #최솟값과 비교대상이 되는 값 교환
    arr[i], arr[min_idx] = arr[min_idx], arr[i]

print(arr)