정렬 알고리즘이란?

선택 정렬

• 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복

'선택 정렬' 소스코드

arr = [7,5,9,0,3,1,6,2,4,8]

for i in range(len(arr)):
    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)

'선택 정렬' 시간복잡도

삽입 정렬

• 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입
• 선택정렬에 비해 구현 난이도가 높은 편이지만 일반적으로 더 효율적으로 동작

'삽입 정렬' 소스코드

arr = [7,5,9,0,3,1,6,2,4,8]

for i in range(1,len(arr)): 
    for j in range(i,0,-1): # 인덱스 i부터 1까지 감소하며 반복
        if arr[j] < arr[j-1]: # 한 칸씩 왼쪽으로 이동
            arr[j], arr[j-1] = arr[j-1], arr[j]
        else: # 자기보다 작은 데이터를 만나면 멈춤
            break
print(arr)

'삽입 정렬' 시간복잡도

퀵 정렬

• 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법
• 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나
• 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘
• 가장 기본적인 퀵 정렬은 첫번째 데이터를 기준 데이터(Pivot)로 설정

'퀵 정렬' 소스코드 1

arr = [5,7,9,0,3,1,6,2,4,8]

def quick_sort(arr,start,end):
    if start >= end: # 원소가 1개인 경우 종료
        return
    pivot = start # 피벗은 첫 번째 원소
    left = start + 1
    right = end

    while (left <= right):
        # 피벗보다 큰 데이터를 찾을 때까지 반복
        while (left <= end and arr[left] <= arr[pivot]):
            left += 1
        # 피벗보다 작은 데이터를 찾을 때까지 반복
        while (right > start and arr[right] >= arr[pivot]):
            right -= 1
        if (left > right): # 엇갈렸다면 작은 데이터와 피벗을 교체
            arr[right], arr[pivot] = arr[pivot], arr[right]
        else: # 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
            arr[left], arr[right] = arr[right], arr[left]
    # 분할 이휴 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    quick_sort(arr,start,right-1)
    quick_sort(arr,right+1,end)

quick_sort(arr,0,len(arr)-1)
print(arr)

'퀵 정렬' 소스코드 2

array = [5,7,9,0,3,1,6,2,4,8]

def quick_sort(arr):
    # 리스트가 하나 이하의 원소만을 담고 있다면 종료
    if len(arr) <= 1:
        return arr

    pivot = arr[0] # 피벗은 첫 번째 원소
    tail = arr[1:] # 피벗을 제외한 리스트

    left = [x for x in tail if x <= pivot]
    right= [x for x in tail if x > pivot]

    return quick_sort(left) + [pivot] + quick_sort(right)

print(quick_sort(array))

'퀵 정렬' 시간복잡도

계수 정렬

• 특정한 조건이 부합할 때만 사용할 수 있지만 빠르게 동작하는 정렬 알고리즘
  -> 계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능
• 데이터의 개수가 N, 데이터(양수) 중 최댓값이 K일 때 최약의 경우에도 수행시간 O(N+K)를 보장

'계수 정렬' 소스코드

# 모든 원소의 값이 0보다 크거나 같다고 가정
arr = [7,5,9,0,1,3,6,2,9,1,4,8,0,5,2]
# 모든 범위를 포함하는 리스트 선언(모든 값 0으로 초기화)
cnt = [0] * (max(arr)+1)

for i in range(len(arr)):
    cnt[arr[i]] += 1 # 각 데이터에 해당하는 인덱스 값 증가

for j in range(len(cnt)): # 리스트에 기록된 정렬 정보 확인
    for k in range(cnt[j]):
        print(j, end = ' ')

'계수 정렬' 시간 복잡도

정렬 알고리즘 비교

문제 1: 두 배열의 원소 교체

문제 풀이

n,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))

a.sort() # 오름차순 정렬
b.sort(reverse = True) # 내림차순 정렬

# 첫 번째 인덱스부터 확인 & 두 배열의 원소를 최대 k번 비교
for i in range(k):
    # a의 원소가 b의 원소보다 작은 경우
    if a[i] < b[i]: 
        # 두 원소를 교체
        a[i],b[i] = b[i], a[i] 
    else: # a의 원소가 b의 원소보다 크거나 같을 때 반복문 탈출
        break

print(sum(a))