정렬 알고리즘 (선택, 삽입, 병합, 퀵, 도수정렬)

정렬에 사용되는 다양한 알고리즘이 있다. 각 정렬은 특성과 원리 시간복잡도에 차이가 있다. 

(시간 복잡도에 관해서는 글 하단의 표 참고)

정렬 알고리즘에 대해 정리하고, 학습 이해에 도움이 되었던 유용한 시각자료를 포스팅하고자 한다.

 

 

선택정렬

• 배열의 가장 작은 요소를 가장 앞의 요소와 반복적으로 바꾸는 방법
• 선형 정렬이므로 전체 연산 횟수는  'N + (N-1) + (N-2) + ..... + 2' 이므로 전체 시간복잡도는 약 O(N2) 이다. 

##선택 정렬 (Python 구현 예시)  

arr = [17, 25, 49, 10, 23,  41, 6, 72, 4, 18]

for i in range(len(arr)):
	min_index = i   
    #가장 작은 원소의 index - 루프 시작 지점에서는 맨 앞의 원소의 인덱스를 사용한다. 루프가 돌면서 계속 update됨
    for j in range(i+1, len(arr)):
    	if arr[min_index] > arr[j]:
        min_index = j 
    arr[i], array[min_index] = arr[min_index], arr[i]
    
print(array)

---

삽입정렬

• 정렬되지 않은 배열에서, 2번째 숫자부터 왼쪽으로 스캔해가며 적절한 위치에 숫자 삽입한다.
• 선택정렬과 마찬가지로 반복문이 두번 중첩되어 사용되었으므로 시간복잡도는 N(2)이다. 

*하지만 만약에 리스트의 데이터가 '거의' 정렬되어있는 경우에는 매우 빠르게 정렬완료됨 O(N)수준! 

두번째 숫자인 array[1] 부터 시작해서 왼쪽으로 스캔하며 본인보다 작은 숫자를 찾는다. 스캔방향 (←)  

7

6

4

5

1

8

4

7

9

0

6

7

4

5

1

8

4

7

9

0

4

6

7

5

1

8

4

7

9

0

4

5

6

7

1

8

4

7

9

0

## 삽입 정렬 Python 구현 예시

arr = [17, 25, 49, 10, 23,  41, 6, 72, 4, 18]

for i in range(1, len(arr)):     #두 번째 숫자부터 스캔 시작
	for j in range(i, 0, -1):    #해당 숫자부터 한칸씩 왼쪽으로 이동해 가면서 찾음
    	if arr[j] < array[j-1]      #해당 숫자보다 왼쪽 숫자가 더 크면?
           arr[j], arr[j-1] = arr[j-1], arr[j]  #위치를 바꾼다 (앞뒤로 바꾸는 방식은 버블 정렬이랑 비슷함)
    	else:
    		break                   #해당숫자보다 작은숫자 만나면 멈춘다.
        
print(arr)

---

퀵 정렬

• 맨 앞의 요소를 피벗으로 삼아서 나머지 배열을 피벗보다 작은 배열, 큰 배열로 나눈다.
• 위 논리를 통해 나누어진 각각의 작은배열, 큰배열에서도 같은 방법을 반복한다. (재귀)
  이해가 어려울 경우 포스팅 하단의 시각자료 참고.
• 이름 값한다고 평균 시간복잡도가 O(NlogN)이라고 하는데, 특정배열에서는 O(N2)이다. 시간복잡도의 array dependency가 있음.

## 퀵 정렬 Python 구현 예시

arr = [17, 25, 49, 10, 23,  41, 6, 72, 4, 18]

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] #피벗보다 작은 요소 array
    right_side=[x for x in tail if x>pivot] #피벗보다 큰 요소 array
    
    return quick_sort(left_side) + [pivot] + quick_sort(right-side)
    
print(quick_sort(arr))

---

병합 정렬 (Merge sort)

• 병합 정렬의 경우 안정적으로 NlogN의 시간복잡도를 가지고 있다. 시간복잡도가 array에 따라 크게 변하지 않음.
  (안정적으로 빨라서 퀵 정렬과 더불어 특정 언어들의 표준라이브러리의 베이스 개념이 된다고 함)
• 기본 컨셉은 정렬되지 않은 배열을 절반으로 나눈 후 각각의 배열을 병합정렬한 후 맨 앞의 값들을 비교해가며 합병한다.....
  병합정렬을 위해 병합정렬을 한다는게 말이 이상해 보이지만 재귀의 개념을 이용하면 가능하다. 참고 이미지, 소스코드, 포스팅 하단의 애니매이션 참고하면 이해가 될 것

  

import sys              ##병합정렬 백준 수 정렬하기2
input=sys.stdin.readline

def merge_sort(arr):
    if len(arr)<=1:   #배열(array)의 요소가 1개일 경우 그대로 반환(재귀 탈출조건)
        return arr

    mid =len(arr)//2			#전체 배열 중간값 mid기준 반띵
    l = merge_sort(arr[:mid])   #정렬된 좌배열 (재귀) 
    r = merge_sort(arr[mid:])   #정렬된 우배열 (재귀)

    i,j,k=0,0,0
    								#i,j는 왼쪽 오른쪽꺼 index시작점임
  								    #k는 메인 arr index시작점임

    while i<len(l) and j<len(r):    #l, r 두개 배열에 대해서 가장 앞의 값 대소비교 후 작은 요소 arr에 할당 
    								#l,r은 위의 9,10 line에서 재귀를 통해 이미 정리되어 있음
        if l[i]<r[j]:
            arr[k]=l[i]
            i+=1
        else:
            arr[k]=r[j]
            j+=1
        k+=1
    
    if i==len(l):    		        #l에있는거 다 쏟았으면 r에 있는 요소 arr에 추가
        while j<len(r):
            arr[k]=r[j]
            j+=1
            k+=1
    elif j==len(r):				    #r에 있는거 다 쏟았으면 l에 있는 요소 arr에 추가
        while i<len(l):
            arr[k]=l[i]
            i+=1
            k+=1
    return arr

N=int(input())
A=[]
for i in range(N):
    A.append(int(input()))
A=merge_sort(A)
for i in A:
    print(i)

---

도수 정렬 (=계수정렬=counting sort) 

• 특정 조건에만 사용 가능한 정렬이다. 사용 조건이 있으나, 조건만 맞으면 매우빠르다. 
  조건) 데이터의 크기범위가 제한되어있어서 정수범위로 표현 가능할 때 사용가능함.
  시간복잡도 O(N+K)      [ N = 데이터 개수, K = 양수 최대값 ]

출처 : 유튜버 '동빈나' 님의 설명자료

도수 정렬에 관해서 백준에 좋은 예제가 있다. 수 정렬하기 3

https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

import sys              #백준 10989 수 정렬하기3 (counting sort = 기수정렬 = 도수 정렬)
input=sys.stdin.readline

N=int(input())
arr=[0]*(10001)
for i in range(N):
    arr[int(input())]+=1

for i in range(10001):
    if arr[i]!=0:
        for j in range(arr[i]):
            print(i)

---

정렬 공부 참고자료

 

정글에서 함께 공부하는 학우분께서 정렬개념을 시각적으로 확인할 수 있는 유용한 웹사이트를 공유해주셨다.

하기 사이트에서 각 Sort 개념들에 해당하는 애니매이션을 볼 수 있다.  

https://visualgo.net/en/sorting

VisuAlgo - Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix)

 

각 정렬별 시간복잡도

정렬 종류	시간 복잡도			공간 복잡도
	평균(Average)	최선(Best)	최악(Worst)
선택 정렬	O(N2)	O(N2)	O(N2)	O(N2)
버블 정렬	O(N2)	O(N2)	O(N2)	O(N)
삽입 정렬	O(N2)	O(N)	O(N2)	O(N2)
합병 정렬	O(N×logN)	O(N×logN)	O(N×logN)	O(N×logN)
퀵 정렬	O(N×logN)	O(N×logN)	O(N2)	O(N×logN)
힙 정렬	O(N×logN)	O(N×logN)	O(N×logN)	O(N×logN)
쉘 정렬	O(N^1.25)	O(N^1.25)	O(N^1.25)	O(N)
기수 정렬	O(dN)	O(dN)	O(dN)

이미지 출처 : https://coding-factory.tistory.com/615

[Algorithm] 각 정렬의 특징 및 장단점 & 시간복잡도

소스코드 참조 유튜브 :  https://youtu.be/KGyK-pNvWos