[파이썬] 정렬 알고리즘 - 버블 정렬 & 카운팅 정렬

버블 정렬

특징

• 인접한 두 개의 원소를 비교하며 자리를 계속 교환하는 방식
• 첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리까지로 이동하는 정렬
• 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬됨 (시간 복잡도 O(n^2))
• 실제로 알고리즘 풀이에는 잘 쓸일 없음(시간 복잡도 때문)

정렬 과정

7, 6, 4 를 정렬한다고 해보자.

Step

1. 맨 앞의 7과 6의 자리를 서로 바꿔준다.
2. 다시 반복해서 7과 4의 자리를 바꿔준다.
3. (숫자가 더 많을 경우) 계속해서 반복해서 바꿔준다.

1번의 싸이클이 돌고 난 후 다시 처음부터 같은 작업을 반복한다

버블 정렬 코드

def Bubblesort(List): #정렬할 list, 원소 수 N
	for i in range(len(List)-1, 0, -1) : # 범위의 끝
		for j in range(i) :
			if List[j] > List[j+1] : #현재 항이 다음 항보다 클 경우
				List[j], List[j+1] = List[j+1], List[j] #서로의 위치를 바꿔라

 

반응형

카운팅 정렬

항목들의 순서를 결정하기 위해 집합에 각 항목이 몇개씩 있는지 세는 작업을 하여 선형 시간에 정렬하는 정렬법

• 제약 : 카운트들을 위한 충분한 공간을 할당하려면 집합 내의 가장 큰 정수를 알아야 함, 숫자가 너무 클 경우 정렬에 어려움이 있음
• 시간복잡도 : O(n+k) (n은 리스트의 길이, k는 정수의 최대값)

정렬 진행 과정 

그림 출처 : https://spagnuolocarmine.github.io/counting-sort

Step

1. 그림 속 리스트 A에서 각 항목들의 발생 횟수를 인덱스로 한 리스트 C를 생성

2. 생성된 리스트 C를 기준으로, 정렬된 집합에서 각 항목 앞에 위치할 항목들의 갯수를 반영하기 위한 modified C를 생성한다

→ 추가설명) C를보면 [3, 2, 1, 0, 2, 1]로 modified C를 보면 [3, 5, 6, 6, 8, 9]이다. modified C는 C의 원소의 앞에 까지의 합이라고 생각하면 된다.
modified C의 0번 인덱스 = C의 0번 인덱스까지의 합 = 3

modified C의 1번 인덱스 = C의 1번 인덱스까지의 합 = 3+2 = 5

modified C의 2번 인덱스 = C의 2번 인덱스까지의 합 = 3+2+1 = 6 ....

3. 이제 리스트 A를 기준으로 오른쪽부터 하나씩 체크하면서 내려온다. (1 → 5 → 4 ...)

4. 숫자 1에 해당하는 Modified C의 인덱스에 해당하는 값을 보면 5이므로, B의 5번째 자리에 1을 넣고, Modified C의 5를 -1해서 4로 수정한다.

5. 다음 숫자 5에 대해서  Modified C의 인덱스에 해당하는 값은 9이므로, B의 9번째 자리에 1을 넣고, Modified C의 9를 -1해서 8로 수정한다

6. 위 3~5 과정을 반복해서 정렬된 리스트 B를 생성한다.

카운팅 정렬 코드

def counting_sort(A):

    C = [0]*(max(A)+1)
    B = [0]*len(A)

    for i in A:
        C[i] += 1   # A 요소의 출현 횟수

    for i in range(len(C)-1):   
        C[i+1] += C[i]  

    for i in range(len(A)-1, -1, -1):
        B[C[A[i]] - 1] = A[i]
        C[A[i]] -= 1
    
    return B

# 조금 더 줄인 코드
def counting_sort(arr):
    k = max(arr)
    C = [0]*(k+1)
    A = [] #정렬된 리스트

    for i in arr :
        C[i] += 1 # arr에 든 숫자의 갯수를 인덱스로 리스트 C 생성
        
    for j in range(1, k+1): 
        for _ in range(C[j]):
            A += [j]
    return A

 

---

개인적인 생각

알아두면 분명 좋은 정렬 방법이지만, 파이썬에선 내장함수 sort나 sorted가 있으니 활용하는게 더 빠르고 간결하니 알고리즘 문제를 풀때는 sort를 활용하자.