4️⃣ 정렬 #4
Comments
선택정렬가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택에서 두번째 데이터와 바꾸는... 과정을 반복하는 것. 가장 원시적인 방법으로 매번 '가장 작은 것을 선택'한다는 의미에서 선택 정렬 Selection Sort 알고리즘이라고 한다. array = [3, 7, 1, 0, 2, 8, 9]
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 다른 대부분의 프로그래밍 언어에서 명시적으로 임시저장용 변수를 만들어 원소의 값을 변경해야 하지만 파이썬에서는 단순히 원소값을 변경할 수 있다.
|
삽입정렬삽입정렬은 특정 데이터를 적절한 위치에 삽입한다는 의미에서 삽입 정렬 Insertion sort 라고 부른다. 데이터를 하나씩 확인하여 필요할 때만 위치를 바꾸는 정렬로 데이터가 '거의' 정렬되어있을 때 훨씬 효율적이다. 반면 선택 정렬은 데이터 상태와 상관없이 모든 원소를 비교하고 정렬한다. 삽입정렬은 특정 데이터가 들어가는 적절한 위치 앞까지의 데이터는 이미 정렬되었다고 가정한다. 때문에 삽입 정렬은 두번째 데이터부터 어떤 위치에 들어갈 지 판단한다. array = [3, 7, 1, 0, 2, 8, 9]
for i in range(1, len(array)) :
for j in range(i, 0, -1) :
if array[j] < array[j-1] :
array[j], array[j-1] = array[j-1], array[j]
else :
break
보통은 퀵 정렬이 빠르고 강력한 알고리즘이지만 정렬이 거의 된 상황이라면 퀵 정렬 알고리즘보다 삽입정렬이 강력하다. |
퀵정렬퀵정렬과 병합정렬 알고리즘은 정렬 알고리즘 중 가장 많이 사용되는 알고리즘이다. 기준을 설정한 다음 기준보다 큰 수와 작은 수를 교환해서 리스트를 반으로 나누는 방식으로 동작한다. 퀵 정렬에서는 피봇 Pivot이 사용되는데, 위에서 설명한 '기준'을 피봇이라고 표현한다. 퀵 정렬을 수행하기 전에 피봇을 어떻게 설정할 지 명시해야한다. 피봇 설정과 리스트 분할하는 방법에 따라 퀵 정렬을 여러 방식으로 나눈다.
피봇의 왼쪽에 피봇보다 작은 데이터가, 오른쪽은 큰 데이터가 위치하게 하는 작업을 분할 Divide 또는 파티션 Partition이라고 한다. 이 상태에서 왼쪽과 오른쪽 리스트를 피봇을 설정해 동일한 방식으로 정렬을 수행하여, 리스트의 전체 요소에 정렬이 이루어지도록 한다. array = [3, 7, 1, 0, 11, 2, 6, 4, 5, 8, 9]
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: #엇갈릴 경우
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)
|
계수정렬계수정렬 Count Sort알고리즘은 특정 조건이 부합할 때만 사용할 수 있으나 매우 빠른 정렬 알고리즘이다. 예를 들어 모든 데이터가 양의 정수일 경우, 데이터의 개수가 N개, 최대값이 K이면 최악의 경우에도 수행시간은 O(N+K)가 된다. 이와 같이 계수 정렬은 데이터 크기범위가 제한되고 정수형태로 표현할 수 있을 때 사용할 수 있다. 일반적으로 가장 큰 데이터와 작은 데이터의 차가 1백만을 넘지 않을 때 효과적�이다. 계수 정렬은 선택, 삽입, 퀵 정렬 알고리즘처럼 데이터 값을 비교해서 위치 변경을 하는 비교기반의 정렬알고리즘이 아니라, 별도의 리스트를 선언하여 그 안에 정렬에 대한 정보를 담는다. 예를 들어 정렬할 데이터의 범위가 0~7이라면 0부터 7까지 저장하는 크기가 8인 리스트를 선언한 후, 데이터를 확인해 데이터 값과 동일한 인덱스 데이터를 1씩 증가시키면 계수정렬이 된다. array = [7, 6, 2, 1, 0, 3, 5, 4, 2, 1, 3]
count_list = [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=' ')
- 계수정렬의 시간 복잡도
모든 데이터가 양의 정수일 때 데이터 개수가 N, 최대값이 K 이면 계수정렬의 시간 복잡도는 O(N+K)이다. 현존하는 정렬 알고리즘 중에서 **기수 정렬 Radix Sort**과 함께 가장 빠르다고 여겨진다.
- 계수정렬의 공간복잡도
계수 정렬의 공간 복잡도는 O(N+K)이다. 계수정렬은 데이터가 0과 999,999 단 두개만 존재하더라도, 리스트의 크기는 100만개가 되도록 선언해야 하는 비효율성을 초래할 수 있다. 동일한 값을 가진 데이터가 다수 등장할 때 적합한 정렬방식이다.
예를 들어 성적 데이터의 경우 중복된 점수가 있을 수도 있어서 계수정렬이 효과적이며, 퀵 정렬은 일반적인 경우에 빠르게 동작하기 때문에 데이터 특성을 파악하기 어려우면 퀵 정렬을 이용하는 것이 권장된다.
|
파이썬의 정렬 라이브러리파이썬의 기본 정렬 라이브러리. 퀵 정렬과 동작방식이 유사한 병합정렬 Merge Sort기반으로 만들어져있다. 병합 정렬은 일반적으로는 퀵정렬보다는 느리지만 최악의 경우에도 시간 복잡도 O(NlogN)을 보장한다. 정확히는 병합정렬과 삽입정렬의 개념을 더한 하이브리드 방식으로 알고리즘을 사용하고 있다. sorted()리스트, 딕셔너리 자료형을 입력받아 �정렬된 리스트 형태로 반환한다. array = [3, 7, 1, 0, 2, 8, 9]
print(sorted(array))sort()리스트의 원소를 바로 정렬하는 함수로 리스트 객체의 내장함수이다. 별도의 정렬된 리스트가 반환되지는 않는다. array = [3, 7, 1, 0, 2, 8, 9]
array.sort()
print(array)key 매개변수sorted(), sort()를 이용할 때 key 매개변수를 입력받을 수 있다. 매개변수로 들어가는 값은 정렬의 기준이 되며, 함수가 들어가야 한다. 예를 들어 튜플로 구성된 리스트의 경우 튜플의 두번째 원소를 기준으로 삼고 싶다면 아래와 같은 형태로 작성할 수 있다. def sort_by(items):
return items[2]
array = [('코숏': 3), ('스핑크스':2), ('아메숏': 1)]
print(sorted(array, key=sort_by)출력결과는
|
정렬 알고리즘 개요
The text was updated successfully, but these errors were encountered: