동빈나 2021 이코테_4. 정렬알고리즘

정렬이란? 데이터를 특정한 기준에 따라 순서대로 나열하는것

일반적으로 문제 상황에 따라 적절한 정렬 알고리즘이 공식처럼 사용됨

 

• 선택정렬 : 처리되지 않은 데이터 중 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는것을 반복
• 시간복잡도 : O(n^2)

 

• 삽입정렬(Insertion Sort) : 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입 ( 위치를 매번 계산해서 데이터를 넣어줌 / 정렬범위를 1칸씩 확장해나가면서 새롭게 정렬 범위에 들어온 값을 기존 값들과 비교하여 알맞은 자리에 꼽아주는 알고리즘
• 시간복잡도 : O(n^2)
• 선택정렬에 비해 난이도가 높지만 더 효율적으로 작동함, 특히 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작하여 최선의 경우 O(N)의 시간복잡도를 가진다.
• 0번째 인덱스는 이미 정렬되어있다고 생각하고 1번째 인덱스부터 시작 
• 외부반복문 : 정렬범위를 2에서 N으로 확대 , 내부반복문 : 정렬범위에 새롭게 추가된 값과 기존값들을 뒤에서부터 비교해나가면서 앞의값이 나보다 클경우 swap

 

 

• 퀵정렬 : 기준데이터(피벗_가장 첫번째 데이터로)를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는방법 
• 일반적상황에서 가장많이 사용되는 정렬 알고리즘임
• 병합정렬과 더불어 가장 근간이 되는 알고리즘
• 시간복잡도 : 평균적으로 O(NlogN)이 걸리고, 최악의 경우 O(N^2)이 걸린다. ( 피벗값에 따라 달라짐 )

이후 재귀적으로 퀵정렬을 수행하면 최종적으로 모두 정렬이 완료된다.

 

리스트 슬라이싱과 컴프리헨션을 이용해서 간결한 코드 작성가능 , 다만 메모리를 더 차지하게 됨

 

 

• 계수정렬 : 특정한 조건이 부합할때만 사용할 수 있지만 매우 빠르게 동작하는 알고리즘
• 계수정렬은 데이터의 크기범위가 제한되어 정수 형태로 표현할 수 있을때 사용가능하다
• 시간복잡도 : 최악의 경우에도 수행시간 O(N+K)를 보장함 ( N: 데이터개수, K:데이터(양수)중 최댓값 )

 

• 굳이 정렬을 직접 구현해야 하는것이 아니라면 라이브러리로 제공되는 정렬을 이용하자

 

< 예제문제1 > _ 두 배열의 원소교체

내코드

import time

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

start_time = time.time()

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


for i in range(k):
    if a[i] < b[i]:
        a[i] = b[i]
    
print(sum(a))
end_time = time.time()


print(end_time-start_time)

 동빈나님 코드