[Sort] 데이터 정렬에 대한 정리
arr = [35,33,42,10,14,19,27,44,26]
def quick_sort(arr,start,end):
if start >= end: # 원소가 1개인 경우 종료
return
pivot = start # 피벗은 첫번째 원소
left = start + 1
right = end
while left <= right:
# 피벗보다 큰 데이터를 찾을 때까지 반복
while left <= end and arr[left] <= arr[pivot]:
left += 1
# 피벗보다 작은 데이터를 찾을 때까지 반복
while right > start and arr[right] >= arr[pivot]:
right -= 1
if left > right: # 엇갈렸다면 작은 데이터와 피벗 교체
arr[right], arr[pivot] = arr[pivot], arr[right]
else: # 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
arr[left], arr[right] = arr[right], arr[left]
# 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 하기
quick_sort(arr, start, right - 1)
quick_sort(arr, right+1, end)
quick_sort(arr,0,len(arr) - 1)
print(arr)정렬 카테고리 용도 :
🔎 데이터 정렬에 필요한 기법들을 정리하기 위함
📘 '이것이 취업을 위한 코딩테스트다' 책을 통해 공부하였습니다.
- 선택 정렬 (Selection Sort)
- 삽입 정렬 (Insertion Sort)
- 퀵 정렬 (Quick Sort)
- 계수 정렬 (Count Sort)
정렬(Sort)이란?
데이터를 특정한 기준에 따라서 순서대로 나열하는 것
(프로그램을 작성할 때 가장 많이 사용되는 알고리즘 입니다.)
- 선택 정렬 (Selection Sort)
데이터가 무작위로 여러 개 있을 때, 이 중에서 가장 작은 데이터를 선택해
맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째
데이터와 바꾸는 과정을 반복하는 것. (매번 가장 작은 것은 선택)
[동작 과정]
출처 - https://en.wikipedia.org/wiki/Selection_sort
[소스 코드]
arr = [8,5,2,6,9,3,1,4,0,7]
for i in range(len(arr)):
min_index = i
for j in range(i + 1, len(arr)):
if arr[min_index] > arr[j]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i] # 스와프(두 변수의 위치 변경)
print(arr)[시간 복잡도]
선택 정렬은 N - 1번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내게 됩니다.
또한 매번 가장 작은 수를 찾기 위해 비교 연산이 필요합니다.
따라서 구현 코드의 시간복잡도를 빅오 표기법으로 나타내면 O(N^2) 입니다
(데이터의 개수가 10,000개 이상이면 시간 초과가 날 수 있습니다!)
2. 삽입 정렬 (Insertion Sort)
"데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입하면 어떨까요?"
삽입 정렬은 특정한 데이터를 적절한 위치에 '삽입'한다는 의미에서 삽입 정렬 이라고 부릅니다.
더불어 삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에,
그 앞까지의 데이터는 이미 정렬되어 있다고 가정합니다.
[동작 과정]
출처 - https://en.wikipedia.org/wiki/Insertion_sort
[소스 코드]
arr = [6,5,3,1,8,7,2,4]
for i in range(1,len(arr)):
for j in range(i,0,-1): # 인덱스 i부터 1까지 감소하며 반복
if arr[j] < arr[j-1]: # 한칸씩 왼쪽
arr[j], arr[j-1] = arr[j-1], arr[j]
else:
break
print(arr)[시간 복잡도]
삽입 정렬의 시간 복잡도는 O(N^2)입니다.
앞서 설명한 선택정렬과 시간 복잡도가 같지만, 삽입 정렬의 경우
데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작합니다.
최선의 경우 O(N)의 시간복잡도를 가집니다.
3. 퀵 정렬(Quick Sort)
"기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸면 어떨까요?"
퀵 정렬은 기준(pivot)을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는
방식으로 동작합니다. (왼쪽 분할에는 피벗보다 작은 데이터가, 오른쪽 분할에는 피벗보다
큰 데이터가 위치됩니다.)
[동작 과정]
출처 - https://engineering.fb.com/2022/07/20/security/hermes-quicksort-to-run-doom/
[소스 코드]
arr = [35,33,42,10,14,19,27,44,26]
def quick_sort(arr,start,end):
if start >= end: # 원소가 1개인 경우 종료
return
pivot = start # 피벗은 첫번째 원소
left = start + 1
right = end
while left <= right:
# 피벗보다 큰 데이터를 찾을 때까지 반복
while left <= end and arr[left] <= arr[pivot]:
left += 1
# 피벗보다 작은 데이터를 찾을 때까지 반복
while right > start and arr[right] >= arr[pivot]:
right -= 1
if left > right: # 엇갈렸다면 작은 데이터와 피벗 교체
arr[right], arr[pivot] = arr[pivot], arr[right]
else: # 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
arr[left], arr[right] = arr[right], arr[left]
# 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 하기
quick_sort(arr, start, right - 1)
quick_sort(arr, right+1, end)
quick_sort(arr,0,len(arr) - 1)
print(arr)[시간 복잡도]
퀵 정렬의 평균 시간 복잡도는 O(NlogN)입니다. (최악 O(N^2))
|
데이터의 개수(N)
|
N^2(선택,삽입 정렬)
|
NlogN(퀵 정렬)
|
|
N = 1,000
|
1,000,000
|
10,000
|
|
N = 1,000,000
|
1,000,000,000,000
|
20,000,000
|
4. 계수 정렬(Count Sort) => 데이터의 크기 범위가 제한되어 정수 형태일 때만 사용가능
계수 정렬은 앞서 다룬 3가지 정렬 알고리즘 처럼 직접 데이터의 값을 비교한 뒤에
위치를 변경하며 정렬하는 방식이 아닙니다.!
일반적으로 별도의 리스트를 선언 후 그 안에 정렬에 대한 정보를 담는 방식입니다.
📌 계수 정렬의 조건은 아래와 같습니다
- 데이터의 크기 범위가 제한된 경우
- ex) 0이상 100이하 성적 데이터 정렬
2. 데이터가 양의 정수인 경우
3. 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않는 경우
[동작 과정]
출처 - https://medium.com/@manishsundriyal/counting-sort-in-javascript-abf976e66b8c
계수 정렬은,
1. 먼저 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록
하나의 리스트를 생성합니다.
2. 처음 리스트의 모든 데이터는 0이되도록 초기화 합니다.
3. 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시키면
계수정렬이 완료 됩니다.
.📢 결과적으로 리스트에는 각 데이터가 몇 번 등장했는지 그 횟수가 기록 됩니다.
[소스 코드]
# 모든 원소의 값이 0보다 크거나 같다고 가정
arr = [7,5,9,0,3,1,6,2,9,1,4,8,0,5,2]
# 모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화)
count = [0] * (max(arr) + 1)
for i in range(len(arr)):
count[arr[i]] += 1 # 각 데이터에 해당하는 인덱스 값 증가
for i in range(len(count)): # 리스트에 기록된 정렬 정보 확인
for j in range(count[i]):
print(i,end=' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력[시간 복잡도]
모든 데이터가 양의 정수인 상황에서 데이터의 개수를 N, 데이터중 최대값의 크기를 K
라고 할 때, 계수 정렬의 시간 복잡도는 O(N + K) 입니다.
🎊 이상으로 데이터 정렬에 대한 정리를 마치겠습니다.