[n523] 알고리즘

Sorting Algorithms (정렬 알고리즘)

Selection Sort(선택정렬)

• 이름이 왜 선택 정렬인가? 가장 작은 노드를 '선택'해서 비교하므로. 
• 가장 작은 노드 하나를 선택한 뒤, 맨 왼쪽 노드와 비교한다. 가장 작은 노드가 왼쪽 노드보다 작으면 교환.
• 최소노드 선택 -> 왼쪽부터 비교 -> 교환하는 과정을 반복한다.
• 아래 그림 예시에서, 첫 번째 인덱스는 기준점이 된다. 그 외의 노드들 중 가장 작은 값 13과 첫번째 인덱스 값을 비교한다. 
• 13이 더 작으면 첫 번째 인덱스 값과 교환을 하고, 아니면 바로 pass 한다. 
• 위의 과정을 계속해서 반복 한다. 
• 시간 복잡도는 O(n^2)이다.

# 선택정렬 소스코드

def selection_sort(li):
    for i in range(len(li) - 1):
        min_idx = i
        for j in range(i + 1, len(li)):
            if li[j] < li[min_idx]:
                min_idx = j
        li[i], li[min_idx] = li[min_idx], li[i]
    return li

 

 

Insertion Sort(삽입정렬)

• 삽입 정렬은 정렬된 노드들 값 들 사이에 작은 값을 '삽입' 하는 정렬 방식이다. 
• 선택정렬처럼 가장 작은 원소를 선택하는 방식이 아니다. 
• 삽입정렬은 소량의 데이터를 정렬하기위한 효율적이지만 시간 복잡도는 최악의 경우 O(n^2)이다.
• 정렬된 노드들을 매번 비교 해야 하므로 정렬을 진행할수록 탐색해야할 정렬 범위가 넓어진다는 점이 특징이다. 
• 시간 복잡도는 O(n^2), 최상의 경우 O(n)이다.

• 위의 그림은 이미 17, 26, 54, 77, 93이 정렬된 후의 과정이다.
  • 1) 노드31에 대해 이미 정렬된 배열 (17, 26, 54, 77, 93)과 비교한다.
  • 2) 노드31보다 작은 값을 갖고 있는 노드가 나올때(26)까지 비교를 진행한다.
  • 3) 31보다 작은 26을 찾으면 노드26 오른쪽 인덱스에 노드31을 삽입한다.
  • 4) 44, 55, 20 노드도 반복한다.

def insertion_sort(data):
    for index in range(len(data) - 1):
        for index2 in range(index+1, 0, -1):
            if data[index2] < data[index2 - 1]:
                data[index2], data[index2 - 1] = data[index2 - 1], data[index2]
            else:
                break
    return data

 

 

Bubble Sort(버블정렬)

• 단순하게 이웃한 두 노드의 크기를 비교한 뒤 교환하는 방식이다. 
• 매우 간단하게 구현 가능하지만 비효율적이라 많이 쓰이지 않는다.
• 시간 복잡도는 O(n^2)이다.

# 버블정렬 소스코드
def bubble_sort(li):
    for i in range(len(li)):
      for j in range(1, len(li)):
        if li[j-1]>li[j]:
          li[j-1], li[j] = li[j], li[j-1]
 
    return li