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

선택 정렬 알고리즘

• 단순한 정렬 시리즈 중 하나
• n개짜리 배열에서 시작하여 아직 정렬되지 않은 배열의 크기를 하나씩 줄임
• 특정 숫자(최대.최소)를 선택하는 방식으로 정렬을 진행
  • 각 Loop마다
    • 남아있는 원소 중, 최대 원소 선택
    • ==최대 원소와 맨 오른쪽 원소를 교환한다(오른쪽)==
  • 하나의 원소만 남을 때까지 위의 Loop를 반복
• 제자리 정렬 알고리즘
  • 입력 배열 이외에 다른 추가 메모리를 요구하지 않음
• 시간 복잡도
  • O(n^2)

def Sel_sort(a):
    n = len(a)
    for i in range(0, n-1):
        idx = i
        for j in range(i+1, n):
            if a[j] < a[idx]:
                idx = j
        a[i], a[idx] = a[idx], a[i]
    print(a)

Sel_sort([2,4,5,1,3])

버블 정렬 알고리즘

• 단순한 정렬 시리즈 중 하나
• n개짜리 배열에서 시작하여 아직 정렬되지 않은 배열의 크기를 하나씩 줄임
• ==이웃하는 숫자를 비교==하여 특정한 수(최대.최소)를 한 쪽(앞.뒤)으로 이동시키는 과정을 반복하여 정렬하는 알고리즘
• Outer-loop가 한 번 돌 때마다, 원소 하나의 최종 위치 확정
• 교환이 많음
  • 실용성 없음
• 시간 복잡도
  • O(n^2)

def bubble_sort(a):
    n = len(a)        
    while True:
        changed = False

        for i in range(0, n-1):
            if a[i] > a[i+1]:
                a[i], a[i+1] = a[i+1], a[i]
                changed = True
            if changed == False:        
                return

d = [2,4,5,1,3]
bubble_sort(d)
print(d)

삽입 정렬 알고리즘

• 단순한 정렬 시리즈 중 하나
• 1개짜리 배열에서 시작하여 이미 정렬된 배열의 크기를 하나씩 늘리는 정렬
• 배열을 정렬된 부분(앞부분)과 정렬 안 된 부분(뒷부분)으로 나누고, 정렬 안 된 부분의 가장 왼쪽 원소를 정렬된 부분의 적절한 위치에 삽입하여 정렬되도록 하는 과정을 반복
  • ex) 두번째 원소부터 하나의 원소를 빼놓고 앞의 정렬된 원소랑 비교하며 크면 자리를 오른쪽으로 복사 그 왼쪽에 삽입
• 시간 복잡도
  • O(n^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)