42. PYTHON - 정렬 알고리즘

버블 정렬

버블 정렬은 가장 간편하지만 속도가 가장 느린 정렬 알고리즘이다. 버블 정렬은 비눗방울이 공중에 서서히 떠오르듯 리스트 안에서 가장 큰 값을 반복적으로 옮긴다. 최악의 경우 버블 벙렬의 시간 복잡도는  O(N^2)이므로 되도록 작은 데이터셋에만 사용하는 것이 좋다.

 

버블 정렬의 작동원리 이해

버블 정렬은 pass라는  과정을 반복한다. 리트스의 크기가 N일 때 버블 정렬의 패스 개수는 N-1개이다. 

버블 정렬의 성능 분석

버블 정렬은 두 개의 루프로 구성되어 이다.

• 외부루프 : 패스를 의미합니다. 예를 들어, 첫 번째 패스는 외부 루프를 처음 1회 실행하는 것과 같다..
• 내부 루프 : 패스 내에서 가장 높은 값을 오른쪽으로 이동시킬 때까지 값들을 반복적으로 비교하는 과정이다. 첫 번째 패스는 총 N-1번을, 두 번째 패스는 N-2번을 반복하는 식으로 패스 횟수가 올라감에 따라 값을 비교하는 횟수가 하나씩 줄어든다.

두 개의 루프가 중첩되어 있기 때문에 최악의 경우 버블 정렬의 시간 복잡도는 O(n^2)이다.

삽입정렬

삽입 정렬의 기본 아이디어는 자료 구조에서 데이터 포인트를 하나씩 빼내어 올바른 위치에 집어넣는 과정을 반복하는 것이다.

삽입정렬의 성능 분석

대상의 리스트가 이미 정렬된 상태라면 삽입 정렬은 매우 빠르게 동작한다. 이경우 시간복잡도는 O(n)이다. 이경우는 가장 이상적일 때이다. 반대로 리스트를 순회 할 때마다 모든요소를 옮겨야만 한다면 리스트의 개수만큼 이동해야한다. O(N^2)이 된다. 삽입정렬은 크기가 ㅈ가은 배열에서 사용된다. 규모 큰 배열에서는 사용하지 않는 것이 좋다.

 

병합 정렬

이 알고리즘의 특성은 성능이 입력 데이터의 정렬 여부와는 관계가 없다. 병합 정렬은 맵리듀스와 같은 빅데이터 알고리즘처럼 분할 및 정복 전략을 사용한다.

병합 정렬의 단계

1. 입력된 리스트를 크기가 같은 두 부분으로 나눈다.
2. 나뉜 부분의 크기가 1이 될 때까지 반복해서 분리한다.
3. 각 부분을 정렬한 뒤 병합하여 최종적으로 정렬된 리스트를 반환한다.

셀 정렬

바로 인접한 이웃 대신 고정된 거리만큼 서로 떨어진 데이터 포인트끼리 묶어 이들을 정렬한다.

셸 정렬의 성능분석

셸 정렬은 빅데이터 보다는 중간 규모의 데이터셋에 적합하다. 최대 6000개 요소가 담긴 리스트라면 셸 정렬이 꽤 괜찮은 성능을 발휘한다. 리스트가 어느정도 정렬된 경우에는 N개의 요소를 각각 한 번씩 검사하면 작업이 끝나기 때문에 시간 복잡도는 O(N)이다.

 

선택정렬

선택정렬은 필요한 교환 횟수를 최소화한 버블 정렬의 개량버전이라고 할 수 있다.

선택 정렬의 성능분석

선택 정렬의 시간 복잡도는 최악의 경우 O(N^2)이다. 이는 버블 정렬과 비슷하기 때문에 큰 데이터셋에는 사용하는것은 피해야한다. 그러나 선택정렬은 버블 정렬보다는 교환을 더 적게 하기 때문에 평균성능은 더 뛰어나다.