그동안 알고리즘 문제를 풀면서 정렬이 필요할 때면
열의 아홉은 사용하는 언어에서 이미 만들어진 함수를 가져다가 쉽게쉽게 구현을 해왔다.
그렇다보니 정작 필요할 때는 아무것도 쓰지 못하고 뇌정지가 와버려서 오늘부터 하나씩 정리를 하려고 한다.
오늘은 선택정렬을 파이썬 코드로 구현하는 방법과 파이썬에서 정렬을 수행해주는 함수도 같이 적어본다.
선택 정렬(Selection Sort)이란
- 원시적인 방법이며 가장 작은 수를 제일 앞쪽에 배치하는 정렬 알고리즘
- 이중 for문을 사용하기 때문에 시간복잡도는 O(N^2)
코드로 표현하기
- 배열에 저장된 모든 원소를 인덱스 순서대로 모두 조회한다.
- 내부 for문에서는 현재 인덱스부터 끝 인덱스까지 조회하여 가장 작은 값을 찾는다.
- 지역변수에 저장된 최솟값보다 작은 값이 있다면 현재 원소를 그 최솟값으로 변경한다.(temp)
코드에서는 최솟값을 저장하는 변수로 min_num 의 이름을 사용했다.
#오름차순 정렬 예제
arr = [1, 10, 5, 8, 7, 6, 4, 3, 2, 9] #임의의 원소 배열
idx = 0 #인덱스를 저장할 변수
for i in range(len(arr)):
min_num = 9999 #원솟값들보다 훨씬 큰 값으로 초기화 -> 비교값으로 첫 원소가 대입되도록 유도
for j in range(i, len(arr)):
if min_num > arr[j]:
min_num = arr[j]
idx = j
temp = arr[i]
arr[i] = arr[idx]
arr[idx] = temp
#결과 출력
for a in arr:
print(a, end=' ')
파이썬 정렬 함수를 알아보자
- List.sort()
- 리스트 자료형에 대해서만 사용이 가능한 정렬 함수
- 요소간의 단순히 크기비교로만 정렬하며 기존 리스트의 순서를 바꾼다. 즉, 반환값이 없고 원본 리스트가 변경된다.
이 함수에 옵션으로 key
, reverse=True
두가지 인자를 두는 것이 가능하다.
key는 각 원소를 특정 기준에 따라 정렬하고자 할 때 사용한다.
예1) a.sort(key=str.lower)
: 문자열의 시작이 소문자인 원소가 앞에 오도록 오름차순으로 정렬
예2) a.sort(key=len)
: 문자열의 길이가 작은 것부터 오름차순으로 정렬
reverse는 디폴트가 False이며 True값으로 명시해주면 내림차순으로 정렬할 수 있다.
리스트 자료형에만 적용될 수 있다는 한계를 풀어주는 것이 바로 sorted()
함수이다.
- sorted(Iterable 객체 [, key, reverse=True] )
- 모든 이터러블(Iterable) 자료형에 대해서 정렬 기능을 해주는 함수
- sort()와 달리 원본은 그대로 두고, 정렬되어 새롭게 만들어진 사본을 반환한다.
sorted() 또한 key
, reverse
매개변수를 사용할 수 있고, 사용법은 동일하다.
하지만 나는 key매개변수 사용법이 헷갈리기 때문에 예제를 몇 개 추가한다.
key매개변수에는 lambda 함수가 적용될 수 있는데 lambda 란, 이름이 없는 무명(Anonymous)함수를 의미한다.
다음과 같은 형식을 가지고 임의의 인자들(한개만 정의하는 것도 가능)에 대해 수식을 수행해준다.
lambda arg1, arg2:수식
이 lambda 함수는 map() 함수 내에서 또는 아래 예제처럼 정렬 시에 key 매개변수의 값으로 사용될 수 있다.
#튜플 내의 값을 기준으로 정렬하기
student_tuples = [
('john', 'A', 15),
('jane', 'B', 12),
('dave', 'B', 10),
]
sorted(student_tuples, key=lambda student: student[2]) #학생의 나이에 따라 정렬
#OUTPUT: [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)
#문자열 리스트를 정렬하기
sorted("This is a test string from Andrew".split(), key=str.lower)
#OUTPUT: ['a', 'Andrew', 'from', 'is', 'string', 'test', 'This']
#딕셔너리 정렬하기
sorted({1: 'D', 2: 'B', 3: 'B', 4: 'E', 5: 'A'})
#OUTPUT: [1, 2, 3, 4, 5]
참조문서
https://docs.python.org/ko/3/library/stdtypes.html#list.sort
https://docs.python.org/ko/3/howto/sorting.html
https://blog.naver.com/ndb796/221226800661