01. List 1 - 5차시 Sort

1. 정렬

2개 이상의 자료를 특정 기준에 의해 오름차순 또는 내림차순하는 것이다.

Key : 자료를 정렬하는 기준이 되는 특정 값

예) 서류 번호대로 정렬하기 -> 키는 서류 번호가 된다.

 

2. 버블 정렬(Bubble Sort)

---

인접한 두 개의 원소를 비교하여 자리를 계속 교환하는 방식

---

첫번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리까지 이동한다. 한 패스가 끝나면 가장 큰 원소 또는 가장 작은 원소가 마지막 자리로 정렬된다.

 

시간복잡도 = O(n^2)

 

예시) 55, 7, 78, 12, 42

1. 첫번째 패스

55 7 78 12 42

7 55 78 12 42

7 55 78 12 42

7 55 12 78 42

7 55 12 42 [78]

이렇게 한 패스가 끝나면 가장 큰 원소가 마지막에 배치된다. 78이 정렬되었다.

 

2. 두번째 패스

이때 정렬의 범위는 앞 패스에서 정렬된 원소를 제외하기 때문에 정렬 범위가 하나 줄어든다.

7 55 12 42 [78]

7 55 12 42 [78]

7 12 55 42 [78]

7 12 42 [55 78]

 

3 세번째 패스

7 12 42 [55 78]

7 12 42 [55 78]

7 12 [42 55 78]

 

4. 네번째 패스

7 12 [42 55 78]

7 [12 42 55 78]

 

5. 정렬 끝

[7 12 42 55 78]

 

슈도코드

def bubbleSort(list): 
	for i in range(len(list) - 1, 0, -1): # 범위의 끝 위치
    	for j in range(0, i):
        	if list[j] > list[j + 1]:
            	list[j], list[j + 1] = list[j + 1], list[j]

 

3. 카운팅 정렬(Counting Sort)

항목들의 순서를 결정하기 위해 집합에 각 항목이 몇개씩 있는지 세는 작업을 하여, 선형시간에 정렬하는 효율적인 알고리즘

 

정렬과정

정수나 정수로 표현할 수 있는 자료에 대해서만 적용 가능하다. 각 항목의 발생 횟수를 기록하기 위해, 정수 항목으로 인데스되는 카운트들의 리스트를 사용하기 때문이다.

 

카운트들을 위한 충분한 공간을 할당하려면 집합 내의 가장 큰 정수를 알아야 한다.

 

시간 복잡도 = O(n + k) ; n은 리스트의 개수, k는 정수의 최대값

 

예시) 0, 4, 1, 3, 1, 2, 4, 1

0	1	2	3	4
1	3	1	1	2

각 데이터의 개수를 카운팅하고 그대로 출려하면서 하나씩 줄여나간다.

 

0	1	2	3	4
0	3	1	1	2

0

0	1	2	3	4
0	2	1	1	2

0 1

0	1	2	3	4
0	1	1	1	2

0 1 1

0	1	2	3	4
0	0	1	1	2

0 1 1 1 

0	1	2	3	4
0	0	0	1	2

0 1 1 1 2 

...

이런식으로 진행한다.

 

슈도코드

def countingSort(A, B, k):
# A [1 .. n] : 입력 리스트 사용된 숫자(1 ~ k)
# B [1 .. n] : 정렬된 리스트
# C [1 .. k] : 카운트 리스트
	
    C = [0] * k
    
    for i in range(0, len(B)):
    	C[A[i]] += 1
        
    for i in range(1, len(C)):
    	C[i] += C[i - 1]
        
    for i in range(len(B)-1, -1, -1):
    	B[C[A[i]]-1] = A[i]
        C[A[i]] -= 1

a = [0, 4, 1, 3, 1, 2, 4, 1]
b = [0] * len(a)

countingSort(a, b, 5)
print(b)