알고리즘 기초 입문을 위해 공부한 DO IT! 자료구조와 함께 배우는 알고리즘 입문 : 파이썬편을 통해 새로 알게 된 내용을 정리한다.

1. 셸 정렬(삽입)

: 단순 삽입 정렬의 장점은 살리고, 단점은 보완한 정렬 방식
: 안정적이지는 않다.

1-1. '단순삽입정렬'의 단점

: [1,2,3,4,5,0,6]과 같은 배열에서 1~5까지는 빠르게 지나가지만, 0의 경우 6번의 원소 이동이 있어 비효율적이다
: 즉, '단순삽입정렬'은 정렬이 어느 정도 되어 있는 상황에서 'GOOD'
: 그러나, 삽입할 위치가 멀리 있는 경우에는 'BAD'

def shellSort(arr):
    n = len(arr)
    h = n//2 # 1. 길이의 반으로 자른다
    
    while h > 0 :
        for i in range(h,n):
            j = i-h # 단순 1. 원래 key의 인덱스이나 편의상 i-h를 했고, 이 때문에 '**'줄에서 j+h를 해준다.
            tmp = arr[i] # 단순 2. key값을 임시 저장
            while arr[j] > tmp and j >= 0: # 단순 3. 조건 (tmp값과 같거나 작은 경우와 끝에 도달했을 때 반복이 끝나므로 드모르간을 통한 계속 법칙) 
                arr[j+h] = arr[j]
                j-=h
            arr[j+h] = tmp # **     
        h //=2

[1차 성능 개선]
: 위의 배열을 나누는 'h'값이 중요한 값이다.
: 골고루 배열의 원소를 섞이게 하기 위해, h값들이 서로의 배수가 되지 않도록 한다!

def shellSort(arr):
    n = len(arr)
    -------------------- 변경 사항 1
    h = 1
    while h<0:
    	h = h*3 +1
    --------------------    
    while h > 0 :
        for i in range(h,n):
            j = i-h
            tmp = arr[i]
            while arr[j] > tmp and j >= 0:
                arr[j+h] = arr[j]
                j-=h
            arr[j+h] = tmp # **     
   --------------------- 변경 사항 2
        h //=3
   ---------------------

2. 퀵 정렬

2-1. 기본 구현

[1차 코드]

def qsort(a , left, right) :    
    pl = left
    pr = right
    pivot = a[(left + right) // 2]
    
    while pl <= pr :
        while a[pl] < pivot : pl +=1
        while a[pr] > pivot : pr -=1 
        if pl <= pr :
            a[pl], a[pr] = a[pr], a[pl]
            pl += 1
            pr -= 1
            
    if left < pr : qsort(a, left, pr) 	
    if pl < right : qsort(a, pl, right) 
    
def quick_sort(a):
    qsort(a, 0 , len(a)-1)

: 1차 코드에서는 퀵 정렬의 중요한 두 과정을 포함한다.

• pivot 값을 기준으로 그 값보다 작은 값은 왼쪽, 큰 값을 오른쪽으로 옮긴다는 것!
  : 현혹되지말자! 따라서 pivot의 위치(index)를 기준으로 정렬하는 것이 아닌 '값(value)'를 중심으로 하기 때문에 pivot의 위치는 상관없다! 적절한 값을 지정하는 것이 중요!

• pivot 값을 기준으로 1차 교환이 이루어질 때, 'pl > pr+1'의 조건에서 교환이 멈춘다.
  이 때, pivot 값보다 작은 쪽(arr[0]~arr[pr])과 pivot 값보다 큰 쪽(arr[pl]~arr[len(arr)-1])을 각각 다시 위의 방식과 같이 교환한다. 즉 '재귀적'으로 교환!

2-2. pivot 선택하기

: pivot의 값으로 중앙값을 선택하는 것은 퀵정렬의 효율을 위해 중요한 작업!

• 방법
  1) 배열의 맨 앞, 중간, 맨 뒤 원소를 정렬
  2) 가운데 원소와 맨끝에서 두 번째 원소 교환

def sort3(arr, idx1, idx2, idx3 ): - 추가
    if arr[idx2] < arr[idx1] :  arr[idx1], arr[idx2] = arr[idx2], arr[idx1]
    if arr[idx3] < arr[idx2] :  arr[idx2], arr[idx3] = arr[idx3], arr[idx2]
    if arr[idx1] < arr[idx3] :  arr[idx3], arr[idx1] = arr[idx1], arr[idx3]
    return idx2

def qsort(a , left, right) :    
    pl = left
    pr = right
    m = sort3(a,pl, (left+right)//2, pr) - 추가
    pc = a[m] - 추가
    a[m], a[pr-1] = a[pr-1], a[m] - 추가
    
    while pl <= pr : 
        while a[pl] < pc : pl += 1
        while a[pr] > pc : pr -= 1
        
        if pl <= pr :
            a[pl] , a[pr] = a[pr], a[pl]
            pl += 1
            pr -= 1
            
        if pr > left : qsort(a,left, pr)
        if pl < right : qsort(a,pl, right)
    
    
def quick_sort(a):
    qsort(a, 0 , len(a)-1)

2-3. 퀵정렬의 시간

: 원소가 9개 미만인 경우 단순 삽입 정렬로 전환(원소가 적을 때 빠른 정렬 방법은 아님)