2019.10.23
출처 : http://ejklike.github.io/2017/03/04/sorting-algorithms-with-python.html, https://hsp1116.tistory.com/33
핵심키워드
- 선택정렬 (Selection Sort)
- 삽입정렬 (Insertion Sort)
- 합병정렬 (Merge Sort)
선택정렬 (Selection Sort)
선택정렬은 이름에 맞게 현재 위치에 들어갈 값을 찾아 정렬하는 방법이다.
<기본 로직>
- 정렬되지 않은 인덱스의 맨 앞(0)에서부터, 이를 포함한 그 이후의 배열 값 중 가장 작은 값을 찾는다.
- 가장 작은 값을 찾으면, 그 값을 현재 인덱스의 값과 바꿔준다.
- 그 다음 인덱스에서도 위 1~2 과정을 반복해준다.
Time Complexity : O(n²) (무조건 전체 비교를 진행하기 때문)
Space Complexity : O(1) ( 단 하나의 배열에서만 진행)
def selection_sort(lst):
for i in range(len(lst)):
tmp = i
for j in range(i, len(lst)):
if lst[tmp] > lst[j]:
tmp = j
lst[i], lst[tmp] = lst[tmp], lst[i]a = [8, 5, 2, 6, 9, 3, 4, 7, 1]selection_sort(a)a # [1, 2, 3, 4, 5, 6, 7, 8, 9]
삽입정렬 (Insertion Sort)
삽입정렬은 현재 위치에서, 그 이하의 배열들을 비교하여 자신이 들어갈 위치를 찾아, 그 위치에 삽입하는 정렬 알고리즘이다.
<기본 로직>
- 두번째 인덱스에서부터 시작한다. 현재 인덱스는 별도의 변수에 저장해주고, 비교 인덱스를 현재 인덱스의 직전 (-1)로 잡는다.
- 별도로 저장해 둔 삽입을 위한 변수와, 비교 인덱스의 배열 값을 비교한다.
- 삽입 변수의 값이 더 작으면 현재 인덱스로 비교 인덱스의 값을 저장해주고, 비교 인덱스를 -1하여 비교를 반복한다.
- 만약 삽입 변수가 더 크면, 비교 인덱스 +1에 삽입 변수를 저장한다.
Time Complexity : O(n²)
Space Complexity : O(1) (단 하나의 배열에서만 진행)
def insertion_sort(lst):
for i in range(1, len(lst)):
temp = lst[i]
j = i-1
while temp < lst[j] and j >= 0:
lst[j], lst[j+1] = lst[j+1], lst[j]
j -= 1a = [8, 5, 2, 6, 9, 3, 4, 7, 1]insertion_sort(a)a # [1, 2, 3, 4, 5, 6, 7, 8, 9]
버블 정렬 (Bubble Sort)
버블 정렬은 매번 연속된 두 개의 인덱스를 비교하여, 정한 기준의 값을 뒤로 넘겨 정렬하는 방식이다. 오름차순으로 정렬할 경우, 비교마다 큰 값을 뒤로 넘기므로 1바퀴를 돌면 가장 큰 값이 맨 뒤에 저장된다.
맨 마지막에는 비교하는 수들 중 가장 큰 값이 저장되기 때문에, (전체 배열의 크기 - 현재까지 순환한 바퀴 수)만큼만 반복해주면 된다.
<기본 로직>
- 버블 정렬은 두 번째 인덱스부터 시작한다. 현재 인덱스 값과, 바로 이전의 인덱스 값을 비교한다.
- 만약 이전 인덱스가 더 크면, 현재 인덱스와 바꿔준다.
- 현재 인덱스가 더 크면, 교환하지 않고 다음 연속된 두 배열값을 비교한다.
- 이를 (전체 배열의 크기 - 현재까지 순환한 바퀴 수)만큼 반복한다.
Time Complexity : 1부터 시작하여, n-1, n-2, …, 1개씩 비교를 반복하기 때문에 선택 정렬과 같이 배열이 어떻든 전체 비교를 진행하므로 O(n²).
Space Complexity : O(1) (단 하나의 배열에서만 진행)
def bubble_sort(lst):
for i in range(1, len(lst)):
for j in range(1, len(lst)-i+1):
if lst[j] < lst[j-1]:
lst[j-1], lst[j] = lst[j], lst[j-1]a = [8, 5, 2, 6, 9, 3, 4, 7, 1]bubble_sort(a)a # [1, 2, 3, 4, 5, 6, 7, 8, 9]
quick sort는 다음에..