정렬(sorting)이란
데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다.(ex. 오름차순, 내림차순)
정렬 알고리즘으로 데이터를 정렬하면 다음장에서 배울 이진탐색(binary search)가 가능해진다. 정렬 알고리즘은 이진탐색의 전처리 과정이라고도 볼 수 있다.
코딩테스트를 대비하기 위해선 크게 5가지 정렬 방법에 대해서 알고 있으면 좋다!
선택정렬 / 삽입정렬 / 퀵정렬 / 계수정렬 / 파이썬 기본 라이브러리 정렬
정렬 알고리즘은 알고리즘 전공 시간때 배운바 있는데, 그때는 c++ 위주로 알고리즘 의사코드를 통해 공부를 했었다.(중간고사 대비를 위해 pseudocode 전체를 외웠던 악몽이...) 그 기억을 떠올려보면서 python에서의 코드 구현에는 어떤 이점이 있는지 알아보고 싶은 욕구가 샘솟는다!
선택정렬
매번 '가장 작은 것을 선택한다'는 의미의 선택정렬(Selection Sort) 알고리즘은 가장 작은 것을 선택하고 앞으로 보내는 과정을 반복해서 수행하다 보면 전체 데이터의 정렬이 이루어지는 알고리즘이다.
정렬을 이해하기 위해선 그림이 가장 좋은 방법인것 같기에 내가 공부하는 책의 그림을 참고로 가지고 와봤다!
#선택정렬 (가장 작은 수를 선택해서 정렬한다)
array = [7,5,9,0,3,1,6,2,4,8]
for i in range(len(array)):
min_index = i #가장 작은 원소의 인덱스
for j in range(i+1, len(array)):
if array[min_index] > array[j]:
min_index = j
array[i], array[min_index] = array[min_index], array[i]
print(array)코드를 보면 알겠지만 선택 정렬의 시간복잡도는 O(n^2)이다. 소스코드상으로 간단한 형태의 2중 반복문이 사용되었기 때문이다.
삽입정렬
'데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입'하는 삽입 정렬(Insertion Sorting)은 선택 정렬에 비해 실행 시간 측면에서 더 효율적인 알고리즘이다. 특히 삽입 정렬은 필요할 때만 위치를 바꾸므로 '데이터가 거의 정렬 되어 있을때' 훨씬 효율적이다.
삽입 정렬은 특징이 있다! 그것은 바로 정렬이 이미 이루어진 원소는 항상 오름차순을 유지하고 있다는 점이다!
위의 그림을 보면 하늘색으로 칠해진 카드들은 어떤 단계든지 항상 정렬된 상태를 유지한다. 이러한 특징 때문에 삽입 정렬에서는 특정하 ㄴ데이터가 삽입될 위치를 선정할 때(삽입된 위치를 찾기 위하여 왼쪽으로 한 칸씩 이동할 때), 삽입될 데이터보다 작은 데이터를 만나면 그 위치에서 멈추면 된다.
#삽입정렬
array = [7,5,9,0,3,1,6,2,4,8]
for i in range(1, len(array)):
for j in range(i, 0, -1): #인덱스 i부터 1까지 감소하며 반복하는 문법
if array[j] < array[j-1]: #한 칸씩 왼쪽으로 이동
array[j], array[j-1] = array[j-1], array[j],
else:
break
print(array)
삽입 정렬의 시간복잡도는 O(N^2)인데, 선택 정렬과 마찬가지로 반복문이 2번 중첩되어 사용되었다. 하지만 선택정렬과 다르게 최선의 경우(리스트의 데이터가 거의 정렬이 되어있는경우)는 O(N)의 시간복잡도를 가진다. 퀵 정렬과 비교했을때도, 이미 데이터가 거의 정렬되어있는 경우에는 삽입 정렬이 더 강력할 수 있다.
퀵 정렬
퀵 정렬은 지금까지 배운 정렬 알고리즘 중에 가장 많이 사용되는 알고리즘이다. 퀵 정렬은 이전 정렬들과 다르게 "빠른 정렬 알고리즘"이라고 볼 수 있다.
'기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸'는 퀵 정렬 알고리즘은 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 '기준'으로 피벗(Pivot)을 사용한다.
피벗을 설정하고 리스트를 분할하는 방법에 따라서 여러 가지 방식으로 퀵 정렬을 구분하는데, 그중 나는 가장 대표적인 호어분할방식을 기준으로 퀵 정렬을 공부하였다.
#퀵정렬, 직관적인 형태의 소스코드
array = [5,7,9,0,3,1,6,2,4,8]
def quick_sort(array, start, end):
if start >= end: #원소가 1개인 경우 종료
return
pivot = start #피벗은 첫번째 원소
left = start +1
right = end
while left <= right:
#피벗보다 큰 데이터를 찾을 때까지 반복
while left <= end and array[left] <= array[pivot]:
left +=1
#피벗보다 작은 데이터를 찾을 때까지 반복
while right > start and array[right] >= array[pivot]:
right -=1
if left > right: #엇갈렸다면 작은 데이터와 피벗을 교체
array[right], array[pivot] = array[pivot], array[right]
else : #엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
array[right], array[left] = array[left], array[right]
#분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
quick_sort(array, start, right-1)
quick_sort(array, right+1, end)
quick_sort(array,0,len(array)-1)
print(array)#파이썬의 장점을 살린 퀵 정렬 소스코드
array = [5,7,9,0,3,1,6,2,4,8]
def quick_sort(array):
#리스트가 하나 이하의 원소만을 담고 있다면 종료
if len(array) <=1:
return array
pivot = array[0] #피벗은 첫번째 원소
tail = array[1:] #피벗을 제외한 리스트
left_side = [x for x in tail if x<= pivot] #분할된 왼쪽 부분
# print(f"left_side: {left_side}")
right_side = [x for x in tail if x>pivot] #분할된 오른쪽 부분
# print(f"right_side: {right_side}")
#분할 이후 왼쪽부분과 오른쪽부분에서 각각 정렬을 수행하고, 전체 리스트를 반환
return quick_sort(left_side) + [pivot] + quick_sort(right_side)
print(quick_sort(array))
퀵 정렬의 평균적인 시간 복잡도는 O(NlogN)이다.
하지만 퀵 정렬 최악의 경우 시간 복잡도가 O(N^2)이다. 퀵정렬은 데이터가 무작위로 입력된 상황에서는 매우 빠르게 동작할 확률이 높지만, 이미 데이터가 정렬되어 있는 경우에는 매우 느리게 동작한다.
계수 정렬
특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다. 계수정렬은 최악의 경우에도 수행시간 O(N+K)를 보장한다.
일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다.
결과적으로 위와 같이 리스트에는 각 데이터가 몇번 등장했는지 그 횟수가 기록된다.
#계수 정렬
#모든 원소의 값이 0보다 크거나 같다고 가정
array = [7,5,9,0,3,1,6,2,9,1,4,8,0,5,2]
#모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화)
count=[0]*(max(array)+1)
for i in range(len(array)):
count[array[i]] += 1 #각 데이터에 해당하는 인덱스의 값 증가
for i in range(len(count)): #리스트에 기록된 정렬 정보 확인
for j in range(count[i]):
print(i, end=' ') #띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력계수정렬은 동일한 값을 가지는 데이터가 여러 개 등장할 때 적합하다.
파이썬의 정렬 라이브러리
파이썬은 기본 정렬 라이브러리인 sorted()함수를 제공한다.
sorted()함수는 퀵 정렬과 동작 방식이 비슷한 병합 정렬을 기반으로 만들어졌는데, 병합정렬의 경우 퀵 정렬보다는 느리지만 최악의 경우에도 시간 복잡도 O(NlogN)을 보장한다는 특징이 있다.
sorted() 함수는 리스트, 딕셔너리 자료형 등을 입력받아서 정렬된 결과를 출력한다. 집합 자료형이나 딕셔너리 자료형을 입력 받아도 반환되는 결과는 리스트 자료형이다.
sort()함수를 이용하면 별도의 정렬된 리스트가 반환되지 않고 내부 원소가 바로 정렬된다.
또한 sorted()나 sort()를 이용할 때에는 key 매개변수를 입력으로 받을 수 있다. key 값으로는 하나의 함수가 들어가야 하며 이는 정렬 기준이 된다. 예를 들어 리스트의 데이터가 튜플로 구성되어 있을 때, 각 데이터의 두번째 원소를 기준으로 설정하는 경우 다음과 같은 형태의 소스 코드를 작성할 수 있다.
array = [('바나나',2), ('사과',5), ('당근',3)]
def setting(data):
return data[1]
result = sorted(array, key=setting)
print(result)결과:
[('바나나',2), ('당근',3), ('사과',5)]
코딩테스트에서 정렬 알고리즘이 사용되는 경우는 일반적으로 3가지 문제 유형으로 나타낼 수 있다.
1. 정렬 라이브러리로 풀 수 있는 문제
2. 정렬 알고리즘의 원리에 대해서 물어보는 문제
3. 더 빠른 정렬이 필요한 문제
자 이제 실전 문제를 풀어보자..!!
실전문제
정답👇🏻👇🏻👇🏻(더보기를 눌러주세용)
#위에서 아래로, 솔아답안1
n = int(input())
arr = []
for i in range(n):
num = int(input())
arr.append(num)
for j in range(len(arr)):
a_max = 0
for i in range(len(arr)):
if a_max < arr[i]:
a_max = arr[i]
print(a_max, end=' ')
arr.remove(a_max)
#위에서 아래로, 솔아답안2
n = int(input())
arr = []
for i in range(n):
num = int(input())
arr.append(num)
arr.sort(reverse=True) #내림차순
for i in range(len(arr)):
print(arr[i], end=' ')
정답👇🏻👇🏻👇🏻(더보기를 눌러주세용)
#성적이 낮은 순서로 학생 출력하기, 솔아답안1
n = int(input())
scores =[]
names = []
for i in range(n):
name, score = map(str, input().split())
names.append(name)
scores.append(int(score))
for j in range(len(scores)):
min_score = 101
min_index = 0
for i in range(len(scores)):
if min_score > scores[i]:
min_score = scores[i]
min_index = i
print(names[min_index])
scores.remove(min_score)
names.remove(names[min_index])
#성적이 낮은 순서로 학생 출력하기, 답안
n = int(input())
array =[]
for i in range(n):
input_data = input().split()
#이름은 문자열 그대로, 점수는 정수형으로 변환하여 저장
array.append((input_data[0],int(input_data[1])))
#key를 이용하여, 점수를 기준으로 정렬
array = sorted(array, key=lambda student: student[1]) #이 문법은 뭐여..ㄷㄷ
#정렬이 수행된 결과를 출력
for student in array:
print(student[0], end=' ')
이 문제에서는 학생 정보가 최대 100,000개까지 입력될 수 있으므로 최악의 경우 O(NlogN)을 보장하는 알고리즘을 이용하거나 O(N)을 보장하는 계수 정렬을 이용하면 된다.
이 문제는 학생정보를 (이름, 점수)로 묶은 뒤에 점수를 기준으로 수행해야한다. 고로 파이썬의 기본 정렬 라이브러리를 사용하는 것이 효과적이다.
정답👇🏻👇🏻👇🏻(더보기를 눌러주세용)
#두 배열의 원소 교체, 솔아답안1
n, k = map(int,input().split())
arr1 = list(map(int,input().split()))
arr2 = list(map(int,input().split()))
arr1.sort() #오름차순
arr2.sort(reverse=True) #내림차순
for i in range(k):
if arr1[i] < arr2[i]:
arr1[i], arr2[i] = arr2[i], arr1[i] #swap
else:
break
print(sum(arr1))
이상으로 정렬파트 게시물 마무리하겠습니다~ 글 읽어주셔서 정말 감사드립니다!
% 해당 글은 "이것이 코딩테스트다. (나동빈 저)" 를 공부하며 정리해놓은 게시글입니다! %
'CS+PS > Algorithm' 카테고리의 다른 글
| [알고리즘] 이진탐색 (범위가 큰 수라면.. 이진탐색이다!) (1) | 2023.11.14 |
|---|---|
| [파이썬]빠른 입출력 (0) | 2023.11.13 |
| [알고리즘] BFS/DFS (feat. stack, queue) (1) | 2023.10.11 |
| [C++] 연결리스트 (feat.바킹독) (0) | 2023.09.19 |
| [C++] 배열 (feat. 바킹독) (0) | 2023.09.13 |
