[알고리즘 기초] 2. 정렬 알고리즘

[주의] 개인 공부를 위해 쓴 글이기 때문에 주관적인 내용은 물론, 쓰여진 정보가 틀린 것일 수도 있습니다!

피드백 부탁드립니다. (- -)(_ _) 꾸벅

 

https://dev.to/koladev/8-must-know-sorting-algorithms-5ja

8 must-know sorting algorithms

---

더 자세한 시간복잡도 순서

 

1. 버블정렬 (Bubble sort)

순서가 잘못된 경우 항목을 교환하여 작동하는 가장 원시적 형태의 알고리즘.

어떠한 경우든 모든 항목을 검사하기 때문에 시간복잡도는 O(n²)이다. 

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

for i in range(1, len(array)):
    for j in range(0, len(array)-i):
        if array[j] > array[j+1]:
            array[j], array[j+1] = array[j+1], array[j]

print(array)

---

2. 선택정렬 (Selection sort)

버블정렬의 개선판. 최악의 경우 버블정렬과 성능이 동일(O(n²)하더라도, 선택정렬은 더 적게 스왑함.

처리되지 않는 데이터 중 가장 작은 데이터를 선택하여 맨 앞에 있는 데이터와 바꾸는 것을 반복

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

for i in range(len(array)):
	min_index = i
	for j in range(i+1, len(array)):
		if array[min_index] > array[j]:
			min_index = j
	array[i], array[min_index] = array[min_index], array[i]

print(array)

---

3. 삽입정렬 (Insert sort)

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

구현 난이도가 높지만 선택정렬보다 빠르게 동작. 왜냐면 선택정렬은 모든 요소를 탐색하지만 삽입정렬의 경우 필요한 요소만큼만 탐색하기 때문이다.

정렬되어있는 경우 한번의 비교만 이루어지기 때문에 복잡도가 O(n)이다.

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

for i in range(1, len(array)): 
    for j in range(i, 0, -1): 
        if array[j-1] > array[j]: 
            array[j-1], array[j] = array[j], array[j-1] 
        else: break 

print(array)

---

4. 퀵 정렬 (Quick sort)

* [분할 정복(divide and conquer) 방법]
문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.

분할 정복을 사용하며, 기준 데이터를 설정하고 그 기준으로 작은 수와 큰 수의 위치를 바꾸는 방법.

일반적으로 정렬하면 가장 많이 사용되는 알고리즘이다.

1. 맨 처음 숫자를 Pivot으로 설정
2. Pivot을 기준으로 왼쪽으로는 큰 수를 탐색, 오른쪽으로는 작은 수를 탐색
3. 큰 수와 작은 수의 위치를 바꾸고, 남은 숫자들을 계속 탐색
4. 교차되면 작은 수의 위치와 Pivot을 위치를 바꾸고 Divde and Conquer로써 Pivot 양 옆을 재귀적으로 퀵 정렬

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

def quickSort(data, left, right):
	if right<= left:
		return 
	else:
		pivot = partition(data, left, right)
		quickSort(data, left, pivot - 1)
		quickSort(data, pivot + 1, right)

	return data

def partition(data, left, right):
	pivot = data[left]
	leftIndex = left + 1
	rightIndex = right

	while True:
		while leftIndex <= rightIndex and data[leftIndex] <= pivot:
			leftIndex += 1
		while rightIndex >= leftIndex and data[rightIndex] >= pivot:
			rightIndex -= 1
		if rightIndex <= leftIndex:
			break
		data[leftIndex], data[rightIndex] = data[rightIndex], data [leftIndex]
		print(data)

	data[left], data[rightIndex] = data[rightIndex], data[left]
	print(data)

	return rightIndex

quickSort(array, 0, len(array)-1)

 

 

퀵 정렬은 가장 이상적인 Pivot이 가운데 있는, 즉 반반으로 나눠지면 O(n·logn)의 이상적인 시간복잡도를 가지지만, 불균형하게 한쪽으로 몰리는 최악의 경우에는 깊은 순환 호출이 일어나기 때문에 O(n²)의 시간복잡도를 가진다.\

 

---

5. 병합 정렬 (Merge sort)