.gif&blockId=11b00c82-b138-8050-a58b-dcbceda2ef8f)
정렬
•
정렬 : 데이터를 특정 기준에 따라 순서대로 나열하는 것
정렬 알고리즘 | 평균 시간 복잡도 | 공간 복잡도 | 특징 |
선택 정렬 | O(N2) | O(N) | 아이디어가 매우 간단함 (,,) |
삽입 정렬 | O(N2) | O(N) | 데이터가 거의 정렬되어 있을 땐 가장 빠름 |
퀵 정렬 | O(NlogN) | O(N) | 대부분의 경우에 가장 접합하며, 충분히 빠름 |
계수 정렬 | O(N+최댓값) | O(N+최댓값) | 데이터의 크기가 한정되어 있는 경우에만 사용이 가능하지만 매우 빠르게 동작함 |
선택 정렬
•
처리 되지 않은 데이터 중 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것
◦
탐색 범위는 반복할 때마다 1개씩 감소
◦
마지막 데이터는 제외
•
앞에 있는 애로 뒤에 있는 애랑 비교
•
구현
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)
Python
복사
삽입(Insert) 정렬
•
처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입
•
선택 정렬에 비해 구현 난이도가 높지만, 일반적으로 더 효율적으로 동작
•
현재 리스트의 데이터가 거의 정렬되어 있는 상태일 때 매우 빠르게 동작
•
뒤에 있는 애로 앞에 있는 애랑 비교
•
구현
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):
if array[j] < array[j - 1]:
array[j], array[j - 1] = array[j - 1], array[j]
else:
break
print(array)
Python
복사
퀵(Quick) 정렬
•
기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법
•
일반적으로 가장 많이 사용
•
정렬이 안된 배열, 분할이 잘 되는 경우 빠름
•
동작
◦
첫 번째 데이터를 기준 데이터(Pivot)로 지정
◦
왼쪽으로부터 pivot보다 큰 값을 찾고, 오른쪽으로부터 pivot보다 작은 값을 찾아서 스왑
◦
위치가 엇갈리는 경우 pivot과 왼쪽 데이터(오른쪽에서 오던)의 위치 서로 변경
•
구현
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] #분할된 왼쪽 부분
right_side = [ x for x in tail if x > pivot] #분할된 오른쪽 부분
#분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행, 전체 리스트 반환
return quick_sort(left_side) + [pivot] + quick_sort(right_side)
print(quick_sort(array))
Python
복사
계수 정렬
•
특정 조건이 부합할 때 매우 빠르게 동작하는 정렬 알고리즘
•
데이터의 크기 범위가 제한되어 정수 형태로 표현 가능할 때 사용
•
데이터의 개수가 N, 데이터(양수) 중 최댓값이 K일 때 최악의 경우에도 수행시간 O(N+K)를 보장
•
계수 정렬은 동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적
•
0과 999,999의 2개만 존재하는 리스트를 정렬한다면 비효율적
•
B의 배열길이는 A에 있는 최댓값에 따라 결정
•
동작
◦
origin, indexCount, sorted 리스트를 만들고
◦
indexCount[origin 리스트의 값]에 값의 개수만큼 카운트를 올려준다.
◦
indexCount의 값들을 1부터 마지막 값까지 바로 이전 값과 계속 더하여 누적합으로 만든다.
◦
indexCount을 바탕으로 sorted 정렬
•
구현
array = [5,7,9,0,3,1,6,2,4,8]
count = [0] * (max(array) + 1) # 0부터 9까지 존재하기 때문
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=' ') #띄어쓰기 구분
Python
복사
