정렬 (sort)

선택 정렬 (Selection sort)

: (오름차순 기준)매번 가장 작은 것을 선택하여 앞으로 보내는 과정을 반복 수행하여 정렬하는 것

 

삽입 정렬 (Insertion sort)

: 특정 데이터를 적절한 위치에 삽입하는 정렬. 특정 데이터가 적절한 위치에 들어가기 이전에, 그 앞에 있는 데이터는 정렬이 되어있다고 가정한다. 정렬된 데이터 리스트에서 적절한 위치를 찾고 그 위치에 삽입된다.

시간복잡도 :  O(N^2)

 

퀵 정렬 (Quick sort)

: 선택, 삽입 정렬보다 빠른 정렬 알고리즘. 기준점인 피벗을 설정하고 이를 기준으로 큰 수와 작은 수의 위치를 바꾼다. 대표적인 분할 방식인 호어 분할 (Hoare Partition)방식에서는 '리스트에서 첫번째 데이터를 피벗으로 정한다.'는 규칙이 있다. 

시간복잡도 : O(NlogN), 최악의 경우 O(N^2)

 

계수 정렬 (Count sort)

: 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는 정렬. 즉 최댓값 데이터까지 담을 수 있는 리스트를 생성하고 (max + 1) 데이터를 하나씩 확인하며 동일한 인덱스에 데이터를 1씩 증가시키는 정렬방식

* 데이터 크기가 한정되어있고 데이터의 크기가 많이 중복되어져 있을 때 사용하는 것이 유리하다.

시간복잡도 : O(N+K) 데이터의 갯수 N, 데이터의 최댓값 K

 

파이썬 정렬 라이브러리

파이썬은 sorted() 함수를 제공한다.퀵 정렬과 방식이 비슷한 병합 정렬 기반으로 만들어졌다. 최악의 경우에도 O(NlogN) 시간복잡도를 보장한다. - sorted(), sort()