정렬(Sorting)은 말 그대로 데이터를 특정한 기준에 따라 순서대로 나열하는 것을 의미한다.
오름차순이라면 점점 커지게, 내림차순이라면 점점 작아지게 나열을 하도록 만들면 된다.
정렬 알고리즘은 정말 다양하게 존재한다.
아래의 알고리즘 설명은 모두 오름차순을 기준으로 설명한다.
1. 선택 정렬 (Selection Sort)
데이터 중에서 가장 작은 데이터를 선택해서 맨 앞에 있는 데이터와 바꾸는 것을 반복하는 알고리즘이다. 최솟값을 계속해서 앞으로 가져오는 걸 반복한다고 생각하면 이해가 더 쉽다.
처음에는 전체의 최솟값인 0과 7의 위치를 바꿔준다.
그 다음 맨 앞은 최솟값임을 확정지었으니 나머지 9개의 최솟값을 또 확정지어서 2번째 원소로 가져온다.
그래서 나머지 9개의 원소들 중 최솟값인 1을 5와 위치를 바꿔준다.
이 과정을 계속해서 반복해나가는 것이다.
범위를 계속해서 좁혀가면서 최솟값을 가져와서 하나씩 쌓아가는 방식이다.
이를 코드로 구현하면 아래와 같다.
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]최솟값을 전체 배열의 크기만큼 찾아줘야 하므로 크게 반복문을 감싼다.
반복문이 진행해감에 따라 i가 시작점이 바뀌는 역할을 하여 그 뒤에 결정되지 않은 나머지 원소들에 대하여 반복문을 한 차례 더 수행한다.
두번째 반복문은 최솟값을 가진 인덱스를 찾는 과정이고 그 다음 최솟값 인덱스를 찾으면 swap을 해주어 최솟값이 앞에 오도록 한다.
2. 삽입 정렬 (Insertion Sort)
데이터를 하나씩 돌면서 적절한 순서를 찾아주는 과정이다.
처음에 7과 5를 비교하여 5의 위치를 찾아주는 것이다. 5는 7보다 작으므로 7의 왼쪽에 위치해야 한다. 따라서 둘의 위치를 바꿔준다.
그다음 9의 위치를 찾아준다. 9는 7보다 크므로 7의 오른쪽에 위치해야한다. 따라서 위치를 그대로 유지한다.
다음 0의 위치를 찾아준다. 0은 9보다 왼쪽에 있으므로 먼저 스왑을 한 번 해주고 그다음 7이랑도 비교한다.
7이랑 비교했을 때도 왼쪽에 있어야하므로 또 스왑을 해준다.
5랑 비교했을 때도 왼쪽에 있어야하므로 또 스왑을 해주어 가장 왼쪽에 오도록 한다.
이 과정을 각 원소에 대하여 계속 반복하는 것이다.
이를 코드로 구현하면 아래와 같다.
for i in range(1, len(array)):
for j in range(i,0,-1):
if array[j]<array[j-1]:
array[j], array[j-1] = array[j-1],array[j]
else:
break2번째 원소부터 배열의 끝까지 반복문을 돌 수 있도록 크게 감싼다.
그 다음 앞에서 결정된 배열들에 대하여 인덱스가 하나씩 감소하여 실행할 수 있도록 반복문을 구성한다.
예를 들어 위에서 0의 위치를 구하는 걸 생각해보면 0,1,2 인덱스는 이미 순서가 확정된 배열이므로 그 부분들에 대해서 2번 인덱스 -> 1번 인덱스 -> 0번 인덱스 순서로 비교를 해주었다. 그래서 점점 인덱스가 감소하는 방식으로 반복문을 구성하였다.
그리고 대소 비교를 하여 값이 작을 경우 왼쪽에 올 수 있도록 스왑을 해주고 만약 값이 크다면 오른쪽에 그냥 두면 되므로 반복문을 바로 탈출할 수 있도록 한다.
3. 퀵 정렬 (Quick Sort)
기준 데이터를 Pivot으로 설정하고 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 알고리즘이다.
위의 그림에서 첫번째 원소인 5가 기준이 된다.
그 다음 왼쪽, 오른쪽에서 하나씩 차례대로 검사를 한다.
왼쪽에서는 5보다 큰 7이 선택되고 오른쪽에서는 5보다 작은 데이터인 4를 선택한다.
그리고 둘의 위치를 바꿔준다.
또 왼쪽에서는 5보다 큰 데이터가 있는지 확인하고 오른쪽에서는 5보다 작은 데이터가 있는지 확인한다.
왼쪽에서는 9가, 오른쪽에서는 2가 선택되어 둘의 위치를 바꿔준다.
그렇게 검사를 진행하다보면 오른쪽의 포인터와 왼쪽의 포인터가 엇갈리게 된다.
이 때는 Pivot을 기준으로 그룹 나누기를 완료한 것으로 간주한다.
그래서 1과 5의 위치를 바꿔주어 5의 왼쪽에는 5보다 작은 값들이 있도록, 오른쪽에는 5보다 큰 값들이 있도록 한다.
그렇다면 5의 위치는 결정이 된 것이다.
왼쪽 그룹에 대해서 또 퀵 정렬을 수행하고 오른쪽 그룹도 마찬가지로 또 퀵 정렬을 수행한다.
이 논리를 들었을 때 바로 이 생각이 들어야 한다.
"아 재귀구나"
퀵 정렬을 코드로 구현하면 아래와 같다.
def quick_sort(array,start,end):
if start>=end:
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[left],array[right] = array[right], array[left]
quick_sort(array,start,right-1)
quick_sort(array,right+1,end)
quick_sort(array, 0, len(array)-1)재귀적으로 수행하야함으로 예상했기 때문에 탈출 조건을 먼저 써준다. 탈출 조건은 배열의 길이가 1이하일 때이다.
pivot값은 맨 처음 값, 포인터 두개는 pivot 다음 위치과 배열의 오른쪽 끝 위치로 설정을 해준다.
두 포인터가 엇갈리기 전까지 정렬을 수행하도록 한다.
왼쪽 포인터가 값을 검사하는데 만약 pivot값보다 작으면 굳이 스왑을 하지 않아도 된다. 따라서 포인터를 오른쪽으로 한 칸 이동한다.
같은 방식으로 오른쪽 포인터는 pivot값보다 클 경우 스왑을 할 필요가 없기 때문에 이 경우 포인터를 왼쪽으로 한 칸 이동한다.
두 개의 while문을 거치면서 왼쪽 포인터는 pivot보다 큰 값을, 오른쪽 포인터는 pivot보다 작은 값을 선택했을 것이다.
만약 포인터가 서로 엇갈리지 않았다면, 즉, 퀵 정렬의 마지막 연산에 도달하지 않았다면 선택된 두 개의 값을 스왑한다.
만약 엇갈려있다면 작은값과 pivot값의 위치를 바꿔준다. -> right가 left보다 왼쪽에 있는 상황이기 때문에 작은 값을 가리킨다.
그리고 이걸 왼쪽 그룹, 오른쪽 그룹에 대해서 재귀적으로 계속 수행해주면 된다.
사실 개인적으로 이 코드는 한 눈에 파악하기에는 조금 어렵다고 생각이 든다.
파이썬의 문법을 활용하여 더 간단하게 코드를 작성할 수도 있다.
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]
right_side= [x for x in tail if x>pivot]
return quick_sort(left_side) + [pivot] + quick_sort(right_side)마찬가지로 원소의 개수가 1개 이하가 될 때까지 재귀적으로 함수를 실행한다.
다만 pivot의 왼쪽 그룹, 오른쪽 그룹을 리스트 내의 반복문 선언으로 더 간단하게 표현이 가능하다.
위의 코드가 훨씬 더 직관적으로 이해가 된다고 생각한다.
4. 계수 정렬 (Counting Sort)
상황에 따라 매우 빠르게 정렬할 수 있는 알고리즘이다.
데이터의 크기 범위가 제한되어 정수 형태일 때 사용이 가능하다.
중복도 포함되어 있는 데이터가 있다고 가정했을 때 최댓값까지의 인덱스를 가지는 리스트에 인덱스를 활용하여 개수를 count하는 방식이다.
개수를 다 count하면 위와 같이 셀 수 있고 이를 차례대로 출력하면 끝이다.
0 0 1 1 2 2 3 4 5 5 6 7 8 9 9
이러면 정렬 끝이다.
코드 구현 또한 간단하다.
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=" ")최댓값까지의 인덱스를 가지는 배열을 선언하고 그 다음 반복문을 한 번 돌면서 각 인덱스에 개수를 세어준다.
그다음 마지막 출력은 count 배열을 돌면서 개수만큼 출력해주면 끝이다.
지금 가지 4개의 정렬 알고리즘을 살펴보았는데 각각의 알고리즘에 대하여 시간복잡도, 공간복잡도와 간단한 특징을 알아보자.
선택정렬과 삽입 정렬은 반복문이 이중으로 중첩되어있는 것만 보아도 O(n^2)임을 바로 이해할 수 있다.
퀵 정렬 같은 경우
이런식으로 그룹이 양쪽으로 나눠지면서 알고리즘이 진행되기 때문에 O(NlogN)의 시간복잡도를 가지는 것을 확인할 수 있다.
계수 정렬은 인덱스의 상수값에 따라 시간복잡도 그리고 빈 배열의 선언을 해줘야하기 때문에 공간복잡도도 조금 커진다.
기본적으로 파이썬 언어에 내장되어있는 정렬 라이브러리는 O(NlogN)의 시간 복잡도를 보장하도록 설계되어있기 때문에 sort()를 쓰면 가
장 빠른 정렬을 할 수 있다고 봐도 무방할 것 같다.
위에서 언급된 정렬 알고리즘 외에도 Merge Sort, Bubble Sort 등등 다양한 정렬 알고리즘이 있으니 살펴봐도 좋을 것 같다.
예제
처음 든 생각
- A에서 작은 놈들을 빼고 B에서 큰 놈들을 대신 더해주면 되겠네
- 정렬을 시키고 순서대로 하나씩 빼주고 더해주면 되겠다.
나의 답
n,k = map(int,input().split(" "))
arrA = list(map(int, input().split(" ")))
arrB = list(map(int, input().split(" ")))
arrA.sort()
arrB.sort()
for i in range(k):
arrA[i], arrB[len(arrB)-1-i] = arrB[len(arrB)-1-i], arrA[i]
sum = 0
for i in arrA:
sum+=i
print(sum)정렬 후에 A에서는 앞에서부터 하나씩 B에서는 뒤에서부터 하나씩 순서를 바꿔주고 다음 최종합을 구해주는 방식으로 코드를 구성했다.
하지만 이 코드는 결함도 있고 단정하지 못한 것 같아 수정을 하였다.
수정 답안
n,k = map(int,input().split(" "))
arrA = list(map(int, input().split(" ")))
arrB = list(map(int, input().split(" ")))
arrA.sort()
arrB.sort(reverse=True)
for i in range(k):
if arrA[i] <= arrB[i]:
arrA[i], arrB[i] = arrB[i], arrA[i]
sum = 0
for i in arrA:
sum+=i
print(sum)스왑하고자 하는 원소의 크기를 비교해주는 로직이 빠져있다. A에 있는 원소가 더 크다면 굳이 바꿔줄 이유가 없기 때문이다.
또한 가독성을 위해 B의 배열을 내림차순으로 정리하였다. 그러면 A와 B가 같은 인덱싱을 통해 문제를 해결할 수 있기 때문에 코드가 훨씬 이해하기 쉬워졌다.
정렬은 원리에 대한 이해가 가장 중요할 것 같다.
각 알고리즘이 어떤 순서대로 동작하는지 어떤 걸 기준으로 움직이는지를 자세히 보면서 복습하면 좋을 것 같다.
'스터디 > 코딩테스트' 카테고리의 다른 글
| python 코딩테스트 - 프로그래머스 카펫 (2) | 2023.11.12 |
|---|---|
| python 코딩테스트 - 소수 찾기 (0) | 2023.11.12 |
| python 코딩테스트 - 베스트 앨범 (0) | 2023.11.07 |
| python 코딩테스트 - 주식가격 (0) | 2023.11.06 |
| python 코딩테스트 - 의상 (0) | 2023.11.06 |