[4] 정렬

정렬(Sorting)

데이터를 특정한 기준에 따라서 순서대로 나열하는 것

정렬 알고리즘으로 데이터를 정렬하면 이진 탐색(Binary Search)이 가능해진다.

 

1. 선택 정렬 (Selection Sort)

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

 

가장 작은 것을 선택해서 앞으로 보내는 과정을 반복하면 전체 데이터의 정렬이 이루어짐.

 

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

에서 가장 작은 데이터인 0을 1번째 인덱스인 7과 자리를 바꾼다.

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

두 번째로 가장 작은 데이터인 1과 2번째 인덱스인 5와 자리를 바꾼다.

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

...

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

데이터가 10개인 경우, 9번만 반복하더라도 마지막 데이터는 가만히 두어도 정렬된 상태라고 할 수 있다.

즉, n-1 번째 단계에서 정렬을 마칠 수 있다.

 

선택 정렬 소스코드

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] # swap

print(array)

 

스왑(swap)이란

특정한 리스트가 주어졌을 때 두 변수의 위치를 변경하는 작업

 

 

2. 삽입 정렬(Insertion Sort)

데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입

선택 정렬에 비해 구현 난이도가 높은 편이지만 실행 시간 특면에서 더 효율적이다.

필요할 때에만 위치를 바꾸므로 '데이터가 거의 정렬되어 있을 때' 훨씬 효율적

특정한 데이터를 적절한 위치에 '삽입'

 

특정한 데이터가 적절한 위치에 들어가기 이전에, 앞까지의 데이터는 정렬되어 있다고 가정

정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤, 그 위치에 삽입된다.

 

삽입 정렬은 두 번째 데이터부터 시작

( 첫 번째 데이터는 그 자체로 정렬되어 있다고 판단 )

 

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

'5'가 어떤 위치에 들어가야할지 판단

1. 7의 왼쪽

2. 7의 오른쪽

오름차순 정렬에서, '5'가 7보다 작기 때문에 7의 왼쪽에 삽입한다.

 

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

'9'가 어떤 위치에 들어가야할지 판단

1. 5의 왼쪽

2. 5와 7의 가운데

3. 7의 오른쪽

9는 7보다 크기 때문에 그 자리 그대로 둔다.

 

... 반복 ...

 

정렬된 원소는 항상 오름차순을 유지함

 

 

삽입 정렬 소스코드

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): # 인덱스 i부터 1까지 감소하며 반복
    	if array[j] < array[j-1]:
        	array[j], array[j-1] = array[j-1], array[j]
        else: # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
        	break
            
print(array)

 

3. 퀵 정렬 (Quick Sort)

정렬 알고리즘 중 가장 많이 사용되는 알고리즘

기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꿈

 

기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나눔

 

피벗(Pivot) : 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 기준

퀵 정렬을 수행하기 전, 피벗을 어떻게 설정할 것인지 미리 명시해야 함

 

호어 분할(Hore Partition) 방식

: 리스트에서 첫 번째 데이터를 피벗으로 정한다.

 

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

피벗 : 5

왼쪽에서부터 '5'보다 큰 데이터 선택 = '7'

오른쪽에서부터 '5'보다 작은 데이터 선택 = '4'

두 위치를 서로 변경

 

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

다시 피벗보다 큰 데이터('9'), 작은 데이터('2') 선택

 

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

피벗보다 큰 데이터 = '6'

피벗보다 작은 데이터 = '1'

* 위치가 서로 엇갈린다

이와 같은 경우, 작은 데이터와 피벗의 위치를 서로 변경한다.

 

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

피벗이 이동한 상태에서 왼쪽 리스트와 오른쪽 리스트를 분할한다.

 

이 리스트를 분할하여 퀵 정렬을 다시 진행한다.

 

퀵 정렬 소스코드

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

def quick_sort(array, start, end):
	if start >= end: # 원소가 1개인 경우 종료
    	return
    pivot = start # 피벗은 첫 번째 원소
    left = start + 1
    right = end
    while left <= right:
    	# 피벗보다 큰 데이터를 찾을 때 까지 반복
        while left <= end and array[left] <= array[pivot]:
        	left += 1
        # 피벗보다 작은 데이터를 찾을 때 까지 반복
        while right > start and array[right] >= array[pivot]:
        	right -= 1
        if left > right: # 엇갈렸다면 작은 데이터와 피벗 교체
        	array[right], array[pivot] = array[pivot], array[right]
        else : # 엇갈리지 않았다면 작은 데이터와 큰 데이터 교체
        	array[left], array[right] = array[right], array[left]
    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    quick_sort(array, start, right - 1)
    quick_sort(array, right + 1, end)
        
quick_sort(array, 0, len(array) - 1)
print(array)

 

파이썬의 장점을 살린 퀵 정렬 소스코드

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

def quick_sort(array):
	# 리스트가 하나 이하의 원소만을 담고 있다면 종료
    if len(array):
    	return array
        
    pivot = array[0] # 피벗은 첫 번째 원소
    tail = array[1:] # 피벗을 제외한 리스트
    
    left_side = [ x for x in tail if x <= pivot] # 분할된 왼쪽 부분
    right_side = [ x for x in tail if x > pivot] # 분할된 오른쪽 부분
    
    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬을 수해하고, 전체 리스트를 반환
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)
    
print(quick_sort(array))

 

4. 계수 정렬 (Count Sort)

특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘

'데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때'만 사용 가능

 

일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용

비교 기반의 정렬 알고리즘X

 

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

 

가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트 생성

가장 큰 데이터가 '9'이고 가장 작은 데이터가 '0'이다.

따라서, 범위가 0부터 9까지이므로 리스트의 인덱스가 모든 범위를 포함할 수 있도록 크기가 10인 리스트 생성

 

처음에는 모든 데이터가 0이 되도록 초기화

그 다음 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시킴

 

[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]

 

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

[ 0, 0, 0, 0, 0, 0, 0, 1, 0, 0 ]

 

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

[ 0, 0, 0, 0, 0, 1, 0, 1, 0, 0 ]

... 반복 ...

 

[ 2, 2, 2, 1, 1, 2, 1, 1, 2 ]

 

결과적으로 위와 같이 리스트에는 각 데이터가 몇 번 등장했는지 횟수가 기록된다.

예를 들어 5 인덱스의 값이 2 이므로 5가 2번 등장한 것이다.

 

저장된 데이터 자체가 정렬된 형태 그 자체라고 할 수 있음

정렬된 결과를 확인하고 싶다면 리스트의 첫 번째 데이터부터 하나씩 그 값만큼 인덱스를 출력하면 된다.

 

계수 정렬 소스코드

# 모든 원소의 값이 0보다 크거나 같다고 가정
array = [ 7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2 ]
# 모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화)
count = [0] * (max(array) + 1)

for i in range (len(array)):
	count[array[i]] += 1 # 각 데이터에 해당하는 인덱스의 값 증가
    
for i in range (len(count)): # 리스트에 기록된 정렬 정보 확인
	for j in range(count[i]):
    	print(i, end = ' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력