[Algorithm] 정렬 방법, 구현(선택, 버블, 삽입, 병렬, 퀵, 계수)

정렬에 대해 공부를 해서 이에 대한 기록을 하려고 한다.

본 글의 정렬은 오름차순을 기본으로 한다.
내림차순은 파이썬에 내장된 reverse 메서드를 사용하면 쉽게 구현할 수 있다.

선택 정렬

선택 정렬은 가장 작은 수나 큰 수를 선택해 우선적으로 정렬시키는 방법이다.

• 위의 그림처럼 가장 큰 수를 계속해서 찾아가는 식의 방법이다.
• 코드는 매번 작은 수를 찾아서 왼쪽에 배치하는 방법을 사용했다.

def SelectionSort(A):
    for i in range(1,len(A)):
        minIdx=i
        for j in range(i,len(A)):
            if A[j]<A[i]:
                minIdx=j
        A[i],A[minIdx]=A[minIdx],A[i]
    return A

• 시간 복잡도
  • 이중 for 문을 사용하기 때문에 O(N**2)으로 가장 오래 걸리는 정렬 방법이다.

Swap Code

두 수를 바꾸는 swap을 파이썬에서는 쉽게 구현할 수 있다.
위 코드에서도 나와있다.

a와 b의 값을 바꾸려면
a,b=b,a

버블 정렬

현재 원소의 값과 다음 원소의 값을 계속 비교하며 가장 큰 값을 찾아내는 방법이다.

• 위의 그림처럼 인접한 두 수의 비교를 통해 큰 값을 맨 뒤로 계속 보내는 방법이다.

def BubbleSort(A):
    for i in range(len(A)-1,1,-1):
        for j in range(1,i):
            if A[j]>A[j+1]:
                A[j],A[j+1]=A[j+1],A[j]
    return A

• 시간 복잡도
  • 선택 정렬과 마찬가지로 이중 for문을 사용하기 때문에 O(N**2)의 시간 복잡도를 가진다.

삽입 정렬

원소 하나하나를 보고, 원소 앞 배열은 모두 정렬되어 있다고 가정하고 알맞은 위치에 원소를 배치하는 방법이다.

• 처음에는 맨 앞 원소만을 정렬되었다고 가정하고 진행한다.
• 두 번째 원소부터 끝 원소까지 본인의 자리를 찾아주는 정렬법이다.

def insertionsort(A):
    for i in range(1,len(A)):
        for j in range(i,0,-1):
            if A[j]<A[j-1]:
                A[j],A[j-1]=A[j-1],A[j]
            else:
                break
    return A

• 시간 복잡도
  • 최선의 경우에는 O(N)의 시간 복잡도를 가진다.
  • 이중 for문을 사용하기 때문에 보통의 경우에는 O(N**2)의 시간 복잡도를 가진다.

병합 정렬

주어진 배열을 재귀적으로 이등분하여 정렬하고, 병합하는 정렬 방법이다.

• 위 그림의 과정을 재귀적으로 원소 하나 하나로 나뉠 때까지 분할하고 정렬, 병합한다.

def mergesort(arr):
    def sort(low,high):
        if high-low<2:
            return
        mid=(high+low)//2
        sort(low,mid)
        sort(mid,high)
        merge(low,mid,high)
        return arr
    def merge(low,mid,high):
        tmp=[]
        l,h=low,mid
        while l<mid and h<high:
            if arr[l]<arr[h]:
                tmp.append(arr[l])
                l+=1
            else:
                tmp.append(arr[h])
                h+=1
        while l<mid:
            tmp.append(arr[l])
            l+=1
        while h<high:
            tmp.append(arr[h])
            h+=1
        for i in range(low,high):
            arr[i]=tmp[i-low]
    return sort(0,len(arr))

• 시간 복잡도
  • 병합 정렬은 모든 경우에서 O(NlogN)의 시간 복잡도를 가진다.

퀵 정렬

퀵 정렬에서는 'pivot'을 사용한 비교를 통해 정렬하는 방법이다.
3단계를 재귀적으로 반복한다.

1단계) 첫 번째 원소를 pivot으로 설정하고
왼쪽은 pivot보다 작은 원소, 오른쪽은 pivot보다 큰 원소가 오도록 한다.

2단계) 왼쪽 인덱스가 오른쪽 인덱스보다 커지면 왼쪽 인덱스와 pivot의 위치를 바꾼다.

3단계) 분할이 완료되었다. 왼쪽에는 pivot보다 작은 원소, 오른쪽에는 pivot보다 큰 원소가 있을 것이다.
두 그룹에 대해 지금까지의 과정을 재귀적으로 반복한다.

재귀의 정지 조건은 그룹에 원소가 하나밖에 남지 않았을 때이다.

 

• 위의 그림에서는 pivot을 마지막 원소로 설정했지만, 코드에서는 첫 번째 원소로 설정했다.

def quicksort(A,start,end):
    if start>=end:
        return
    pivot=start
    left=start+1
    right=end
    while left<=right:
        while left<=end and A[left]<=A[pivot]:
            left+=1
        while right>start and A[right]>=A[pivot]:
            right-=1
        if left>right:
            A[pivot], A[right] = A[right], A[pivot]
        else:
            A[right],A[left]=A[left],A[right]
    quicksort(A,start,right-1)
    quicksort(A,right+1,end)

• 시간 복잡도
  • 퀵 정렬의 시간 복잡도는 평균적으로 O(NlogN)이지만, 최악의 경우 O(N**2)이다.

계수 정렬

원소의 값을 인덱스로 하는 배열을 추가로 생성해서,
해당 원소 값의 개수를 배열의 값으로 저장하는 방법이다.

def countsort(A):
    count=[0]*(max(A)+1)
    returnArr=[0]*len(A)
    idx=0
    for i in range(len(A)):
        count[A[i]]+=1
    for i in range(len(count)):
        for j in range(count[i]):
            returnArr[idx]=i
            idx+=1
    return returnArr

• 시간 복잡도
  • 계수 정렬의 시간 복잡도는 O(N)이지만, 데이터의 개수가 한정적인 정수 개수일 때 효과적인 정렬방법이다.