[정렬 알고리즘] 정렬(Sorting)

정렬(Sorting)

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

 

정렬 알고리즘의 종류

1) 선택 정렬

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

선택 정렬 소스코드 (Python)

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)

 

선택 정렬의 시간 복잡도

O(N^2) : N + (N - 1) + (N - 2) + ... + 2

 

2) 삽입 정렬

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

 

삽입 정렬 소스코드 (Python)

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
            
print(array)

 

삽입 정렬의 시간 복잡도

O(N^2) : 선택 정렬과 마찬가지로 반복문이 두 번 중첩되어 사용됨

O(N) : 최선의 경우로, 현재 리스트의 데이터가 거의 정렬되어 있는 상태에 매우 빠르게 동작

 

3) 퀵 정렬

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

 

 

퀵 정렬이 빠른 이유

이상적인 경우, 분할이 절반씩 일어난다면 전체 연산 횟수로 O(NlogN)을 기대할 수 있습니다.

 

퀵 정렬의 시간 복잡도

O(NlogN) : 평균의 경우

O(N^2) : 최악의 경우

 

퀵 정렬 소스코드 (Python)

# 1. 일반적인 방식
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)

# 2. 파이썬의 장점을 살린 방식
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))

 

4) 계수 정렬

특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘으로, 계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능합니다.

 

 

계수 정렬의 시간 복잡도

O(N + K) : 데이터의 개수가 N, 데이터(양수) 중 최댓값이 K일 때 최악의 경우에도 시간 복잡도 보장

-계수 정렬의 시간 복잡도와 공간 복잡도는 모두 O(N + K)로 동일합니다.

-계수 정렬은 0과 999,999로 단 2개의 데이터만 존재하는 경우와 같이 심각한 비효율성을 초래할 수 있습니다.

-계수 정렬은 동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적으로 사용할 수 있습니다. 예를 들면, 성적의 경우 100점을 맞은 학생이 여러 명일 수 있기 때문에 계수 정렬이 효과적입니다.

 

계수 정렬 소스코드 (Python)

# 모든 원소의 값이 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=' ')	# 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력

 

정렬 알고리즘 비교하기

대부분의 프로그래밍 언어에서 지원하는 표준 정렬 라이브러리는 최악의 경우에도 O(NlogN)을 보장하도록 설계되어 있습니다.

 

선택 정렬과 기본 정렬 라이브러리 수행 시간 비교

from random import randint
import time

# 배열에 10,000개의 정수를 삽입
array = []
for _ in range(10000):
	# 1부터 100 사이의 랜덤한 정수
    array.append(randint(1, 100))
    
# 선택 정렬 프로그램 성능 측정
start_time = time.time()

# 선택 정렬 프로그램 소스코드
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]
    
# 측정 종료
end_time = time.time()
# 수행 시간 출력
print("선택 정렬 성능 측정:", end_time - start_time)

# 배열을 다시 무작위 데이터로 초기화
array = []
for _ in range(10000):
	# 1부터 100 사이의 랜덤한 정수
    array.append(randint(1, 100))
    
# 기본 정렬 라이브러리 성능 측정
start_time = time.time()

# 기본 정렬 라이브러리 사용
array.sort()

# 측정 종료
end_time = time.time()
# 수행 시간 출력
print("기본 정렬 라이브러리 성능 측정:", end_time - start_time)

 

문제 : 두 배열의 원소 교체

<문제 설명>

-수진이는 두 개의 배열 A와 B를 가지고 있습니다. 두 배열은 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수입니다.

-수진이는 최대 K번의 바꿔치기 연산을 수행할 수 있는데, 바꿔치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는 것을 말합니다.

-수진이의 최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것이며, 여러분은 수진이를 도와야 합니다.

-N, K, 그리고 배열 A와 B의 정보가 주어졌을 때, 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력하는 프로그램을 작성하세요.

 

 

<문제 해결 아이디어>

-핵심 아이디어 : 매번 배열 A에서 가장 작은 원소를 골라서, 배열 B에서 가장 큰 원소와 교체

-가장 먼저 배열 A와 배열 B가 주어지면 A에 대하여 오름차순 정렬하고, B에 대하여 내림차순 정렬

-이후에 두 배열의 원소를 첫 번째 인덱스부터 차례로 확인하면서 A의 원소가 B의 원소보다 작을 때에만 교체를 수행

-이 문제에서는 두 배열의 원소가 최대 100,000개까지 입력될 수 있으므로, 최악의 경우 O(NlogN)을 보장하는 정렬 알고리즘을 이용해야 함

 

<소스코드>

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

 

 

출처: 이것이 취업을 위한 코딩 테스트다