정렬

정렬이란?

: 데이터를 특정한 기준에 따라서 순서대로 나열하는 것 >> 오름차순, 내림차순 등

 

 

정렬의 종류 : 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬

 

# 파이썬에서 제공하는 기본 정렬 라이브러리를 적용하여 효과적인 정렬 수행 가능

 

 

• 선택 정렬 O(N^2)
  • 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 과정을 반복
  • 가장 작은 데이터를 앞으로 보내는 과정을 N-1번 반복하면 정렬 완료
  • 반복문 중첩 두 번 => O(N^2)
  • 기본 정렬 라이브러리보다는 비효율적

lst = [2, 5, 1, 3, 4]

for i in range(len(lst)):
	min_idx = i
    for j in range(i+1, len(lst)):
    	if lst[min_idx] > lst[j]:
        	min_idx = j
    lst[i], lst[min_idx] = lst[min_idx], lst[i]  # 자리 바꾸기

 

 

 

• 삽입 정렬 O(N) ~ O(N^2): 보통의 경우
  • 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤, 그 위치에 삽입
  • 앞 전의 데이터들은 항상 정렬되어 있음
  • 데이터가 많이 정렬되어 있는 상태라면 퀵 정렬보다 빠를 수 있음

lst = [2, 5, 1, 3, 4]

for i in range(1, len(lst)):
	for j in range(i, 0, -1)
    	if lst[j] < lst[j-1]:     #한 칸씩 왼쪽으로 이동
        	lst[j], lst[j-1] = lst[j-1], lst[j]
    else:    #자기보다 작은 데이터를 만나면 그 위치에서 멈춤
    	break

 

 

 

• 퀵 정렬 O(NlogN):보통의 경우 ~ O(n^2)
  • 피벗(기준)보다 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식
  • 재귀 함수 형태
  • 이미 정렬이 되어 있는 경우에 느리게 동작

lst = [2, 5, 1, 3, 4]

def quick_sort(lst):
	if len(lst) <= 1:
		return lst
   
    pivot = lst[0]
    tail = lst[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)
    
quick_sort(lst)

 

 

 

• 계수 정렬 O(N + K)                # K = 데이터 중 최대 값
  • 특정한 조건이 부합할 때 사용할 수 있음
  • 조건 : 가장 큰 데이터와 작은 데이터의 차이가 100000보다 작아야 함
  • 가장 작은 수 부터 큰 수의 lst를 만들어 놓고 해당 인덱스에 맞도록 리스트에 넣음

lst = [2, 5, 1, 3, 4]

idx = [0] * max((lst) + 1)

for i in range(len(lst)):
	idx[lst[i]] += 1

for i in range(len(idx)):
	for j in range(idx[i])
    	print(i)

 

 

 

• 파이썬의 정렬 라이브러리 O(NlogN) : 최악의 경우
  • sorted(),   sort()
  • 일반적으로 퀵 정렬보다 느림

lst = [2, 5, 1, 3, 4]

#lst.sort()

result = sorted(lst)