_05.algorithm_sort

정렬 알고리즘

• 정렬(sorting)이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것
• 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용

1. 선택 정렬

• 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복
• 탐색(선형 탐색) 범위는 반복할 때 마다 작아진다

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] # swap

print(array)
# [0,1,2,3,4,5,6,7,8,9]

2. 삽입 정렬

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

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

for i in range(1, len(array)): # 두번째 원소인 1부터 
    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

print(array)
# [0,1,2,3,4,5,6,7,8,9]

3. 퀵 정렬

• 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법
• 일반적인 상황에서 가장 많이 사용
• 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘
• 가장 기본적인 퀵 정렬은 첫번째 데이터를 기준 데이터(Pivot)로 설정
• Pivot, 첫번째 데이터를 기준으로 데이터 왼쪽부터 Pivot보다 큰 데이터를 선택하고 데이터 오른쪽부터 Pivot보다 작은 데이터를 선택하여 swap한다. 반복.
• 왼쪽에서부터 오는데이터와 오른쪽에서부터 오는 데이터가 위치가 엇갈리는 경우 pivot과 작은 데이터의 위치를 변경
• 위 상황에서 pivot을 기준으로 왼쪽은 작은값 오른쪽은 큰값을 가지게 되며
• 피벗을 기준으로 데이터 묶음을 나누는 작업을 분할(DIvide)라고 함
• 피벗을 기준으로 왼쪽 오른쪽으로 나뉘어 각각 정렬을 수행

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

def quick_sort(array, start, end):
    if start >= end: # 원소가 1개인 경우 종료
        return
    pivot = start # 피벗은 첫 번째 원소
    left = start + 1
    right = end
    while(left <= right):
        # 피벗보다 큰 데이터를 찾을 때까지 반복
        while(left <= end and array[left] <= array[pivot]):
            left += 1
        # 피벗보다 작은 데이터를 찾을 때까지 반복
        while(right > start and array[right] >= array[pivot]):
            right -= 1
        if (left > right): # 엇갈렸다면 작은 데이터와 피벗을 교체
            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)
print(array)
# [0,1,2,3,4,5,6,7,8,9]

퀵 정렬 파이썬의 장점을 살린 방식

array = [5,7,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))
 # [0,1,2,3,4,5,6,7,8,9]   

4. 계수 정렬

• 특정 조건일 때만 사용 가능하나, 매우 빠름
• 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용가능
  1. 가장 작은 데이터부터 가장 큰 데이터까지의 범위가 모두 담길 수 있도록 리스트를 생성
  2. 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시킨다
  3. 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시킨다
  4. 반복
  5. 결과적으로 최종 리스트에는 각 데이터가 몇 번씩 등장했는지 그 횟수가 기록됨
  6. 결과를 확인할 때는 리스트의 첫 번째 데이터부터 하나씩 그 값만큼 반복하여 인덱스를 출력하면됨

# 모든 원소의 값이 0보다 크거나 같다고 가정
array = [7,5,9,0,3,1,6,2,9,1,4,8,0,5,2]
# 모든 범위를 포함하는 리스트 선언(모든 값은 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=' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력

# 001122345567899

문제. 두 배열의 원소 교체: 문제 조건

입력조건

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

출력조건

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

---

• 핵심 아이디어: 매번 배열 A에서 가장 작은 원소를 골라서, 배열 B에서 가장 큰 원소와 교체
• 가장 먼저 배열 A와 B가 주어지면 A에 대하여 오름차순 정렬하고, B에 대해 내림차순 정렬
• 이후, 두 배열의 원소를 첫 번째 인덱스부터 차례로 확인하면서 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() # 오름차순 정렬 수행
b.sort(rever=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)) # 배열 A의 모든 원소의 합을 출력