대표적인 정렬 알고리즘 알기 ( 선택정렬, 버블정렬, 삽입정렬, 병합정렬, 퀵정렬, 힙정렬)

1. 버블 정렬(Bubble Sort)

• 인접한 두 수를 비교해서 정렬해나가는 방식으로, 시간 복잡도는 O(n^2).
• 앞에서 부터 차례대로 인접한 두 수를 비교하며 위치를 1회 바꾸고 나면 가장 큰 수가 마지막으로 정렬된다.

주어진 배열이 다음과 같다고 하자

4 1 3 2 

|

1 4 3 2

|

1 3 4 2

|

1 3 2 4

• 1회 정렬을 마치고 나면 가장 큰 수인 4가 맨 뒤로 정렬이 된다 => 뒤쪽부터 하나씩 정렬이 됨.
• 바깥 for문은 앞 뒤로 확인하므로 n-1번째 까지 만 반복(i변수사용), 안쪽 for문은 점점 정렬할 범위가 뒤에서 부터 줄어들기 때문에    n - 1 - i 번째 까지 반복한다.

파이썬 코드

arr = [9,8,7,6,5,4,3,2,1]

def bubbleSort(arr):
	n = len(arr)
    
    for i in range(n - 1):
    	swapped = False
    	for j in range(n - 1 - i):
        	if arr[j] > arr[j + 1]:
            		arr[j], arr[j + 1] = arr[j + 1], arr[j]
                    swapped = True
        if not swapped:
        	break
        print(arr)

# 8 7 6 5 4 3 2 1 9
# 7 6 5 4 3 2 1 8 9
# 6 5 4 3 2 1 7 8 9
# 5 4 3 2 1 6 7 8 9
# ....
# 1 2 3 4 5 6 7 8 9

2. 선택 정렬(Selection Sort)

• 선택 된 숫자를 중심으로 뒤에 있는 수들 중 가장 작은 값을 찾아 맨 앞과 교환하는 방식의 정렬. => 앞부분부터 차례대로 정렬이 된다.
• 버블정렬과 마찬가지로 시간 복잡도는 O(n^2)이다.

4 1 3 2

                                                                       | -> (i == 0, 4 이후 숫자 중 제일 작은 1과 교환)

1 4 3 2

                                                                       | -> (i == 1, 4 이후 숫자 중 제일 작은 2와 교환)

1 2 3 4

                                                                      | -> (i == 2, 3 이후 제일 작은 숫자 이제 없음)

이미 정렬 끝

파이썬 코드

arr = [8,4,6,2,9,1,3,7,5]

def selectionSort(arr):
	n = len(arr)
	for i in range(n):
		minIdex = i
		for j in range(i + 1, n):
			if arr[j] < arr[minIndex]:
				minIndex = j # 제일 작은 수의 index를 찾고, 저장.
		arr[i], arr[minIndex] =  arr[minIndex], array[i]
		print(arr[:i+1])# 정렬를 완료한 i번째까지만 출력.

# [1]
# [1, 2]
# [1, 2, 3]
# [1, 2, 3, 4]
# [1, 2, 3, 4, 5]
# ...
# [1, 2, 3, 4, 5, 6, 7, 8, 9]

3. 삽입 정렬(Insertion Sort)

• 데이터를 알맞은 위치에 삽입하는 방식, 정렬된 데이터 그룹을 점점 늘려간다.
• 시간 복잡도 O(n^2)
• 만약 최선의 경우일 때(이미 정렬된 배열일시) O(n) 시간 복잡도를 가짐.

파이썬 코드

arr = [8,4,6,2,9,1,3,7,5]

def insertionSort(arr):
	n = len(arr)
    for i in range(1, n):
    	for j in range(i, 0, -1):
        	if arr[j - 1] > arr[j]:
            		arr[j - 1], arr[j] = arr[j], arr[j - 1]
                else:# 이미 i 이전 부분들은 정렬이 되어있는 상태로, 처음부터 arr[j] > arr[j-1] 면 break.
                    break
        print(arr[:i+1]) # i번째까지 정렬된 배열 출력.
 
 # 4 8
 # 4 6 8
 # 2 4 6 8
 # 2 4 6 8 9
 # 1 2 4 6 8 9
 # ...
 # 1 2 3 4 5 6 7 8 9

4. 병합 정렬(Merge Sort)

• 분할 정복과 재귀를 이용한 알고리즘이다. => 배열을 반을 쪼개는 것을 반복하고 각 쪼갠 배열을 각각 sort하고 병합하는 방식.
• 시간 복잡도는 O(n log n)이다.
• 메모리 사용도가 높아 입력개수가 많아지면 메모리 초과 날 수 있음.

파이썬 코드

def solution(arr):
    # 분할된 배열 길이가 1이면 정렬할 필요X 때문에 return
    if len(arr) <= 1:
        return
    # 중간 인덱스 값을 기준으로 배열을 재귀적으로 두 그룹으로 분할
    mid = len(arr) // 2
    g1 = arr[:mid]
    g2 = arr[mid:]

    solution(g1)
    solution(g2)
    # 두 그룹의 인덱스 값(i1,i2)을 통해 더 작은 값을 배열에 배치(index 변수가 병합될 배열의 인덱스)
    i1 = 0
    i2 = 0
    index = 0
    while i1 < len(g1) and i2 < len(g2):
        if g1[i1] < g2[i2]:
            arr[index] = g1[i1]
            i1 += 1
        else:
            arr[index] = g2[i2]
            i2 += 1
        index += 1
    
    # g1, g2 각 두 그룹에 남아있는 원소를 arr배열에 넣어서 마무리
    while i1 < len(g1):
        arr[index] = g1[i1]
        i1 += 1
        index += 1
    while i2 < len(g2):
        arr[index] = g2[i2]
        i2 += 1
        index += 1

if __name__ == "__main__":
    n = int(input())
    arr = []
    for _ in range(n):
        arr.append(int(input()))
    
    solution(arr)
    for val in arr:
        print(val)

병합정렬 그림 참고

5. 퀵 정렬

• 병합 정렬과 마찬가지로 분할 정복 알고리즘
• 추가적인 메모리 공간이 필요없음
• pivot을 정하고 그 기준으로 정렬
• 시간 복잡도 O(n log n), 최악일 때 O(n**2) : 배열이 순차 또는 역순 정렬일 때 

파이썬 코드

arr = [8,4,6,2,5,1,3,7,9]

def quickSort(arr):
	if len(arr) <= 1:
		return arr
	pivot = len(arr) // 2
	frontArr, pivotArr, backArr = [], [], []
	for value in arr:
		if value < arr[pivot]:
			frontArr.append(value)
		elif value > arr[pivot]:
			backArr.append(value)
		else:
			pivotArr.append(value)
	print(frontArr, pivotArr, backArr)
	return quickSort(frontArr) + quickSort(pivotArr) + quickSort(backArr)


arr = quickSort(arr)
print(arr)
# [4 2 1 3] [5] [8 6 7 9]
# [] [1] [4 2 3]
# [] [2] [4 3]
# [] [3] [4]
# [6] [7] [8 9]
# [8] [9] []
# 1 2 3 4 5 6 7 8 9

6. 힙 정렬(Heap Sort)

• 힙 정렬은 힙의 루트에 가장 크거나 작은 값이 들어간다는 점을 이용하는 알고리즘(최대 힙 또는 최소 힙)
• 힙에서 루트가 아닌 다른 모든 노드는 부모 노드보다 작거나 큰 값을 갖는데, pop을 했을 때 가장 작거나 큰 값이 나옴
• 힙에 모든 원소를 넣고 순서대로 pop을 시켜서 반환 => 정렬된 리스트 반환.

파이썬 코드

import heapq

def heapSort(arr):
  h = []
  for val in arr:
    heapq.heappush(h, val)# 각 val를 h 배열에 push
  return [heapq.heappop(h) for _ in range(len(h))]

arr = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]
newArr = heapSort(arr)
print(newArr)

 

시간 복잡도 정리

출처 : 네이버 https://d2.naver.com/helloworld/0315536

	시간 복잡도(최선)	시간 복잡도(평균)	시간 복잡도(최악)	공간 복잡도
버블 정렬	O(n)	O(n**2)	O(n**2)	O(1)
선택 정렬	O(n**2)	O(n**2)	O(n**2)	O(1)
삽입 정렬	O(n)	O(n**2)	O(n**2)	O(1)
합병 정렬	O(nlog(n))	O(nlog(n))	O(nlog(n))	O(n)
퀵 정렬	O(nlog(n))	O(nlog(n))	O(n**2)	O(log(n))

 

참고자료

파이썬으로 정렬 알고리즘

 

정렬 알고리즘 종류와 설명(파이썬 예제)

 

TIL24. 정렬 알고리즘 정리 (feat.python)