CH6. 정렬 개념정리 (part 1)

시간복잡도 O($n^2$)인 정렬: 선택, 삽입, 버블 정렬

1. 선택 정렬

가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 2번째 데이터와 바꾸는 정렬

• 공간복잡도: O(n)
• 수행 복잡도: O($n^2$)

특정한 리스트에서 가장 작은 데이터를 찾을 때 유리하다.

기본 로직

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

def selection_sort(array):
	n = len(array)

	# 0~(n-1)번 index에 들어갈 수 찾기
	for i in range(n):
		min_index = i

		# i 이후 index의 수 중 가장 작은 수의 index를 min_index에 저장
		for j in range(i + 1, n):
        
        	# 여기 부호만 바꾸면 내림차순 정렬도 가능
			if array[j] < array[min_index]:   
				min_index = j  

		# i index와 가장 작은 수의 위치 switch
		array[i], array[min_index] =  array[min_index], array[i]

selection_sort(array)
print(array)         # [1, 2, 3, 4, 5, 6, 7, 8, 9]

---

2. 삽입 정렬

현재 위치에서 그 앞 index 배열들을 비교해 자신이 들어갈 위치를 찾아 그 위치에 삽입.

• 알고리즘 문제 풀이에 사용하기에는 느린편이다.
• 데이터가 거의 정렬되어 있을 때 유리하다. (최선의 경우 O(N)의 시간 복잡도)

기본 로직

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

def insertion_sort(array):
	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

insertion_sort(array2)
print("삽입정렬:", array2)

---

3. 버블 정렬

선택 정렬의 변형이다. (2개씩 비교해 작은것을 앞으로)

기본 로직

1. 삽입 정렬은 2번째 index부터 시작. 현재 index와 이전 index 비교
2. 이전 index가 더 크면 현재 index와 바꿔준다
3. 현재 index가 더 크면 교환하지 않고 다음 2 연속 배열 비교
4. 이를 (전체 배열 크기 - 현재 순환한 바퀴 수)

def bubble_sort(a):
    n=len(a)
    for i in range(n):
		# n-i-1 위치: 0 ~ (n-i-1)에서 가장 큰 수가 배치
        for j in range(n-i-1):
            if a[j] > a[j+1]:   # 2개씩 비교해 작은것을 앞으로
                a[j], a[j+1] =a[j+1], a[j]

d=[2, 4, 5, 1, 3]
bubble_sort(d)
print(d)        # [1, 2, 3, 4, 5]