➕ 나동빈님 이코테에서 들은 내용을 기반으로 정리하고 공부한 게시글입니다.

✔ 정렬이란?

정렬(sorting)이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것이다.

◾ 선택정렬

: 처리되지 않은 데이터 중에서 가장 작은 데이터를 처리되지 않은 원소들의 맨 앞과 바꾸는 것을 반복한다.

👉 문제해결과정

if) array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]를 오름차순으로 정렬하라.
1. 7을 선택하고 [5, 9, 0, 3, 1, 6, 2, 4, 8] 중에서 가장 작은 수를 선택해 7과 위치를 바꾼다.
2. [0, 5, 9, 7, 3, 1, 6, 2, 4, 8]중에서 5을 선택하고 [9, 7, 3, 1, 6, 2, 4, 8] 중에서 가장 작은 수를 선택해 5과 위치를 바꾼다.
3. 마지막 두개의 원소가 자리를 바꿀때까지(N-1번 수행될때까지) 1,2번 과정을 반복한다.

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] #파이썬에서 지원되는 방식

print(array)

👉 시간복잡도

원소가 N개일 때, N번 만큼 가장 작은 수를 찾아서 앞으로 보내야 하기 때문에 전체 연산 횟수는 N+(N-1)+(N-1)+...+2 = (N^+N-2)/2이다.
빅오 최고차항만을 고려하기 때문에 O(N^)이다.

◾ 삽입정렬

: 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다. 선택정렬에 비해 효율적이다.

👉 문제해결과정

두번째 데이터부터 시작하여 그 앞에 있는 데이터들의 왼/오 중에 어디에 들어갈지 판단한다.
if) array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]를 오름차순으로 정렬하라.
1. [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]에서 두번재 데이터 5가 그 앞에 있는 데이터 7의 왼/오 중에 어디에 들어갈지 판단한다.
2. [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]에서 세번재 데이터 9가 그 앞에 있는 데이터 5,7의 왼/오 중에 어디에 들어갈지 판단한다.
3. 마지막 원소가 자리를 바꿀때까지 1,2번 과정을 반복한다.

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

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

👉 시간복잡도

시간 복잡도는 선택정렬과 마찬가지로 반복문이 두번 중첩되어 사용되었기에 O(N^)을 가진다.

◾ 퀵정렬

: 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다. 가장 기본적인 퀵정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정한다.

👉 문제해결과정

if) array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]를 오름차순으로 정렬하라.
1. [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]에서 기본으로 pivot=5 이다. 왼쪽에서부터 5보다 큰 데이터 4 선택, 오른쪽에서 5보다 작은 데이터 4선택해 두 데이터 위치 서로 변경한다.
2. [5, 4, 9, 0, 3, 1, 6, 2, 7, 8]에서 왼쪽에서부터 5보다 큰 데이터 9 선택, 오른쪽에서 5보다 작은 데이터 2를 선택해 두 데이터 위치 서로 변경한다.
3. 단, 왼/오 에서 선택한 데이터의 위치가 엇갈리는 경우, pivot과 작은데이터의 위치를 서로 변경한다.

4. pivot을 기준으로 왼쪽 데이터 묶음 / 오른쪽 데이터 묶음을 각각 하나의 배열로 판단해 위 과정을 반복한다.(재귀적)

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): # 엇갈렸다면(right 값이 left보다 작으면) 작은 데이터와 피벗을 교체
            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)

🔽파이썬의 리스트 컴프리헨션을 이용하면 파이썬에서 간결하게 코드를 짤 수 있다!

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))

👉 시간복잡도

-> 최악의 경우 분할이 이루어졌을 때 오른쪽 부분만 존재하기 때문에 다시 또 똑같은 분할을 수행해야해서 O(N^)을 가진다.

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

N개의 자연수 원소 구성된 배열 A, B가 있다. 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 바꿔치는 연산을 K번 수행해 배열 A의 모든 원소의 합이 최대가 되도록 하여라.

👉 문제해결과정

1. 배열 A를 오름차순, 배열 B를 내림차순 정렬한다.
2. 배열 A의 가장 작은 원소(I)를 선택해 배열 B에서 I보다 큰 수 중 제일 큰 원소와 교체한다.
3. 배열 A를 모두 돌때까지 2번과정을 반복한다.

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의 모든 원소의 합을 출력

🌱 결론

정렬에 따라 시간복잡도가 다르기 때문에 문제에서 주어진 시간 제한에 따라 적합한 정렬을 사용해야 한다.