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

1. 정렬 알고리즘

1-1. 안정적 정렬 알고리즘

: 값이 같은 원소의 순서가 정렬된 이후에도 변하지 않는 알고리즘

1-2. 정렬 알고리즘의 '핵심'

교환, 선택, 삽입
: 모든 정렬 알고리즘은 교환, 선택, 삽입하면서 정렬을 이룬다.

2. 정렬 알고리즘 종류

2-1. 버블 정렬(교환)

def bubbleSort(arr) : 
    n = len(arr)
    for i in range(1,n):
        for j in range(n-1, i, -1):
            if arr[j] < arr[j-1]:
                arr[j-1], arr[j] = arr[j], arr[j-1]
        
[1차 성능 개선] 
: 한 패쓰(이중 포문에서 두 번째 포문 한 턴 도는 것)에서 교환이 한 번도 일어나지 않았다면, 그대로 for문을 나오자는 발상!!

def bubbleSort(arr) : 
    n = len(arr)
    for i in range(1,n):
        count = 0
        for j in range(n-1, i, -1):
            if arr[j] < arr[j-1]:
                count +=1
                arr[j-1], arr[j] = arr[j], arr[j-1]
        if count == 0 :
            break
            
[2차 성능 개선]
: 가장 마지막에 교환이 일어났던 인덱스를 다음 패쓰의 마지막 인덱스로 한다.
def bubbleSort(arr) : 
    n = len(arr)
    k = 0
    while k < n-1:     
        last = n-1   
        for j in range(n-1, k, -1):
            if arr[j] < arr[j-1]:        
                arr[j-1], arr[j] = arr[j], arr[j-1]
                last=j        
        k = last
       

2-1(기타). 셰이커 정렬

: 정렬이 거의 완료된 상황에서 정렬될 원소가 양 극단에 있는 경우! 그럴 때 쓰면 좋다.

def shakerSort(arr) : 
    n = len(arr)
    left = 0
    right = n-1
    last = right   
    
    while left < right:  
        for j in range(right, left, -1):
            if arr[j] < arr[j-1]:        
                arr[j-1], arr[j] = arr[j], arr[j-1]
                last=j        
        left = last
        
        for j in range(left, right):
            if arr[j] > arr[j+1]:        
                arr[j+1], arr[j] = arr[j], arr[j+1]
                last=j
        right = last        

2-2. 단순 선택 정렬

: 배열의 가장 작은 원소를 '선택'하여 배열의 앞 부분부터 교환하는 정렬
: 안정적이지 않다(서로 이웃한 원소끼리 교환하는 것이 아니라서)

def selectionSort(arr) :
    n = len(arr)    
    
    for i in range(n-1):        
        min = i # # 포인트 1. '인덱스'만 가져도 충분
        for j in range(i+1,n): # 포인트 2. i+1부터 추적해야 시간 줄임!
            if arr[min] > arr[j]:
                min = j
        arr[i], arr[min] = arr[min],arr[i]    

2-3. 단순 삽입 정렬

: 아직 정렬되지 않은 부분의 맨 앞 원소를 정렬된 부분의 알맞은 위치에 삽입
: 안정적이지 않다
: [종료조건]

• 정렬된 배열의 끝에 도달할 경우
• tmp보다 작거나 같은 원소를 발견할 경우

def insertionSort(arr) :
    n = len(arr)
    for i in range(1,n):
        j = i # 이 아이디어 좋네
        tmp = arr[i]
        while arr[j-1] > tmp and j>0 : 
            arr[j] = arr[j-1]
            j-=1
        arr[j] = tmp      
      
[1차 성능 개선]
: 결국 tmp보다 값이 같거나 작은 값을 찾는 거라면 '탐색'이다. 그 중 정렬된 배열에서 빨리 탐색해주는 건 '이진탐색'
def insertionSort(arr) :
    n = len(arr)
    
    for i in range(1,n):
        pl = 0
        pr = i-1
        key = arr[i]
        
        while True :
            pc = (pl + pr) // 2
            if arr[pc] == key : 
                break
            elif arr[pc] > key : 
                pr = pc-1
            else : 
                pl= pc +1
            if pl > pr : 
                break
            
        pd = pc + 1 if pl <= pr else pr + 1 # 이 부분이 잘 이해가 안된다. 저번에 이해했는데??  
        for j in range(i,pd,-1):
            arr[j] = arr[j-1]
        arr[pd] = key

**
import bisect
for i in range(len(arr)):
bisect.insort(arr, arr.pop(i), 0,i)