[알고리즘] 5. 정렬

알고리즘 꽃

정렬 : 자료를 특정 순서대로 정렬하는 것

정렬의 종류 : 선택정렬, 삽입정렬, 병합정렬,  퀵정렬, 거품정렬

 

1. 선택정렬 

선택정렬 : 리스트 중에 순서대로 선택해서 정렬시키기!

1) 선택정렬 알고리즘 (쉽게)

def find_min_idx(a):
    n=len(a)
    min_idx=0
    for i in range(1,n):
        if a[i]<a[min_idx]:
            min_idx=i
    return min_idx
 
 
def sel_sort(a):
    result=[]
    while a:
        min_idx=find_min_idx(a)
        Value = a.pop(min_idx)
        result.append(Value)
    return result
 
d=[2,4,5,1,3]
print(sel_sort(d))

2) 선택정렬 알고리즘 (일반)

def sel_sort(a):
    n=len(a)
    for i in range(0,n-1):
        min_idx = i
        for j in range(i+1,n):
            if a[j] < a[min_idx]:
                min_idx = j
        a[i], a[min_idx] = a[min_idx],a[i]
    
d=[2,4,5,1,3]
sel_sort(d)
print(d)

 

3) 알고리즘 분석

시간복잡도 = O(n^2)

 

 

2. 삽입정렬

삽입정렬 : 리스트를 하나하나 뽑아서 제자리로 정렬

1) 삽입정렬 알고리즘 (쉽게)

def find_ins(r,v):
    for i in range(0,len(r)):
        if v < r[i]:
            return i
    
    return len(r)
 
 
def ins_sort(a):
    result=[]
    while a:
        value = a.pop(0)
        ins_idx = find_ins(result,value)
        result.insert(ins_idx,value)
    return result
 
d=[2,4,5,1,3]
print(ins_sort(d))

 

2) 선택정렬 알고리즘 (일반)

def ins_sort(a):
   n = len(a)
   for i in range(1, n):
       key = a[i]
       j = i - 1
       while j >= 0 and a[j] < key:  # 부등호 방향 뒤집기
           a[j + 1] = a[j]
           j -= 1
       a[j + 1] = key
 
d = [2, 4, 5, 1, 3]
ins_sort(d)
print(d)
 

 

3) 알고리즘 분석

시간복잡도 = O(n^2)