[알고리즘] 정렬 - (선택/삽입/퀵/계수/버블/병합/라이브러리)

정렬 (sorting) 이란?
- 정렬 (sorting): 어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 것
- 정렬은 프로그램 작성시 빈번하게 필요로 함
- 다양한 알고리즘이 고안되었으며, 알고리즘 학습의 필수
> 다양한 정렬 알고리즘 이해를 통해, 동일한 문제에 대해 다양한 알고리즘이 고안될 수 있음을 이해하고, 각 알고리즘간 성능 비교를 통해, 알고리즘 성능 분석에 대해서도 이해할 수 있음

 

선택 정렬

• 다음과 같은 순서를 반복하며 정렬하는 알고리즘
    1. 주어진 데이터 중, 최소값을 찾음
    2. 해당 최소값을 데이터 맨 앞에 위치한 값과 교체함
    3. 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복함
• https://visualgo.net/en/sorting
• 시간 복잡도 : O(N^2). 데이터 개수 10,000개 이하일 때만 사용하기.

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

def selection_sort(data):
    for stand in range(len(data) - 1):
        lowest = stand
        for index in range(stand + 1, len(data)):
            if data[lowest] > data[index]:
                lowest = index
        data[lowest], data[stand] = data[stand], data[lowest]	#스와프. (c 등 다른 언어는 temp 변수를 이용해 스와프 함)
    return data
    
print(selection_sort(array))

 

삽입 정렬

• 해당 인덱스(key 값) 앞에 있는 데이터(B)부터 비교해서 key 값이 더 작으면, B값을 뒤 인덱스로 복사. 이를 key 값이 더 큰 데이터를 만날때까지 반복, 그리고 큰 데이터를 만난 위치 바로 뒤에 key 값을 이동
• 두 번째 데이터부터 시작
• 시간 복잡도 : O(N^2). 완전 정렬이 되어 있는 상태라면 최선은 O(n)
• 대부분 정렬되어 있는 데이터라면 퀵 정렬보다 빠름(O(N))
• 직접 눈으로 보면 더 이해가 쉽다: https://visualgo.net/en/sorting

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

def insertion_sort(array):
    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
	return array
print(insertion_sort(array))

 

퀵 정렬

• 정렬 알고리즘의 꽃
• 기준점(pivot 이라고 부름)을 정해서, 기준점보다 작은 데이터는 왼쪽(left), 큰 데이터는 오른쪽(right) 으로 모으는 함수를 작성함
• 각 왼쪽(left), 오른쪽(right)은 재귀용법을 사용해서 다시 동일 함수를 호출하여 위 작업을 반복함
• 함수는 왼쪽(left) + 기준점(pivot) + 오른쪽(right) 을 리턴함
• 시간 복잡도 : O(NlogN) - 일반
• 맨 처음 pivot이 가장 크고 작거나, 대부분 정렬되어 있다면 모든 데이터를 비교하는 상황으로 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)

 

## 이거 보기!!
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))

 

계수 정렬

• 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적
• 데이터의 크기가 한정되어 있고 많이 중복되어 있을수록 효과적
• 시간 복잡도 : O(N+K). K는 최대값의 크기
• 공간 복잡도 : O(N+K)

array = [7,5,9,0,3,1,6,2,9,1,4,8,0,5,2]
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=' ')

 

버블 정렬

• 두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘
  https://visualgo.net/en/sorting

Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - VisuAlgo

def bubblesort(data):
    for index in range(len(data) - 1):
        swap = False
        for index2 in range(len(data) - index - 1):
            if data[index2] > data[index2 + 1]:
                data[index2], data[index2 + 1] = data[index2 + 1], data[index2]
                swap = True
        
        if swap == False:
            break
    return data
    
import random

data_list = random.sample(range(100), 50)
print (bubblesort(data_list))

시간 복잡도 

* 반복문이 두 개 O(n^2)
* 완전 정렬이 되어 있는 상태라면 최선은 O(n)

병합 정렬

• 재귀용법을 활용한 정렬 알고리즘
    1. 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
    2. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
    3. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.
• 직접 눈으로 보면 더 이해가 쉽다: https://visualgo.net/en/sorting
• 단계별 시간 복잡도 O(n) * O(log n) = O(n log n)

def merge(left, right):
    merged = list()
    left_point, right_point = 0, 0
    
    # case1 - left/right 둘다 있을때
    while len(left) > left_point and len(right) > right_point:
        if left[left_point] > right[right_point]:
            merged.append(right[right_point])
            right_point += 1
        else:
            merged.append(left[left_point])
            left_point += 1

    # case2 - left 데이터가 없을 때
    while len(left) > left_point:
        merged.append(left[left_point])
        left_point += 1
        
    # case3 - right 데이터가 없을 때
    while len(right) > right_point:
        merged.append(right[right_point])
        right_point += 1
    
    return merged


def mergesplit(data):
    if len(data) <= 1:
        return data
    medium = int(len(data) / 2)
    left = mergesplit(data[:medium])
    right = mergesplit(data[medium:])
    return merge(left, right)

정렬 라이브러리

• 시간 복잡도 : 항상 O(NlogN)

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

result = sorted(array)
print(result)

array.sort()
print(array)

array = [('바나나',2),('사과',5),('당근',3)]
def setting(data):
	return data[1]
result = sorted(array, key=setting)
print(result)