[알고리즘] 정렬 알고리즘 (Sorting Algorithm)

이전글 : )

[알고리즘] 완전 탐색 • 브루트 포스 (Brute Force)

 

---

 

 정렬 알고리즘 sorting algorithm 

정렬 알고리즘이란 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘입니다.

효율적인 정렬은 탐색이나 병합 알고리즘처럼 다른 알고리즘을 최적화하는 데 중요합니다.

또 정렬 알고리즘은 데이터의 정규화나 의미 있는 결과물을 생성하는 데 흔히 사용됩니다.

 

 대표적인 정렬 알고리즘 종류 

알고리즘	시간 복잡도
버블 정렬 (Bubble Sort)	O(n²)
선택 정렬(Selection Sort)
삽입 정렬 (Insertion Sort)
병합 정렬 (Merge Sort)	O(n log n)
퀵 정렬 (Quick Sort)

 

---

 

 버블 정렬 bubble sort 

wikipedia - bubble sort

버블 정렬이란 원소의 이용이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름입니다.

이는 두 인접한 원소를 검사하여 정렬하는 방법입니다.

시간 복잡도가 O(n²)로 상당히 느린 편이지만, 코드가 단순하기 때문에 자주 사용됩니다.

 

 예제 

# 버블 정렬 코드 예제

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

 

---

 

 선택 정렬 selection sort 

 wikipedia - selection sort

선택 정렬은 한 바퀴 돌 때 가장 작은 값을 찾아 맨 앞과 교환하는 정렬 알고리즘 입니다.

앞에서부터 정렬해나가는 특성을 가지고 있고 버블 정렬과 마찬가지로 O(n²)의 성능을 가지고 있습니다.

 

 예제 

# 선택 정렬 코드 예제

def selectionSort(x):
	length = len(x)
	for i in range(length-1):
	    indexMin = i
		for j in range(i+1, length):
			if x[indexMin] > x[j]:
				indexMin = j
		x[i], x[indexMin] = x[indexMin], x[i]
	return x

 

---

 

 삽입 정렬 insertion sort 

wikimedia - insertion sort

삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여,

자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘입니다.

key값은 2번째 인텍스부터 시작되며, 매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 삽입합니다.

 

 예제 

# 삽입 정렬 코드 예제

def insert_sort(x):
	for i in range(1, len(x)):
		j = i - 1
		key = x[i]
		while x[j] > key and j >= 0:
			x[j+1] = x[j]
			j = j - 1
		x[j+1] = key
	return x

 

---

 

 병합 정렬 merge sort 

wikipedia - merge sort

병합 정렬은 Devide and Conquer(분할 정복) 기법과 재귀 알고리즘을 이용한 정렬 알고리즘입니다.

주어진 배열을 원소가 각각 하나씩만 남도록 1/2로 쪼갠 후 다시 크기 순으로 재배열하면 원래의 길이인 배열로 합칩니다.

 

정렬 과정을 지켜보면 분할(split) 단계와 병합(marge) 단계로 나눌 수 있으며, 단순히 중간 인덱스를 찾아야 하는 분할 비용보다 모든 값을 비교해야 하는 병합 비용이 큽니다.

반복해서 반절로 쪼개는 과정은 O(logN)의 시간이 필요하며, 각 패스에서 병합할 때 모든 값을 비교해야 하므로 O(N)의 시간이 소모됩니다. 따라서 총 시간 복잡도는 O(NlogN)입니다.

다른 정렬 알고리즘과 달리 인접한 값들 간에 상호 자리 교태가 일어나지 않습니다.

 

 예제 

 

병합 정렬은 분할을 담당하는 merge_sort 함수와 병합을 담당하는 merge합수가 사용됩니다.

# 분할을 위한 merge_sort함수 예제

def merge_sort(list):
    if len(list) <= 1:
        return list
    mid = len(list) // 2
    leftList = list[:mid]
    rightList = list[mid:]
    leftList = merge_sort(leftList)
    rightList = merge_sort(rightList)
    return merge(leftList, rightList)

# 병합을 위한 merge함수 예제

def merge(left, right):
    result = []
    while len(left) > 0 or len(right) > 0:
        if len(left) > 0 and len(right) > 0:
            if left[0] <= right[0]:
                result.append(left[0])
                left = left[1:]
            else:
                result.append(right[0])
                right = right[1:]
        elif len(left) > 0:
            result.append(left[0])
            left = left[1:]
        elif len(right) > 0:
            result.append(right[0])
            right = right[1:]
    return result

 

 

---

 

 퀵 정렬 quick sort 

wikimedia - quicksort

퀵 정렬도 병합 정렬과 비슷하게 Devide and Conquer(분할 정복) 기법과 재귀 알고리즘을 이용한 정렬 알고리즘입니다.

기준 데이터를 설정(pivot)하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법입니다.

일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나입니다.

병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘입니다.

가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(pivot)로 설정합니다.

 

 예제 

# 퀵 정렬 코드 예제

def quick_sort(list):
	if len(list) <= 1 :
    	return list
    pivot = list{len(list) // 2]
    less_arr, equal_arr, big_arr = [],[],[]
    
    for i in list:
    	if i < pivot :
        	less_arr.append(i)
        elif i > pivot :
        	big_arr.append(i)
        else :
        	equal_arr.append()
    
    return quick_sort(less_arr) + equal_arr + quick(big_arr)

 

---

+

계수 정렬

[알고리즘] 계수 정렬 (Counting Sort)