[알고리즘] 01. 정렬 알고리즘 - 1

11 Jan 2020 in Computer-Science

다양한 정렬 알고리즘의 특징을 살펴본다.

어떤 데이터들을 정해진 순서대로 나열하는 여러 알고리즘 중 시간복잡도가 O(n²)인 대표적인 알고리즘을 살펴본다.

1. 버블 정렬

def bubble_sort(lst):
    for end in range(len(lst)-1, -1, -1):
        swap = False
        for idx in range(end):
            if lst[idx] > lst[idx+1]:
                lst[idx], lst[idx+1] = lst[idx+1], lst[idx]
                swap = True
        if not swap:
            break
    return lst

1. 첫 번째 인덱스부터 두 개씩 인접한 데이터를 순서대로 비교하며 크기에 따라 순서대로 자리를 바꾼다.

2. 1의 과정중 가장 마지막으로 옮겨진 값은 고정하고, 그 전 인덱스까지 1의 과정을 반복한다.

2. 삽입 정렬

def insertion_sort(lst):
    for st in range(1, len(lst)):
        idx = st
        for i in range(st-1, -1, -1):
            if lst[i] > lst[idx]:
                lst[i], lst[idx] = lst[idx], lst[i]
                idx = i
            else:
                break
    return lst

1. 선택한 데이터와 바로 앞 인덱스에 있는 데이터를 비교하여 선택한 데이터보다 크면 자리를 바꾸고 작거나 존재하지 않으면 그대로 둔다.

2. 선택한 데이터의 바로 뒤의 인덱스 부터 데이터 끝까지 1의 과정을 반복한다.

3. 선택 정렬

def selection_sort(lst):
    for st in range(len(lst)-1):
        select = False
        tmp = st
        for idx in range(st+1, len(lst)):
            if lst[tmp] > lst[idx]:
                tmp = idx
                select = True
        if select:
            lst[st], lst[tmp] = lst[tmp], lst[st]
    return lst

1. 데이터 중 최소값을 찾고 그 값을 제일 앞으로 가져온다.

2. 앞으로 가져온 값은 고정하고 나머지 값 중 최소값을 찾아 고정한 값 다음 자리에 고정한다.

3. 위의 과정을 반복한다.