정렬 알고리즘

정렬

: 데이터를 특정한 기준에 따라서 순서대로 나열하는 것

오름차순 정렬

• 내림차순은 크기 비교 반대로 수행
• 파이썬에서는 리스트 뒤집는 메소드 제공

선택정렬

• 데이터 개수 = n
• 선택정렬은 가장 데이터를 선택해 맨 앞의 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 두번 째 데이터와 바꾸는 과정을 반복한다.
• 데이터를 앞으로 보내는 과정을 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]
 	#swap
print(array)

이미지넣기

선택 정렬의 시간 복잡도

• 0~n-1번의 수행이므로 N(N+1)/2, O(N^2)이다.

삽입 정렬

: 데이터를 하나씩 확인하여, 적절한 위치에 삽입하는 정렬

• 삽입 정렬은 데이터가 거의 정렬 되어 있을 때 효율적이다.
• 삽입 정렬은 첫 번째 데이터는 정렬되어 있다고 판단하여 두 번째 데이터부터 시작한다.
• n-1번 수행하여 정렬 완료
• 정렬이 이뤄진 원소는 항상 오름차순을 유지한다.
• 자기보다 작은 데이터를 만났다면 그 위치에 삽입된다.

이미지넣기

삽입정렬 소스코드

array = [7,5,9,0,3,1,6,2,4,8]

for i in range(1, len(array)):
#1번 인덱스부터 시작
    for j in range(i, 0,-1):
    #i번째 인덱스부터 1(end+1)까지 1씩 감소
    	if array[j] < array[j-1]:
        #왼쪽 인덱스가 더 크면
        	array[j], array[j-1]= array[j-1],array[j]
             #swap(왼쪽 이동)
        else:
        	break
            #왼쪽 인덱스가 더 작으면 현 위치에 멈춤(삽입)
print(array)

선택 정렬의 시간 복잡도

• 반복문 중첩으로 O(N^2) -> 데이터가 거의 정렬되어 있는 상태라면 O(N)

퀵 정렬

: 기준 데이터 설정 후 큰수와 작은 수를 교환한 후 리스트를 반으로 나누는 형식

피벗 : 교환하기 위한 기준

• 호어 분할 방식에서는 첫번째 데이터를 피벗으로 정한다.
• 삽입 정렬은 첫 번째 데이터는 정렬되어 있다고 판단하여 두 번째 데이터부터 시작한다.
• n-1번 수행하여 정렬 완료
• 정렬이 이뤄진 원소는 항상 오름차순을 유지한다.
• 자기보다 작은 데이터를 만났다면 그 위치에 삽입된다.

이미지넣기

퀵정렬 소스코드

array = [5,7,9,0,3,1,6,2,4,8]

def quick_sort(array, start, end):
    if start >= end:
    	return
    #퀵 정렬 종료 조건 : 원소 하나면 종료
    pivot = start
    #첫번째 원소는 pivot
    left = start +1
    right = end
    while left < = right:
    	while left <= end and array[left] <= array[pivot]:
        left += 1
        #오른쪽 인덱스보다 작고, 피벗보다 작을 때 left 오른쪽 이동 반복
    	while right > start and array[right] >= array[pivot]:
        right -= 1
         #왼쪽 인덱스보다 크고 피벗보다 클 때 right 왼쪽 이동 반복
        if left > right:
        	array[right], array[pivot] = array[pivot], array[right]
        #엇갈림 발생 시 피벗과 작은 데이터 swap
        else:
            array[left], array[right]= array[right],array[left]
             #엇갈림 발생하지 않으면 left right swap
    quick_sort(array, start, right-1)
    quick_sort(array, right +1, end)
    
quick_sort(array, 0, len(array)-1)
print(array)

파이썬 장점을 살린 퀵 정렬 소스코드

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))

퀵 정렬의 시간 복잡도

• 데이터 갯수 = n
• 높이는 logN
• O(NlogN)

계수 정렬

:

• 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용
• 큰 데이터와 가장 작은 데이터의 차이가 너무 크면 사용 불가
• 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다는 특징
• 리스트의 데이터를 크기순으로 하나의 리스트를 생성
• 리스트에 각 데이터가 몇 번 등장했는지 횟수를 기록한다.

계수 정렬 소스코드

array = [7,5,9,0,3,1,6,2,4,8]
count = [0] * (max(array) +1)
#모든 범위 포함하는 리스트 선언(0으로 초기화)

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 = '')
        #띄어쓰기로 구분

계수 정렬의 시간 복잡도

• 데이터 개수 = N
• 최대값 크기 = K
• O(N+K) -> 데이터 하나씩 확인하며 리스트의 인덱스 값 하나씩 증가시키고, 리스트의 인덱스에 해당하는 값들을 확인할 때 데이터 중 최댓값의 크기만큼 반복 수행하기 때문

파이썬의 정렬 라이브러리

sorted()함수

: 병합 정렬를 기반으로 만들어짐(병합 정렬은 퀵정렬보다 느림)

sort()함수

: 리스트 객체의 내장 함수로, 별도의 정렬된 리스트 반환하지 않고 내부 원소가 바로 정렬된다.

array = [('바나나', 2),('사과', 5),('당근', 3)]

def setting(data):
	return data[1]

result = sorted(array, key = setting)
#1번 인덱스 값이 key가 되어 정렬된다.
print(result)