[알고리즘] 정렬 알고리즘

❗ Stable vs Not Stable

• Stable 정렬 알고리즘 : 중복된 값에 대해 순서대로 정렬하는 알고리즘
• Not Stable 정렬 알고리즘 (stable의 반대)

1. 버블 정렬

• 배열에서 이웃한 두 원소를 비교한다.
• 두 원소 중 더 큰 값이 뒤에 오도록 한다.
• 맨 뒤쪽부터 정렬된다.
• stable 정렬 : 앞 원소가 큰 경우에만 swap을 진행하기 때문이다.
• O(N^2)

def swap(arr, i, j):
	temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
    
    
def bubble_sort(list) :
	for i in range(list(len)):
    	for j in range(len(list)-i-1):
        	if list[j] > list[j+1]: 
            	swap(list,j,j+1) #뒤에 오는 원소가 더 크도록 위치 교환
                

2. 선택정렬

• 구현 방법
  1. 정렬대상 배열에서의 최소값을 결과 배열에 옮기는 과정을 반복한다.
     -> 추가의 메모리(배열)가 필요하다.
  2. 정렬되지 않은 부분에서 최솟값을 찾고,
     정렬되지 않은 부분의 맨 앞 원소와 위치를 바꾼다.(1 개선)
• 맨 앞쪽부터 정렬된다.
• stable : 앞쪽부터 최소 원소를 찾고, 앞쪽부터 정렬되기 때문이다.
• O(n^2)

# 개선된 선택정렬
def select_sort(list) :
	for i in range(len(list)):
    	min_idx = i
        for j in range(i+1,len(list)):
        	if list[j] < list[min_idx]:
            	min_idx = j
        swap(list,i,min_idx) # 버블정렬에서 사용된 swap 사용
                

3. 삽입정렬

• 정렬되지 않은 부분의 첫번째 원소를 정렬된 부분의 적절한 위치에 삽입한다.
• 정렬된 부분의 원소가 더 큰 경우 뒤로 한 칸씩 밀어내, 정렬대상 원소의 자리를 마련한다.(정렬대상 원소보다 작은 원소를 만날 때까지 반복)
• stable : 정렬된 부분의 원소가 같은 경우 밀어내기를 진행하지 않기 때문이다.
• O(N^2)

def insert_sort(list):
	for i in range(1,len(list)):
    	target = list[i] # 삽입할 원소
    	for j in range(i-1,-1,-1):
        	if list[j] > target :
            	list[j+1]=list[j]
            else :
            	list[j+1] = target

4. 힙정렬

• 힙 자료구조를 이용한다.
• 정렬 수행 순서 (오름차순 기준, 1번 인덱스가 최소값)
  1) 최소힙 구성
  2) 최소값을 배열의 맨 마지막에 놓는다.
  3) 마지막 노드를 루트(인덱스 1)에 두고 1,2 수행(heap[:-i]에 대해)
• not stable : 형제 노드가 동일한 경우 오른쪽 노드와 부모 노드를 교환하기 때문(아래 구현의 경우)

def heapify(heap, index, heap_size):
	largest = index
    left_child_index = index*2
    right_child_index = index*2+1
    
    if (left_child_index < heap_size) and (heap[largest] > heap[left_child_index]) : #왼쪽 자식 노드가 존재하고, 부모 노드보다 작은 경우
    	largest = left_child_index
     if (right_child_index < heap_size) and (heap[largest] > heap[right_child_index]) : #오른쪽 자식 노드가 존재하고, 부모 노드보다 작은 경우
    	largest = right_child_index
      
      if index != largest : 
      	heap[largest],heap[index] = heap[index],heap[largest] # 자식노드와 부모 노드를 교환한다.
      	heapify(heap, largest, heap_size) # 자식노드를 루트노드로 하는 힙에 대해서 heapify를 수행한다.
    
def heap_sort(list):
	n = len(list)
	# 1. 최소힙 구성
	# 자식 노드를 갖는 마지막 노드부터 상향으로 heapify 진행한다.
    # 마지막 노드부터 수행하지 않아도 된다.
	for i in range(n//2-1,-1.-1):
    	heapify(list, i, n) 
    
    
    for i in range(n-1,0,-1):	
        list[i], list[1] = list[1], list[i] # 2. 루트 노드와 마지막 노드의 값을 교환한다.
        heapify(list, 0, i) # 3. 나머지 배열에 대해 heapify 수행
    

❓ 힙

• 완전 이진트리의 일종으로, 우선순위 큐를 위해 만들어진 자료구조
• 최댓값 or 최솟값을 빠르게 찾아내기 위한 자료구조
• 일종의 반정렬(느슨한 정렬 상태)를 유지한다.
  • 부모 노드는 자식 노드보다 우선순위가 높다.
  • 형제 노드 간 우선순위는 정렬되어있지 않다.
• 부모노드와 자식 노드의관계
  • 왼쪽 자식 노드의 인덱스 = (부모 노드의 인덱스)*2
  • 오른쪽 자식 노드의 인덱스 = (부모 노드의 인덱스)*2+1
• 힙의 삽입, 삭제
  • 삽입
    1) 완전 이진트리의 끝에 새로운 노드를 삽입한다.
    2) 부모 노드와 비교해 우선순위가 높으면 부모 노드와 교환한다.
    3) 2의 과정을 루트노드에 도달하거나 더 높은 우선순위 노드를 만날 때까지 반복한다.
  • 삭제(루트노드 삭제)
    1) 루트 노드를 삭제한다.
    2) 마지막 노드를 루트 노드 위치로 옮긴다.
    3) 우선순위가 높은 자식 노드와 비교하여 해당 노드가 우선순위가 낮으면 자식 노드와 교환한다.
    4) 자식 노드가 없거나(리프 노드 도달) 우선순위가 높은 자식 노드를 발견하지 못할 때까지 3의 과정을 반복한다.
• 참고 https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

5. 병합정렬

• devide - conqure(분할 정복), 재귀
• 원소가 1개가 남을 때까지 분할하고, 분할된 두 배열을 합친다.
• not stable : 아래 구현의 경우 그러하다
• O(NlogN)

def merge_two_array(list, left, mid, right):
	temp_list=[]
    
    current_index = left
    left_index = left
    right_index = mid +1
    
    while (left_index <= mid) and (right_index <= right) :
    	if list[left_index] < list[right_index] :
	        temp_list[current_index] = list[left_index]
            left_index += 1
    	else :
        
        """
        not stable인 이유 :
        두 배열의 비교 대상이 동일한 원소인 경우,
        뒤쪽 배열에 위치한 원소를 먼저 옮기기 때문이다.
        """
	        temp_list[current_index] = list[right_index]
            right_index += 1
        current_index += 1
            
    #왼쪽 원소 완전히 옮기기
    while (left_index <= mid) : 
    	temp_list[current_index] = list[left_index]
        left += 1
        current_index += 1
        
    #오른쪽 원소 완전히 옮기기    
    while (mid+1 <= righ) : 
    	temp_list[current_index] = list[right]
        right += 1
        current_index += 1

	#결과 배열로 원소 옮기기
    for i in range(len(list)):
    	list[i] = temp_list[i]
        
def merge_sort(list, left, right):
	if left < right :
    	# 정렬 대상 분할하기
    	mid = (left+right)//2
        merge_sort(list,left,mid)
        merge_sort(list,mid+1,right)
        
        # 정렬 대상 합치면서 정렬하기
        merge_two_array(list,left,mid,right)

6. 퀵정렬

• devide - conqure(분할 정복), 재귀
• 피벗(임의 위치의 기준값)을 기준으로 보다 작은 부분과 보다 큰 부분을 나눈다.
• 위 과정을 재귀적으로 수행해 정렬한다.
• 피벗의 값 or 정렬여부에 따라 시간복잡도가 달라진다.
• 프로그래밍 언어에서 기본으로 제공하는 정렬 함수의 경우 퀵정렬을 사용하는 경우가 많다.
• not stable : 'low < high'인 경우 먼저 나온 원소(low)가 high와 교환되어 뒤쪽으로 갈 수 있기 때문.
• O(NlogN) : 최악의 경우 N^2가 될 수도 있음

""" 
 윤성우의 열혈 자료구조 ver 
- 분할하는 부분과 정렬하는 부분을 두 함수로 구분
"""
def partition(list,left,right):
	low  = left+1
    high = right
    
    while low <= high :
    	while (low <= right) and (list[low] <= list[left]) :
        	low += 1
        while (left <= high) and (list[high] >= list[left]) :
        	high -= 1
        if low < high :
        	swap(list,low,high)
            
    swap(list, left, high)
    return high
    
def quick_sort(list, left, right):
	if left < right :
    	pivot = partition(list, left, right)
        quick_sort(list,left, pivot-1)
        quick_sort(list,pivot+1,right)
        

"""
일반적으로 많이 쓰이는 ver
- 하나의 함수 안에서 분할, 정렬을 모두 수행
- 피벗을 기준으로 세 배열로 나눈 후 이를 합치는 방법으로 정렬을 수행
"""
def quick_sort(list) :
	if len(list) <= 1:
    	return list
    pivot = list[0] # 배열의 중간값을 사용해도 됨
    
    # 각각 피벗보다 크기가 작은, 같은, 큰, 원소를 저장하는 리스트를 의미함
    less_list =[]
    equal_list=[]
    greater_list = [] 
    
    for i in list : 
    	if i > pivot :
        	greater_list.append(i)
        elif i == pivot :
        	equal_list.append(i)
        else:
        	less_list.append(i)
            
    return quick_sort(less_list) + equal_list + quick_sort(greater_list) 
    	
    	

7. 기수정렬