정렬 알고리즘

선택 정렬

처리되지 않은 데이터 중에서 가장 작은 데이터를 '선택'하여 맨 앞에 있는 데이터와 바꾸는 것을 반복한다.

매번 데이터 중에서 가장 작은 값을 골라야 하기 때문에 이중 반복문을 사용해서 구현한다. O(n**2)

삽입 정렬

처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입하는 것을 반복한다. 첫 번째 데이터부터 정렬되어 있다고 판단하고, 다음 순서의 데이터를 정렬되어 있는 데이터들의 어디 위치에 들어갈지 판단한다.

모든 데이터를 한번씩 방문하고 그 데이터를 정렬되어 있는 리스트에서 어디에 들어가야 할지 판단하기 때문에 이중 반복문으로 O(n**2)의 복잡도를 가진다. 하지만 거의 정렬되어 있는 리스트에선 빠르게 동작한다.

퀵 정렬

기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다. 기준 데이터 = pivot

먼저 첫번째 데이터를 pivot으로 놓고 왼쪽으로 부터 pivot보다 큰 값을 선택하고 오른쪽으로 부터 pivot보다 작은 값을 선택하여 두 값의 위치를 바꾼다.

이때 저렇게 구한 두 값의 위치가 엇갈렸을 때 pivot과 작은 데이터의 위치를 바꾼다.

이제 pivot 기준으로 왼쪽 데이터들 중에서 다시 위와 같은 과정을 반복하면 전체 데이터에 대해서 정렬이 수행된다.

퀵정렬은 평균의 경우 nlogn의 시간 복잡도를 가진다.

보통 코테에서는 sort를 라이브러리로 사용하는데 파이썬 list에 내장되어 있는 sort는 퀵정렬이다.

그냥 sort쓰면 될 것 같다.