나동빈님의 '이것이 코딩테스트다 with 파이썬'저서와 유튜브 강의를 참고하며 작성하였습니다.
코드 출처: https://github.com/ndb796/python-for-coding-test
▶ 정렬이란?
데이터를 특정 기준으로 나열하는 것을 말한다. 문제에 따라 정렬 알고리즘이 달라지는데 그 알고리즘들 중 선택정렬, 삽입정렬, 퀵 정렬, 계수정렬에 대해 정리해보고자 한다.
▶ 선택정렬이란?
현재 탐색범위인 데이터에서 가장 작은 데이터를 선택해 맨 앞으로 보내고 맨 앞에 있던 데이터를 가장 작은 데이터가 있던 자리로 바꿈으로써 오름차순으로 정렬한다. 다른 정렬들에 비해선 시간 비효율적인 알고리즘이지만 코딩테스트에서 가장 작은 데이터를 찾는 문제가 자주 출제되기 때문에 숙지하고 있어야한다.
시간복잡도- 빅오표기법에 따르면 O(N^2)이다.
▷ 예시
4,3,2,1
- 범위: 4,2,3,1 가장 작은 수인 1을 4와 바꾼다 -> 1,3,2,4
- 범위: 3,2,4 현재 범위에서 가장 작은 수 인 2를 가장 앞에 위치한 3과 바꾼다 -> 1,2,3,4
- 범위: 3,4 현재 범위에서 가장 작은 수인 3이 이미 앞으로 나와있다.
- 마지막 수인 4는 따로 정렬해주지 않아도 가장 큰 수로 마지막에 남아있다.
▷ 구현
▶ 삽입 정렬이란?
처리되지 않은 데이터를 하나씩 골라 이전에 정렬된 요소들과 비교한 후 선후관계가 적절한 위치에 삽입한다. 선택정렬에 비해 구현은 어렵지만 시간효율적이다.
- 시간복잡도: 선택정렬과 마찬가지로 이중반복문이므로 O(n^2)이다. 현재 리스트가 대다수 정렬돼있는 상태면 매우 빠르게 동작할 수 있다.
▷ 예시
4,3,2,1
- 4가 이미 정렬된 데이터라고 생각해보자. 3을 골라 4와 비교해보았을 때 3은 4의 왼쪽 혹은 오른쪽으로 들어갈 수 있으나 4보다 작은 수 이기 때문에 4의 왼쪽으로 삽입된다. -> 3,4,2,1
- 2를 골라 4와 비교해보았을 때 작으므로 왼쪽으로, 이어서 3과 비교해보았을 때 3보다도 작기 때문에 최종적으로 3의 왼쪽으로 삽입된다. -> 2,3,4,1
- 1을 골라 4와 비교해보았을 때 왼쪽, 3과 비교해보았을 때 왼쪽, 2와 비교해보았을 때도 왼쪽이므로 최종적으로 가장 왼쪽에 1이 삽입된다. -> 1,2,3,4
▷ 구현
▶ 퀵 정렬이란?
데이터의 특성과 관련없이 표준적으로 많이 사용되는 정렬알고리즘이다. 기준 데이터(피벗이라 부름)를 설정하고 데이터의 왼쪽에서부터 피벗보다 큰 데이터를 찾고 오른쪽에서부터 피벗보다 작은 데이터의 위치를 찾아 서로 교환해준다. 그리고 만약 반대로 큰 데이터가 오른쪽에, 작은 데이터가 왼쪽에 있으면 작은 데이터와 피벗의 위치를 바꾼다. 이 과정까지 오면 원래 기준 데이터였던 피벗을 기준으로 왼쪽엔 피벗보다 작은 값이, 오른쪽엔 피벗보다 큰값들이 위치하게 된다. 이러한 작업을 분할(파티션)이라고 부른다. 분할 상태에서 각 왼쪽과 오른쪽 리스트를 별개로 피벗을 설정하고 퀵정렬을 동일하게 수행하다가 정렬을 수행하는 파티션의 리스트들의 원소가 하나일 때 정렬이 멈춰진다.
- 시간복잡도: 분할이 절반씩 일어나는 이상적인 퀵정렬의 경우 O(NlogN)의 시간복잡도를 가진다. 최악의 경우 O(N^2)의 시간복잡도를 가진다.
▷ 예시
4,3,2,1,5
- 4를 피벗으로 두었을 때 남은 데이터 중 왼쪽에서 4보다 큰 데이터를 탐색한다. 5이다. 오른쪽에서부터 4보다 작은 데이터는 1이다. 왼쪽과 오른쪽의 순서가 바뀌었으므로 1과 4의 위치를 바꾼다-> 1,3,2,4,5
- 4를 기준으로 왼쪽에 4보다 작은 값이, 오른쪽에 4보다 큰 값이 위치한다. 오른쪽의 경우 원소가 하나밖에 없으므로 퀵정렬을 수행하지 않는다. 왼쪽 리스트만 다시 퀵정렬을 수행한다. 피벗은 1로 잡는다. 남은 3,2중 왼쪽에서부터 1보다 큰 값은 3이고 오른쪽에서부터 1보다 작은 값은 오른쪽에서부터 탐색하여 자기자신인 1로 선택된다. 따라서 작은 수인 1과 피벗의 1의 위치가 같기 때문에 그대로 둔다. -> 1,3,2,4,5
- 마지막으로 3과 2 중 3을 기준으로 잡았을 때 작은 수인 2가 오른쪽에서부터 찾았을 때 선택되고 큰수는 3으로 피벗과 동일한 수로 선택된다. 따라서 작은 수인 2와 피벗인 3의 위치를 바꾼다 -> 1,2,3,4,5
- 이제 분할하기 위한 리스트 원소들이 하나씩 밖에 존재하지 않기 때문에 퀵정렬을 중단한다.
▷ 구현
▶ 계수정렬이란?
데이터의 크기 범위가 제한돼 정수형태로 표현할 수 있을 때만 수행가능하지만 매우 빠르게 작동하는 정렬이다. 즉 무한한 값이 존재할 수 있는 실수데이터의 경우엔 계수정렬을 사용할 수 없고 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다.
배열이 있을 때 배열의 가장 작은 데이터부터 가장 큰 데이터까지 수만큼의 리스트를 생성하고 그 리스트 안에는 해당 데이터가 몇 번 등장했는지 그 횟수가 기록된다. 그리고 출력 시, 리스트에 저장된 횟수만큼 리스트의 위치를 출력함으로써 정렬을 수행한다.
- 시간복잡도: N이 데이터의 개수, K가 데이터에서 최대값이라고 할때 O(N+K)이다. 데이터의 범위가 그리 크지 않고 데이터가 많이 반복되어있을수록 더욱 적합한 정렬방식이다.
- 공간복잡도: 데이터의 범위가 클 때 그 범위만큼의 리스트를 선언해야하기 때문에 심각한 비효율성을 초래할 수 있으므로 데이터 크기가 한정되어있을 때 사용하자
▷ 예시
4,4,3,1,1,2,0
- 0에서 4까지 5개 원소가 들어갈 수 있는 리스트를 선언한다. 초기값은 0이다. -> [0,0,0,0,0]
- 각 리스트의 위치에 해당하는 값들의 횟수를 리스트에 넣어준다. -> [1,2,1,1,2]
- 횟수만큼 리스트의 인덱스를 출력한다. -> 0,1,1,2,3,4,4
▷ 구현
▶ 네가지 정렬 비교
정렬 라이브러리는 최악의 경우에도 O(NlongN)의 시간복잡도롤 보장하기 때문에,
일반적으로 문제에서 정렬알고리즘의 풀이를 요구하지 않는다면 정렬 라이브러리를 사용하는 것이 편리하다.
▶ 정렬 라이브러리
- sort(): 리스트 객체의 내장함수로 별도로 정렬된 리스트를 반환하진 않고 리스트 내부의 원소들을 바로 정렬할 수 있다.
- sorted(): 리스트의 원소들을 정렬한 후 그 결과를 반환한다.
- 두 함수모두 key매개변수를 입력 받아 정렬의 기준이 되는 원소를 설정할 수 있다.
'python > 알고리즘 문제풀이' 카테고리의 다른 글
| [프로그래머스 | 파이썬3] 이진탐색 (2) / 입국심사 (0) | 2021.07.01 |
|---|---|
| 이진탐색 (1) (0) | 2021.06.30 |
| [프로그래머스 | 파이썬] 기능개발- 큐사용 (0) | 2021.06.29 |
| [프로그래머스 | 파이썬] BFS와 DFS (4)/ 타겟넘버, 네트워크 (0) | 2021.06.29 |
| BFS와 DFS (3)/ BFS와 DFS 정의와 구현 (0) | 2021.06.28 |