정렬 알고리즘

정렬

데이터를 특정한 기준에 따라 순서대로 정렬

선택 정렬

가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복

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

for i in range(len(array)):
    min_index = i # 가장 작은 원소의 인덱스
    for j in range(i+1, len(array)):
        if array[min_index] > array[j]:
            min_index = j
    array[i], array[min_index] = array[min_index], array[i] # 스와프

삽입 정렬

처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입

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

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

퀵 정렬

기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법

1. 첫번째 데이터를 기준으로
2. 왼쪽에서 기준 보다 작은 수 선택
3. 오른쪽에서 기준 보다 큰 수 선택
4. 선택된 수 서로 위치 변경
5. 2~3 반복하며 범위가 겹칠때 작은 수와 기준 위치 변경 ( 분할 )
6. 바뀐 기준을 기준으로 왼쪽 묶음과 오른쪽 묶음으로 나눠 1~5를 재귀적으로 반복

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

def quick_sort(array, start, end):
    if start >= end: # 원소가 1개인 경우 종료
        return
    pivot = start # pivot는 첫번째 원소
    left = start + 1
    right = end
    while(left <= right):
        # pivot보다 큰 데이터를 찾을 때까지 반복
        while(left <= end and array[left] <= array[pivot]):
            left += 1
        # pivot보다 작은 데이터를 찾을때까지 반복
        while(right > start and array[right] >= array[pivot]):
            right -= 1
        if(left > right): # 엇갈렸다면 작은 데이터와 pivot을 교체
            array[right], array[pivot] = array[pivot], array[right]
        else:
            array[left], array[right] = array[right], array[left]
    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    quick_sort(array, start, right -1)
    quick_sort(array, right + 1, end)

quick_sort(array, 0, len(array) -1)

• list comprehension 기법 사용

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

def quick_sort(array):
    # 리스트가 하나 이하의 원소만을 담고 있다면 종료
    if len(array) <= 1:
        return array
    pivot = array[0] # 피벗은 첫번째 원소
    tail = array[1:] # 피벗을 제외한 리스트

    left_side = [ x for x in tail if x <= pivot ] # 분할된 왼쪽 부분
    right_side = [ x for x in tail if x > pivot ] # 분할된 오른쪽 부분

    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬을 수행하고 전체 리스트 반환
    return quick_sort(left_side) + [ pivot ] + quick_sort(right_side)

print(quick_sort(array))

계수 정렬

데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용

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

# 모든 범위를 포함하는 리스트 선언 (모든 값은 0으로 초기화)
count = [0] * (max(array)+1)

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

for i in range(len(count)): # 리스트에 기록된 정렬 정보 확인
    for j in range(count[i]):
        print(i, end=' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력

연습문제

두 배열의 원소 교체

• 동빈이는 두개의 배열 A와 B를 가지고 있습니다. 두 배열은 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수입니다.
• 동빈이는 최대 K번의 바꿔치기 연산을 수행할 수 있는데 바꿔치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는 것을 말합니다
• 동빈이의 최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것입니다.
• N, K, 그리고 배열 A, B의 정보가 주어졌을 때, 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력하는 프로그램을 작성하세요
• 예를 들어 N = 5, K = 3
  • 배열 A = [1, 2, 5, 4, 3]
  • 배열 B = [5, 5, 6, 6, 5]
• 이 경우 다음과 같이 3번의 연산 수행할 수 있습니다.
  • 연산 1) 배열 A의 원소 '1'과 배열 B의 원소 '6'을 바꾸기
  • 연산 2) 배열 A의 원소 '2'과 배열 B의 원소 '6'을 바꾸기
  • 연산 3) 배열 A의 원소 '3'과 배열 B의 원소 '5'을 바꾸기
• 세 번의 연산 이후 배열 A와 B는 다음과 같이 구성될 것입니다.
  • 배열 A = [6, 6, 5, 4, 5]
  • 배열 B = [3, 5, 1, 2, 5]
• 이때 배열 A의 모든 원소 합은 26이 되며 이보다 더 합을 크게 만들 수 없습니다.

입력조건

• 첫번째 줄에 N, K가 공백을 기준으로 구분되어 입력 ( 1 ≤ N ≤ 100,000 , 0 ≤ K ≤ N )
• 두번째 줄에 배열 A의 원소들이 공백을 기준으로 구분되어 입력됩니다. 모든 원소는 10,000,000보다 작은 자연수 입니다.
• 세번째 줄에 배열 B의 원소들이 공백을 기준으로 구분되어 입력됩니다. 모든 원소는 10,000,000보다 작은 자연수 입니다.

출력조건

• 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력합니다.

입력예시

5 3

1 2 5 4 3

5 5 6 6 5

출력예시

26

문제 풀이

핵심아이디어

매번 배열 A에서 가장 작은 원소를 골라서, 배열 B에서 가장 큰 원소와 교체

n, k = map(int, input().split()) # n,k를 입력 받기
a = list(map(int, input().split())) # 배열 A
b = list(map(int, input().split())) # 배열 B

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

# 첫번째 인덱스부터 확인하며, 두 배열의 원소를 최대 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)) # 배열 A의 모든 원소의 합 출력

참고

[한빛미디어] 이것이 취업을 위한 코딩 테스트다 with 파이썬 (나동빈 저)