[이론] 정렬

 

선택정렬

: 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고 , 그 다음 작은 데이터를 선택해앞에서 두번째 데이터와 바꾸는 과정을 반복

- 가장 작은 것을 선택한다 는 의미에서 선택 정렬 

- N-1번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 된다

 : N +(N-1) + .. + 2 -> (N)(N+1)/2 

 => O(n^2)

- 10000 개 이상의 데이터 부터 급격히 늦어짐

#선택정렬
#
import sys
sys.stdin = open("input.txt","r")
arr = [7,5,9,0,3,1,6,2,4,8]

for i in range(len(arr)):
    min_index=i #가장 작은 원소의 인덱스
    for j in range(i+1,len(arr)):
        if arr[min_index]>arr[j]: #작은 원소의 인덱스를 찾아서
            min_index=j #인덱스를 저장하고
    arr[i],arr[min_index]=arr[min_index],arr[i] #가장 작은수와 현재 가장 작은 원소의 인덱스 원소와 바꿈 
print(arr)

 

 

삽입정렬

: 데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입한다

- 선택정렬에 비해 구현 난이도가 높지만 실행 시간 측면에서 효율적임

- 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬 되어 있을 때 훨씬 효율적

- 삽입정렬은 두번째 데이터부터 시작함, 첫번째 데이터는 그 자체로 정렬되어 있다고 생각하기 때문

- O(n^2)

- 최선의 경우, O(n) : 데이터가 거의 정렬되어 있는 상태일 경우 

 

#삽입정렬
#
import sys
sys.stdin = open("input.txt","r")
arr = [7,5,9,0,3,1,6,2,4,8]

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)

 

퀵정렬

: 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸면 어떨까?

- 빠른 정렬 알고리즘 

- O(NlogN)

- 최악의 경우, O(n^2) ,리스트의 가장 왼쪽 데이터를 피벗으로 삼을 때, 이미 데이터가 정렬되어 있는 경우 느리게 동작

 

맨 오른쪽 pivot으로 하는 경우 퀵소트

-맨 오른쪽을 pivot으로 하는 코드

#퀵정렬 - 맨 오른쪽 pivot
#
import sys

def Qsort(lt,rt):
    if lt<rt:
        pos=lt
        pivot=arr[rt]
        for i in range(lt,rt):
            if arr[i]<=pivot:
                arr[i],arr[pos]=arr[pos],arr[i]
                pos+=1
        arr[rt], arr[pos] = arr[pos], arr[rt]
        Qsort(lt,pos-1)
        Qsort(pos+1,rt)

if __name__ == "__main__":
    arr=[45,21,23,36,15,67,11,60,20,33]
    print("Before sort: ",end=' ')
    print(arr)
    Qsort(0,9)
    print("After sort: ", end=' ')
    print(arr)

 

- 맨 왼쪽을 pivot - 파이썬장점 이용한 코드

#퀵정렬 - 파이썬의 장점이용
#
import sys
sys.stdin = open("input.txt","r")
arr = [5,7,9,0,3,1,6,2,4,8]

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

 

- 맨 왼쪽을 pivot 

#퀵 정렬
#
import sys
sys.stdin = open("input.txt","r")
arr = [5,7,9,0,3,1,6,2,4,8]

def quick_sort(arr,start,end):
    if start>=end: #원소가 1개인 경우 종료
        return
    pivot = start #피벗은 첫번째 우너소
    left = start+1
    right = end
    while left<=right:
        #피벗보다 큰 데이터를 찾을 때까지 반복
        while left<= end and arr[left]<=arr[pivot]:
            left+=1
        #피벗보다 작은 데이터를 찾을 때까지 반복
        while right>start and arr[right] >= arr[pivot]:
            right-=1
        if left > right : #엇갈렸으면 작은 right-=1 데이터와 피벗을 교체
            arr[right],arr[pivot] = arr[pivot],arr[right]
        else: #엇갈리지 않으면 작은 데이터와 큰 데이터 교체
            arr[left],arr[right]=arr[right],arr[left]
    #분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬
    quick_sort(arr,start,right-1)
    quick_sort(arr,right+1,end)

quick_sort(arr,0,len(arr)-1)
print(arr)

 

계수 정렬(Count Sort)

: 특정한 조건이 부합할 때만 사용할 수 있으나 매우 빠른 정렬 알고리즘 

- 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용 가능

- 가장 큰 데이터와 가장 작은 데이터 차이가 1,000,000 을 넘지 않을 떄 효과적

- 데이터의 크기가 한정되어 있고, 데이터의 크기가 많이 중복되어 있을수록 유리하며 항상 사용할 수 없음

- 가장 큰 데이터와 가장 작은 데이터의 차이가 너무 크면 계수 정렬을 사용할 수 없다.

- 계수정렬은 모든 범위를 담을 수 있는 크기의 리스트를 선언해야한다

- 데이터의 개수가 N, 데이터 중 최대값이 K일 때, 최악의 경우에도 O(N+K) 보장

1) 먼저 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트 생성 -> 우리가 정렬할 데이터의 범위가 리스트의 인덱스가 모든 범위를 포함할 수 있도록 함 

2) 결과적으로 리스트에는 각 데이터가 몇번 등장했는지 그 횟수가 기록됨

3) 리스트의 첫번째 데이터부터 하나씩 그 값만큼 인덱스를 출력하면 됨 

 

#계수 정렬
#
import sys
sys.stdin = open("input.txt","r")

#모든 원소의 값이 0보다 크거나 같다고 가정
arr = [7,5,9,0,3,1,6,2,9,1,4,8,0,5,2]
cnt = [0]*(max(arr)+1)

for i in range(len(arr)):
    cnt[arr[i]]+=1 #각 데이터에 해당하는 인덱스의 값 증가

for i in range(len(cnt)):
    for j in range(cnt[i]):
        print(i,end=' ')

 

파이썬의 정렬 라이브러리

- sorted() : 퀵 정렬과 동작 방식이 비슷한 병합 정렬 기반, 일반적으로 퀵정렬보다 느리지만 최악의 경우에도 O(NlogN) 보장

- arr.sort() : 리스트 객제의 내장함수 sort()

 

*코딩테스트에서 정렬 알고리즘 사용되는 경우

1. 정렬 라이브러리로 풀 수 있는 문제

2. 정렬 알고리즘의 원리에 대해서 물어보는 문제 : 선택,삽입,퀵 정렬 등의 원리를 알고 있어야함

3. 더 빠른 정렬이 필요한 문제 : 퀵 정렬 기반의 정렬 기법으로는 풀 수없으며 계수 정렬 등의 다른 정렬 알고리즘 이용 

 

정렬 알고리즘	핵심 아이디어
선택 정렬	가장 작은 데이터를 '선택' 해서 정렬되지 않은 데이터 중에서 가장 앞쪽에 있는 데이터와 위치를 바꾸는 방법
삽입 정렬	데이터를 앞에서부터 하나씩 확인하며 데이터를 적절한 위치에 '삽입'하는 방법
퀵 정렬	기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법
계수 정렬	특정한 값을 가지는 데이터의 개수를 '카운트'하는 방법

정렬 알고리즘	평균 시간 복잡도	공간 복잡도	특징
선택 정렬	O(N^2)	O(N)	아이디어가 매우 간단
삽입 정렬	O(N^2)	O(N)	데이터가 거의 정렬되어 있을 때 가장 빠르다
퀵 정렬	O(NlogN)	O(N)	대부분의 경우에 가장 적합, 충분히 빠르다
계수정렬	O(N+K)	O(N+K)	데이터의 크기가 한정되어 있는 경우에만 사용가능, 매우빠르다