[WEEK02] 정렬 알고리즘

[Do it 자료구조와 함께 배우는 알고리즘 입문 with 파이썬] + [이것이 취업을 위한 코딩테스트다]  개념정리

 

정렬?

: 항목의 값을 대소 관계에 따라 데이터 집합을 일정한 순서로 바꾸어 늘어놓는 작업을 말함

: 오름차순 정렬 혹은 내림차순 정렬

: 안정적인 알고리즘 / 그렇지 않은 알고리즘으로 나눌 수 있음

: 교환 / 선택 / 삽입이 핵심

1. 단순 정렬 알고리즘

1) 버블 정렬 (Bubble Sort)

: 원소의 수가 n인 배열에서 n-1번 비교, 교환 하면 가장 작은 원소인 1이 맨 앞으로 이동함 (패스)

: 이러한 일련의 과정을 지속적으로 거쳐 정렬

: 알고리즘 개선방법 (Do it 참고)

: 시간복잡도 = O(n^2)

2) 셰이커 정렬 (Shaker Sort)

: 버블정렬을 개선한 알고리즘으로 홀수 패스에서는 가장 작은 원소를 맨 앞으로, 짝수 패스에서는 가장 큰 원소를 맨 뒤로 이동

: 시간복잡도 =

3) 단순 선택 정렬 (Straight Selection Sort)

: 가장 작은 원소부터 선택해 알맞은 위치로 옮기는 작업을 반복하며 정렬하는 알고리즘

: 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고 그 다음 똑같이 반복 (가장 원시적인 방법)

: 서로 떨어져 있는 원소를 교환하므로 안정적이지 않음 

: 시간복잡도 = O(n^2)

 

1) 아직 정렬하지 않은 부분에서 값이 가장 작은 원소를 선택함

2) 1)에서 선택한 원소와 아직 정렬하지 않은 부분에서 맨 앞에 있는 원소를 교환

4) 단순 삽입 정렬 (Straight Insertion Sort)

: 왼쪽부터 차례대로 확인하며 앞쪽의 원소보다 더 앞쪽에서 알맞은 위치로 삽입하며 정렬하는 알고리즘

: 아직 정렬되지 않은 부분의 맨 앞 원소를 정렬된 부분의 알맞은 위치에 삽입

: 특정한 데이터가 적절한 위치에 들어가기 이전에 그 앞까지의 데이터는 이미 정렬되어 있다고 가정하고 적절한 위치를 찾아 삽입

: 거의 정렬되어 있는 상태라면 매우 빠르게 동작함

: 시간복잡도 = O(n^2)

 

2. 개선된 정렬 알고리즘

1) 셸 정렬 (Shell Sort)

: 먼저 정렬할 배열의 원소를 그룹으로 나눠서 각 그룹별로 정렬을 수행

ex) 8개의 리스트 중 

      2개의 원소에서 4칸 떨어진 원소 간의 정렬을 수행

      4개의 원소에서 2칸 떨어진 원소 간의 정렬을 수행

      8개의 원소에서 1칸 떨어진 원소 간의 정렬을 수행

: 시간복잡도 = O(n^1.25)

2) 퀵 정렬 (Quick Sort)

: 리스트에서 첫번째 데이터를 피벗으로 정함

: 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾음 (엇갈리면 피벗과 작은데이터를 바꿈)

: 최종적으로는 왼쪽에는 피벗보다 작은 데이터가 위치하고 오른쪽에는 피벗보다 큰 데이터가 위치함

: (분할 (Divide) 혹은 파티션 (Partition)이라 부름)

: 호어 분할 (Hoare Partition)

: 원소 수가 2개 이상인 그룹에서 아래와 같이 정렬

 - 왼쪽 커서 (a[0]) 보다 pr이 오른쪽에 위치하면서 왼쪽 그룹을 나눔

 - 오른쪽 커서 (a[-1]) 보다 pl이 왼쪽에 위치하면서 오른쪽 그룹을 나눔

: 시간복잡도 = O(nlgn) / 최악의 경우 = O(n^2)

3) 병합정렬 (Merge Sort)

: 배열을 앞부분과 뒷부분 두 그룹으로 나누어서 각각 정렬 후 병합하는 작업을 반복

: 배열의 앞부분을 병합 정렬로 정렬 -> 배열의 뒷부분을 병합 정렬로 정렬 -> 배열의 앞부분과 뒷부분을 병합

4) 힙정렬 (Heap Sort)

: 힙에서 최댓값인 루트를 꺼내고 루트 이외의 부분을 힙으로 만드는 정렬

: 힙으로 만드는 과정

  1) 루트를 꺼냄

  2) 마지막 원소를 루트로 이동함

  3) 루트에서 시작해서 자신보다 값이 큰 자식과 자리를 바꾸고 아래쪽으로 내려가는 작업을 반복

: 시간복잡도 = O(nlgn)

5) 도수정렬 (Counting Sort)

: 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘

: 앞에서부터 데이터를 하나씩 확인 + 리스트 각 인덱스에 해당하는 값 확인할 때 데이터 중 최댓값만큼 반복

: 계수정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용 가능 (실수는 사용이 어려움)

: 일반적으로 가장 큰 데이터와 가장 작은 데이터 차이가 1,000,000을 넘지 않을때 효과적으로 사용 가능

: 때에 따라서는 비효율을 초래할 수 있는데 예를 들어서 0과 999,999 2개만 존재할 때

: 따라서 동일한 값을 가지는 데이터가 여러개 등장할 때 적합함

: 데이터의 크기 한정되어 있고 데이터의 크기가 많이 중복되어 있을 때!

: 최악의 경우에도 시간복잡도가 O(N + K)임 (데이터의 개수 : N, 데이터 중 최댓값 : K)

 

1단계 : 도수분포표 만들기

2단계 : 누적 도수분포표 만들기

3단계 : 작업용 배열 만들기

4단계 : 배열 복사하기