[정렬] 기본 정렬 알고리즘 정리 (Python)

정렬 알고리즘은 주어진 리스트나 배열에서 사용자가 지정한 기준에 따라 정렬하는 알고리즘을 말한다. 알고리즘에 따라 O(N^2) 또는 O(NlogN) 으로 시간복잡도가 다양하다.

 

1. 선택 정렬

말 그대로 해당하는 값을 선택해서 맨 앞의 값과 위치를 바꿔주는 정렬이다. 오름차순으로 정렬할지 내림차순으로 정렬할 지에 따라 최소선택정렬(Min-Selection Sort)와 최대선택정렬(Max-Selection Sort)로 나뉘어진다. 

 

@ 알고리즘 구성 (최소선택정렬)

1) 정렬되지 않은 리스트의 맨 처음부터 가장 작은 값을 찾아준다.

2) 가장 작은 값을 찾은 뒤 맨 앞의 인덱스와 위치를 바꿔준다.

3) 다음 인덱스부터 1), 2)를 반복한다.

def selection_sort(arr):
    for i in range(N-1):
        tmp = i
        for j in rnage(i+1, N):
            if arr[tmp] >= arr[j]:
                tmp = j
        arr[i], arr[tmp] = arr[tmp], arr[i]
    return arr

2. 삽입 정렬

삽입 정렬은 두번째 인덱스부터 탐색을 시작한다. 두번째 인덱스부터 시작해서 앞의 자료들과 비교하여 삽입할 위치를 지정하여 자료들을 뒤로 옮기고 지정 위치에 삽입한다. 

 

@ 알고리즘 구성

1) 두번째 인덱스부터 차례로 앞의 자료들에서 삽입할 위치를 찾는다.

2) 삽입할 위치를 찾을 때 까지 자료들을 뒤로 한 칸씩 옮긴다.

def insertion_sort(arr):
    j = 1
    for j in range(j, len(arr)):
        key = arr[j]
        i = j - 1
        while i >= 0 and arr[i] > key:
            arr[i+1] = arr[i]
            i = i-1
        arr[i+1] = key
    return arr