정렬

정렬 알고리즘에는 선택정렬, 삽입정렬, 퀵정렬 등 다양한 방식이 있다.

선택정렬(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)):  # for문을 돌면서 가장 작은 원소를 찾아 넣어준다.
     	if array[min_index] > array[j]:
        	min_index = j
   	array[i], array[min_index] = array[min_index], array[i]
    
print(array)

 

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

 

array = [3, 5]

array[0], array[1] = array[1], array[0]  

 

 

삽입정렬(Insertion Sort) : O(N^)

 

데이터를 하나씩 확인하며, 특정한 데이터를 적절한 위치에 삽입하는 알고리즘이다. 

특히 삽입정렬은 필요할때만 위치를 바꾸므로, 데이터가 거의 정렬되어 있을떄 훨씬 효율적이며, 선택정렬보다 더 효율적인 알고리즘이다. 

삽입정렬은 첫번째 데이터는 정렬되어 있다고 가정하고 두번째 데이터부터 시작한다.

 

 

 

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

for i in range(1, len(array)):   # 맨처음 원소는 정렬되었다고 가정. 1부터 시작한다
	for j in range(i, 0, -1):  # 인덱스 i부터 1까지 1씩 감소
    	if array[j] < array[j-1]:  # 내가 내 왼쪽보다 작다면 한칸 왼쪽으로 이동
        	array[j], array[j-1] = array[j-1], array[j]
        else:
        	break
            
print(array)

* range의 매개변수가 세개인 경우 :  range(start, end ,step)

 

 

퀵 정렬(Quick Sort) : O(NlogN)

 

기준을 설정한 다음, 큰 수와 작은 수를 교환 후 리스트를 반으로 나누는 방식으로 동작한다.

이 기준을 피벗(pivot)이라고 하고, 가장 대표적인 방식은 호어 분할 방식이다. ( = 리스트의 첫 번째 데이터를 피벗으로) 

앞의 두 정렬 방법에 비해 매우 빠른 편이다. 최악의 경우 시간복잡도는 O(N^)이다. 

 

 

 

• 리스트의 첫 번째 데이터인 3을 피벗으로 설정한다.
• 왼쪽에서부터는 피벗보다 큰 데이터를 찾고, 오른쪽에서부터는 피벗보다 작은 데이터를 찾는다.
• 모두 찾았다면, 두 데이터의 위치를 서로 교환해준다. ( 이 과정을 반복한다.)
• 두 데이터의 위치가 엇갈린다면, 피벗과 작은 데이터의 위치를 변경한다.

분할완료시, 피벗의 왼쪽에는 피벗보다 작은 데이터가 위치하고, 피벗의 오른쪽에는 피벗보다 큰 데이터가 위치한다. 

이 상태에서 왼쪽과 오른쪽 리스틀ㄹ 개별적으로 다시 정렬시킨다.

 

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

def quick_sort(array, start, end):
	if start >= end:  # 원소가 한개인 경우 => 종료
    	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:  # 두 데이터가 엇갈렸다면 => pivot, right(작은거) 교체
        	array[right], array[pivot] = array[pivot], array[right]
        else:  # 엇갈리지 않았다면 => right, left 교체
        	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)

 

 

계수 정렬(Count Sort) : O(N+K)

(N은 데이터 갯수, K는 데이터 중 최댓값의 크기)

 

계수 정렬은 특정한 조건이 부합할 때만 사용이 가능하지만, 매우 빠르게 동작하는 알고리즘이다.

계수 정렬에서는 모든 범위를 담을 수 있는 크기의 리스트를 선언해, 그 리스트 안에 정렬에 대한 정보를 담는 방식이다.

리스트에 각 데이터가 몇 번 등장했는지를 기록하고, 정렬결과는 기록된 값만큼 인덱스를 출력해주면 된다. 

* 조건 : 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때

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

 

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

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=' ')

 

 

파이썬은 기본 정렬 라이브러리를 제공한다. sort()와 sorted().

정렬 라이브러리는 최악의 경우에도 시간복잡도 O(NlogN)을 보장한다. 

sorted()는 퀵 정렬과 동작방식이 비슷한 병합 정렬을 기반으로 만들어졌다. 

 

1. sorted() :  입력받아 정렬된 결과를 반환한다. 

 

array = [3, 1, 5]

result = sorted(array)

 

2. sort() : 별도의 정렬된 리스트가 반환되지 않고, 내부 원소가 바로 정렬된다. 

 

array = [3, 1, 5]

array.sort()

 

sorted()나 sort()를 이용할 때는 key매개변수를 입력으로 받을 수 있다.

key값으로는 하나의 함수가 들어가야 하며 이는 정렬 기준이 된다.