정렬
데이터를 특정한 기준에 따라 순서대로 나열하는 것
선택 정렬
처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복
Step 0 : 처리되지 않은 데이터 중 가장 작은 '0'과 가장 앞 '7'와 교체
Step 1 : 처리되지 않은 데이터 중 가장 작은 '1'과 가장 앞 '5'와 교체
이를 반복한다 마지막은 제외해도 된다
python
array[i], array[min] = array[min], array[i] #이걸로 스왑가능c++
swap(array[i], array[j])선택 정렬의 시간 복잡도
N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야한다.
N + (N-1) + (N-2) + ... + 2
이는 O(N^2) 이라 할 수 있다.
삽입 정렬
처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입
일반적으로 선택보다 효율적 작동
Step0 : 첫 번째 데이터 '7'은 그 자체로 정렬이 되어 있다고 판단하고, 두 번째 데이터인 '5'가 어떤 위치로 들어갈지 판단 '7'의 왼쪽이나 오른쪽 두 가지 경우만 존재
매번 그렇게 왼쪽 데이터와 비교하여 위치를 이동시킨다.
삽입 정렬의 시간 복잡도
- O(N^2)이며,
삽입정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다.
최선의 경우 O(N)의 시간 복잡도 갖음
퀵 정렬
- 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법
- 일반적인 상황에서 가장 많이 쓰인다.
- 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 된다
- 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정
Step 0 : 현재 피벗의 값은 5, 왼쪽에서 부터 5보다 큰 데이터를 선택 하므로 7이 선택 오른쪽에서부터 5보다 작은 데이터를 선택하므로 4가 선택 이제 이 두 데이터 서로 변경
Step 1 : 이 과정을 반복하다가 위치가 엇갈리는 경우 '피벗'과 '작은 데이터'의 위치를 서로 변경한다
분할완료 왼쪽은 5보다 작고 오른쪽은 5보다 크다 이렇게 피벗을 기준으로 데이터 묶음을 나누는 작업을 분할이라 한다
왼쪽과 오른쪽을 따로 또 정렬한다
퀵정렬 시간복잡도
최소O(NlogN)이고 최대 O(N^2)이다 왜냐하면 이미 정렬되어 있다면 왼쪽 큰값 선택하고 오른쪽 자기자신보다 작은 수가 자기자신 밖에 없기에 위치가 그대로 된다
계수 정렬
- 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 알고리즘
- 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때
- 데이터의 개수가 N, 데이터(양수) 중 최댓값이 K일 때 최악의 경우에도 O(N+K)를 보장
Step 0: 가장 작은 데이터부터 가장 큰 데이터까지의 범위가 모두 담길 수 있도록 리스트를 생성
정렬할 데이터 : 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2
Step 1: 데이터를 하나씩 확인하며 데이터 값과 동일한 인덱스의 데이터를 1씩 증가
처음 정렬할 데이터가 7이기에 인덱스 7에 1증가
Step 2: 최종 리스트에 각 데이터가 몇 번씩 등장했는지 기록
이후 리스트에 인덱스마다의 개수 만큼 출력한다
계수 정렬 복잡도
- 시간 복잡도와 공간 복잡도 모두 O(N+K)이다
<K는 데이터 중에 가장 큰 값> - 계수 정렬은 때에 따라서 심각한 비효율성을 초래
- 데이터가 0과 999,999단 두개 존재하지만 0~999,999까지를 담는 배열을 만들어야 한다. - 동일한 값을 가진 데이터가 여러 개 등장할 때 효과적(성적 정렬)
