정렬 알고리즘

정렬이란?

선택 정렬

처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복하여 정렬하는 방법

선택 정렬 동작 예시

이런 방식으로.. 쭉 쭉 정렬 된다.

선택 정렬 소스코드

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)

선택 정렬 시간복잡도

삽입정렬

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

삽입 정렬 동작 예시

이런 방식으로 진행된다.

삽입 정렬 소스코드

for i in range(1,len(arr)):
    for j in range(i,0,-1): 
        if arr[j]<arr[j-1]:
            arr[j],arr[j-1] = arr[j-1],arr[j]
        else :
            break 
print(arr)

삽입 정렬 시간복잡도

퀵 정렬

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

퀵 정렬 동작예시

이런 방식으로 정렬을 진행한다.

퀵 정렬이 빠른 이유 : 직관적인 이해

퀵 정렬 소스코드

파이썬의 장점을 살린 방식의 코드이다

def quick_sort(arr):
    if len(arr)<=1:
        return arr 
    pivot = arr[0]
    tail = arr[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(arr))

퀵 정렬 시간복잡도

계수 정렬

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

계수 정렬 동작예시

이처럼 해당 하는 값의 인덱스로 접근 하는 방식이다.

계수 정렬 소스코드

count = [0] * (max(arr)+1)
for i in range(len(arr)):
    count[arr[i]]+=1 

for i in range(len(count)):
    for j in range(count[i]):
        print(i,end=" ")

계수 정렬 시간복잡도

정렬 알고리즘 비교하기

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

걍.. 파이썬에서는 정렬할때 sort쓰는게 짱짱인듯?

정렬 예제

두 배열의 원소 교체

배열 A에서 가장 작은 원소와 배열 B에서 가장 큰 원소를 스왑해주면될것같다.

문제 해결 아이디어

답

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

뭐.. 정렬은 결국 sort~