정렬

정렬

요소들을 일정한 순서대로 열거하는 알고리즘

정렬의 특징

• 정렬 기준은 사용자가 정할 수 있다.
• 크게 비교식과 분산식 정렬로 나눌 수 있다.
• 대부분의 언어가 빌트인으로 제공해준다.
• 삽입, 선택, 버블, 머지, 힙, 퀵 정렬 등다양한 정렬 방식이 존재한다.

어떤 정렬이 제일 빠를까?

정렬들은 각각 유리한 상황과 불리한 상황이 있기 때문에 어떤 정렬이 젤 빠른지 알 수 없다.

비교식 정렬

버블 정렬

서로 인접한 두 요소를 검사하여 정렬하는 알고리즘 O(n^2) 시간복잡도를 가진다.

선택 정렬

선택한 요소와 가장 우선순위가 높은 요소를 교환하는 정렬 알고리즘 O(n^2)시간복잡도를 가진다.

삽입 정렬

선택한 요소를 삽입 할 수 있는 위치를 찾아 삽입하는 방식의 정렬 알고리즘 O(n^2)시간 복잡도를 가진다.

분산식 정렬

분할 정복

문제를 작은 2개의 문제로 분리하고 더 이상 분리가 불가능할 때 처리한 후 합치는 전략

합병 정렬

분할 정복 알고리즘을 이용한 최선과 최악이 같은 안정적인 정렬 알고리즘 O(nlogn)시간 복잡도를 가진다.

요소가 하나가 될때까지 나눈후 합쳐준다.!
선형시간이 logn만큼 걸려서 nlogn이 걸린다.

퀵 정렬

분할 정복 알고리즘을 이용한 매우 빠르지만 최악 경우가 존재하는 불안정 정렬 O(nlog)시간 복잡도를 가진다.

sort

array = [5, 9, 10, 3, 8, 3, 2]

## 기존 List 변수는 변하지 않고 정렬된 새로운 List를 반환한다.
print(sorted(array))
print(array)

# List 변수가 변한다.
array.sort()
print(array)