반응형
안녕하세요~!
27년차 진로탐색꾼 조녁입니다.
코딩테스트를 풀어도 계속 막히는 저를 보며 .. 인적성을 처음 무작정 풀다가 책을 던졌던 그 때가 떠올랐습니다 ..허허
그때 유튜브에서 봉봉TV 찾아서 개념공부하고 적용시키면서 푸니까 많이 늘었던 기억이 있어서 !!
본격적으로 알고리즘 이론 공부를 해볼까합니다. 오늘은 첫번째로 "정렬"에 대해서 공부해봤습니다.
정렬이란 , 데이터를 특정한 기준에 따라 순서대로 나열하는 것을 말합니다.
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) #[0,1,2,3,4,5,6,7,8,9]
- 시간복잡도는 빅오 표기법에 따라 O(N^2)입니다.
*빅오 표기법은 최고차항만 남기는 것, 이 때 계수도 무시된다.
2. 삽입 정렬 : 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입합니다. 일반적으로 선택정렬보다 더 효율적이다.
#예시코드
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까지 1씩 감소하며 반복하는 문법
if array[j] < array[j-1]: #한 칸씩 왼쪽으로 이동
array[j], array[j-1] = array[j-1],array[j]
else: #자기보다 작은 데이터를 만나면 그 위치에서 멈춤
break
print(array) #[0,1,2,3,4,5,6,7,8,9]
- 시간복잡도는 빅오 표기법에 따라 O(N^2)입니다. 그러나 이미 정렬되어있는 경우에는, O(N)이다.
3. 퀵 정렬 : 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법입니다.
- 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정합니다.
이후 , 왼쪽 정렬과 오른쪽 정렬에 대해 각각 퀵 정렬 진행해주면 정렬이 완료된다.
- 시간복잡도는 빅오 표기법에 따라 평균 O(Nlog(N))입니다. 그러나 최악의 경우, O(N^2)이다. 여기서 최악의 경우는 이미 정렬된 배열이다.
#예시코드
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[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)
print(array)
* 파이썬의 장점을 살린 방식 (list comprehension)
#퀵정렬 소스코드
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)) #[0,1,2,3,4,5,6,7,8,9]
<정렬 알고리즘 한눈에 정리>
참고자료
- https://www.youtube.com/playlist?list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC
반응형