정렬 알고리즘
정렬 알고리즘 | 평균 시간 복잡도 | 공간 복잡도 | 특징 |
선택 정렬 | 아이디어가 매우 간단하다. | ||
삽입 정렬 | 데이터가 거의 정렬되어 있을 때는 가장 빠르다. | ||
퀵 정렬 | 대부분의 경우에 가장 적합하며, 충분히 빠르다. | ||
계수 정렬 | 데이터의 크기가 한정되어 있는 경우에만 사용이 가능하지만, 매우 빠르게 동작한다. |
선택정렬가장 작은 데이터를 선택해서 정렬되지 않은 데이터 중에서 가장 앞쪽에 있는 데이터와 위치를 바꾸는 방법이다.
삽입정렬•
데이터를 앞에서부터 하나씩 확인하며 데이터를 적절한 위치에 삽입하는 방법이다.
•
필요할 때만 위치를 바꾸므로 ‘데이터가 거의 정렬 되어 있을 때’ 효과적이다.
퀵 정렬•
기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다.
•
기준을 설정한 다음 큰 수와 작은 수를 교환한 후, 리스트를 반으로 나누는 방식으로 동작한다.
•
호어 분할 방식
◦
피벗 : 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 기준
◦
리스트에서 첫번째 데이터를 피벗으로 정한다.
•
데이터다 거의 정렬되어 있을 때는 느리게 동작한다.
계수 정렬•
특정한 값을 가지는 데이터의 개수를 카운트하는 방법이다.
•
가장 큰 데이터와 가장 작은 데이터의 차이가 1000000 을 넘지 않을 때 효과적으로 사용할 수 있다. (모든 범위를 담을 수 있는 크기의 리스트를 선언해야 하기 때문)
파이썬의 정렬 라이브러리
sorted() •
퀵 정렬과 동작 방식이 비슷한 병합 정렬을 기반으로 만들어졌다.
•
리스트, 딕셔너리 자료형 등을 입력받아서 정렬된 결과를 출력한다.
•
반환되는 결과는 리스트 자료형이다.
sort()•
별도의 정렬된 리스트가 반환되는 것이 아니라 내부 원소가 바로 정렬된다.
key 매개변수•
sorted() 나 sort() 를 이용할 때에는 key 매개변수를 입력으로 받을 수 있다.
•
리스트의 데이터가 튜플로 구성되어 있으며, 각 데이터의 두번째 원소를 기준으로 설정하는 경우
array = [('바나나', 2), ('사과', 5), ('당근', 3)]
def setting(data) :
return data[1]
result = sorted(array, key=setting)
print(result)
# output
[('바나나', 2), ('당근', 3), ('사과', 5)]
Python
복사