정렬

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

 

1. 선택 정렬

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

 

#직접 작성한 초기 코드
array=[7,5,9,0,3,1,6,2,4,8]

for i in range(len(array)-1):
    min_num=array[i]
    num=array[i+1]
    index=i+1
    for j in range(len(array)):
        
        if(j<i):
            continue
        
        if num>array[j]:
            index=j
            num=array[j]
        
    if min_num>num:
        array[index]=min_num
        array[i]=num
    
print(array)

#답안
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],aray[i] #스와프 코드

print(array)

 

➡️ 시간 복잡도
N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야한다.
구현 방식에 따라서 사소한 오차는 있을 수 있지만, 전체 연산 횟수는 다음과 같다.
N + (N-1) + (N-2) + ... +2 -> ( N^2 + N - 2 ) / 2
빅오 표기법에 따라서 O(N^2)라고 작성한다.

 

2. 삽입 정렬

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

- 구현 난이도가 높지만, 효율적으로 동작함.

 

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):
    	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. 퀵 정렬

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

- 일반적 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나이다.

- 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터로 설정한다.

- 이상적인 경우 분할이 절반씩 일어난다면 전체 연산 횟수로 O(N log N)을 기대할 수 있다. (평균)
하지만 최악의 경우 O(n^2)의 시간 복잡도를 가진다. (이미 정렬되어 있는 경우)

#직접 작성한 초기 코드
array=[7,5,9,0,3,1,6,2,4,8]

for i in range(len(array)-1):
    min_num=array[i]
    num=array[i+1]
    index=i+1
    for j in range(len(array)):
        
        if(j<i):
            continue
        
        if num>array[j]:
            index=j
            num=array[j]
        
    if min_num>num:
        array[index]=min_num
        array[i]=num
    
print(array)

#답안
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],aray[i] #스와프 코드

print(array)

 

4. 계수 정렬

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

- 데이터의 개수가 N, 데이터(양수) 중 최대값이 K일 때 최악의 경우에도 수행 시간 O(N+K)를 보장한다.

- 각각의 데이터가 몇번 나오는지 센다. 0과 999,999로 단 두개만 존재하는 경우 비효율성을 초래할 수도 있다.

- 동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적이다. ex. 성적

 

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

 

문제) 두 배열의 원소 교체

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

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

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

 

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

a.sort()
b.sort(reverse=True)

for i in range(k):
	if a[i]<b[i]:
    	a[i],b[i],b[i],a[i]
    else:
    	break
print(sum(a))

 

참고) 이것이 취업을 위한 코딩 테스트다 with 파이썬