[알고리즘] 이코테 - 정렬

정렬

• 데이터를 특정 기준에 따라 순서대로 나열한 것
• 정렬 시 이진탐색 가능
• 오름차순 기준(내림차순을 위한 reverse()는 O(N)의 복잡도로 간단히 수행 가능)

 

1. 선택 정렬: 데이터가 무작위로 여러 개 있을 때 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꾸는 과정 반복(가장 작은 것을 선택)
   • 선택 정렬은 가장 작은 데이터를 앞으로 보내는 과정 N-1번 반복 시 정렬 완성
   • 시간 복잡도: N-1만큼 가장 작은 수 찾는 것 + 가장 작은 수 찾기 위한 비교연산
   • 연산 횟수는 근사치로 N*(N+1)/2번의 연산 -> O(N^2): 2중 반복문 사용
   • 선택 정렬 이용 시 데이터의 개수가 10000개 이상이면 정렬 속도 늦어짐

#선택 정렬
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]

 

 

2. 삽입정렬: 특정 데이터를 적절한 위치에 삽입

• 삽입 정렬은 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬되어 있을 때 효율적, 선택정렬과 달리 무조건 모든 원소 비교 및 위치 바꾸기X
• 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정, 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤 그 위치에 삽입된다.
• 정렬이 이루어진 원소는 항상 오름차순을 유지하고 있다는 특징
• 특정 데이터가 삽입될 위치를 선정할 때(삽입될 위치를 찾기 위하여 왼쪽으로 한 칸씩 이동할 때), 삽입될 데이터보다 작은 데이터를 만나면 그 위치에서 멈추기
• 시간복잡도: O(N^2)인데 선택 정렬과 마찬가지로 2중 반복문, 선택 정렬과 흡사한 시간이지만 리스트가 거의 정렬되어 있는 상태라면 매우 빠르게 동작 -> 최선의 경우 O(N)

# 삽입 정렬
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

 

 

3. 퀵 정렬

• 피벗, 큰 숫자와 작은 숫자를 교환할 때 교환하기 위한 기준(보통 리스트에서 첫번째 데이터) 사용
• 피벗을 설정한 뒤에는 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다. 그다음 큰 데이터와 작은 데이터의 위치를 서로 교환해준다.
• 반복 후, 현재 왼쪽에서부터 찾는 값과 오른쪽에서부터 찾는 값의 위치가 서로 엇갈린다. 이 경우 작은 데이터와 피벗의 위치를 서로 변경한다.
• 이후 피벗보다 작은 데이터가 피벗의 왼쪽, 피벗보다 큰 데이터가 피벗의 오른쪽에 위치하게 된다.(분할 혹은 파티션)
• 정렬 수행 후에 피벗 기준 왼쪽 리스트와 오른쪽 리스트에서 각각 다시 정렬 수행
• 재귀적으로 수행 후, 종료조건은 현재 리스트의 데이터 개수가 1인 경우
• 평균 시간 복잡도:O(NlogN),최악의 경우 시간 복잡도가 O(N^2) -> 이미 데이터가 정렬되어 있는 경우에 매우 느리게 동작

# 전통적 퀵 정렬 코드
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)

array=[]
quicksort_sort(array,0,len(array)-1)
print(array)

 

# 비효율적이지만 직관적인 퀵 정렬 코드
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)

array=[]
print(quick_sort(array))

 

 

4. 계수 정렬

• 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용 가능하지만 매우 빠른 정렬 알고리즘(데이터 개수 N, 데이터 중 최대값 K일 때 -> 계수 정렬은 최약의 경우에도 수행 시간 O(N+K)를 보장)
  • 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용 가능하다.
  • 모든 범위를 담을 수 있는 크기의 리스트를 선언해야 하기 때문
• 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다.
  • 데이터의 크기가 제한되어 있을 때에 한해서 데이터의 개수가 매우 많더라도 빠르게 동작한다.
  • 리스트에는 각 데이터가 몇 번 등장했는지 그 횟수가 기록된다.
  • 정렬된 결과를 직접 확인하고 싶다면 리스트의 첫번째 데이터부터 하나씩 그 값만큼 인덱스를 출력하면 된다.
• 시간복잡도: O(N+K), 계수정렬은 앞에서부터 데이터를 하나씩 확인하면서 리스트에서 적절한 인덱스의 값을 1씩 증가시킴 + 추후에 리스트의 각 인덱스에 해당하는 값들을 확인할 때 데이터 중 최대값의 크기만큼 반복 수행 필요
• 공간복잡도: O(N+K),때에 따라 비효율성 초래 가능, 동일한 값을 가지는 데이터가 여러 개 등장할 때 적합. 데이터의 특성을 파악하기 어렵다면 퀵 정렬을 이용하는 것이 유리.

# 계수 정렬
array=[] #정렬할 원소들(0보다 크거나 같음)을 담은 리스트

#모든 범위를 포함하는 리스트 선언 + 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=' ') #띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력

 

 

5. 파이썬의 정렬 라이브러리

• 기본 정렬 라이브러리 sorted() 함수 -> 퀵 정렬과 동작 방식이 비슷한 병합 정렬 기반(최악의 경우 시간 복잡도 O(NlogN) 보장): 리스트 딕셔너리 집합 입력 가능 -> 반환 결과는 리스트 자료형
• 리스트 객체의 내장 함수 sort() -> 반환X, 내부 원소가 바로 정렬
• sorted, sort() 이용 시, key 매개변수를 입력으로 받을 수 있다. key값으로 정렬 기준이 되는 하나의 함수 입력 -> lambda 함수 사용도 가능
• 시간복잡도: O(NlogN), 병합 정렬 + 삽입 정렬 아이디어
• 단순 정렬 시 기본 정렬 라이브러리, 데이터 범위가 한정되어 있고 더 빨리 동작해야 할 때는 계수 정렬 사용.

# 튜플의 두번째 원소 기준 정렬
array=[('바나나',2),('사과',5),('당근',3)]

def setting(data):
  return data[1]
result=sorted(array,key=setting)

print(result)

 

# 성적이 낮은 순서로 학생 출력하기(정렬 알고리즘의 원리에 대해서 물어보는 문제)
n=int(input()) #2
array={}

for i in range(n): #홍길동 95 이순신 77
  m=input().split()
  array[m[0]]=int(m[1])

result = sorted(array.items(), key=lambda x: x[1])

for key,value in result:
  print(key,end=' ') # 이순신 홍길동