<청춘> 격정적으로 사는 것

밤을 새고 공부한 다음 날 새벽에 느꼈던 생생한 환희와 야생적인 즐거움을 잊을 수 없다

자료구조 알고리즘

[알고리즘] 정렬 (Sorting) / 코드 Python / 선택정렬, 삽입정렬, 퀵정렬, 계수정렬

수학도 2021. 6. 15. 17:28

정렬 (Sorting)

정렬이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 

 

선택 정렬 (Selection Sort)

선택 정렬은 여러 개의 데이터가 있을 때, 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복해서 전체 데이터를 정렬하는 알고리즘이다.

매번 가장 작은 것을 선택 한다는 의미에서 선택 정렬이라고 한다.

 

예)

데이터의 개수 N = 4

빨간색 - 가장 작은 데이터

초록색 - 정렬 완료된 데이터

 

step1

6 2 8 4

step2

2 6 8 4

step3

2 4 8 6

step4

2 4 6 8

 

이처럼 선택 정렬은 가장 작은 데이터를 앞으로 보내는 과정을 N-1번 반복하면 정렬이 완료된다.

 

 

선택 정렬 소스코드

array = [6, 2, 8, 4]

for i in range(len(array)):
    min_index = i
    for j in range(len(array)):
        if array[min_index] > array[j]:
            min_index = j
    array[i], array[min_index] = array[min_index], array[i] # 스와프 : 특정한 리스트가 주어졌을 때 두 변수의 위치를 변경하는 작업

print(array)

[6, 8, 4, 2]

 

선택 정렬 시간 복잡도

O(N^2)

 

N개 중 가장 작은 것을 선택 + N-1 개 중 가장 작은 것을 선택 + ... + 2개 중 가장 작은 것을 선택

= N + (N+1) +(N+2) + ... + 2

= N x (N+1) / 2

=(N^2 + N) / 2

= O(N^2)

 

다른 알고리즘에 비해 매우 비효율적이지만, 코딩 테스트에서는 유용하게 사용된다.

 

 

삽입 정렬 (Insertion Sort)

삽입 정렬은 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤에, 그 위치에 삽입되는 정렬로, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다. 그래서 첫 번째 데이터는 그 자체로 정렬되어 있다고 판단하고, 두번째 데이터부터 정렬을 시작한다.

특정한 데이터를 적절한 위치에 삽입 한다는 의미에서 삽입 정렬이라고 부른다.

 

 

예)

데이터의 개수 N = 4

빨간색 - 정렬할 데이터

초록색 - 정렬 완료된 데이터

 

step1

6 2 8 4

두번째 원소인 2부터 시작

2보다 앞에 있는 (이미 정렬되어 있다고 가정하는) 원소들에서 적절한 위치를 찾는다.

'6'의 왼쪽 혹은 오른쪽 중 적절한 위치인 왼쪽에 삽입한다.

 

step2

2 6 8 4

세번째 원소인 8을 기준으로

8보다 앞에 있는 원소들에서 적절한 위치를 찾는다.

2의 왼쪽 혹은 2와 6 사이 혹은 6의 오른쪽 중 적절한 위치인 6의 오른쪽에 삽입한다.

 

step3

2 6 8 4

네번째 원소인 4를 기준으로

4보다 앞에 있는 원소들에서 적절한 위치를 찾는다.

2의 왼쪽 혹은 2와 6 사이 혹은 6과 8 사이 혹은 8의 오른쪽 중 적절한 위치인 2와 6 사이에 삽입한다.

 

step4

2 4 6 8

N-1 번 반복해서 위와 같이 모든 데이터가 정렬되었다.

 

이처럼 삽입 정렬은 적절한 위치에 삽입하는 과정을 N-1번 반복하면 정렬이 완료된다.

 

 

삽입 정렬 소스코드

array = [6, 2, 8, 4]
for i in range(1, len(array)):
    for j in range(i, 0, -1):
        if array[j] < array[j-1]:	# 한 칸씩 왼쪽으로 이동
            array[j], array[j-1] = array[j-1] ,array[j]
        else:						# 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
            break

print(array)

 

삽입 정렬 시간복잡도

O(N^2)

반복문이 2번 중첩되어 사용되었기 때문에 N x N 해서 N^2 으로 생각하면 편하다.

하지만 리스트의 데이터가 거의 정렬되어 있는 상태라면 최선의 경우 O(N) 의 시간복잡도를 가진다.

 

 

퀵 정렬 (Quick Sort, 빠른 정렬 알고리즘) 

퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다.

퀵 정렬에서는 피벗 (Pivot)이 사용되는데, 피벗이란 큰 숫자와 작은 숫자를 교환할 때 교환하기 위한 '기준'을 말한다.

따라서 퀵 정렬을 수행하기 전에는 피벗(기준)을 어떻게 설정할 것인지 미리 명시해야 한다.

 

퀵 정렬 - 호어 분할 (Hoare Partition) 방식

  • 리스트에서 첫 번째 데이터를 피벗으로 정한다.
  • 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다.
  • 큰 데이터와 작은 데이터의 위치를 교환한다.
  • 큰 데이터와 작은 데이터의 위치가 엇갈리면 ( 교환할 필요 없이 작은 데이터가 왼쪽에 큰 데이터가 오른쪽에 위치하면) 작은 데이터와 피벗의 위치를 교환한다.
  • 분할 완료 : 피벗보다 왼쪽에 있는 데이터는 모두 피벗보다 작고, 오른쪽에 있는 데이터는 모두 피벗보다 크다.
  • 왼쪽 리스트와 오른쪽 리스트에서 개별적으로 퀵 정렬을 수행한다. (재귀 함수)
  • 리스트의 원소가 1이라면 더 이상 분할이 불가능하므로 퀵 정렬이 종료된다. (종료 조건)

 

예)

데이터의 개수 N = 6

빨간색 - 피벗 (기준)

초록색 - 피벗보다 작은 데이터 (오른쪽부터 찾기)

파란색 - 피벗보다 큰 데이터 (왼쪽부터 찾기)

 

 

퀵정렬1

3 4 1 6 2 5
3 2 1 6 4 5
1 2 3 (정렬완료) 6 4 5

 

퀵정렬 (왼쪽 오른쪽 각각)

1 2 3 (정렬완료) 6 4 5
1 (정렬완료) 2 3 (정렬완료) 6 4 5
1 (정렬완료) 2 (정렬완료) 3 (정렬완료) 5 4 6 (정렬완료)
1 (정렬완료) 2 (정렬완료) 3 (정렬완료) 4 5 (정렬완료) 6 (정렬완료)
1 (정렬완료) 2 (정렬완료) 3 (정렬완료) 4 (정렬완료) 5 (정렬완료) 6 (정렬완료)

 

 

퀵정렬 소스코드 1

array = [3, 4, 1, 6, 2, 5]

def quick_sort(array, start, end):
    if start >= end:
        return
    pivot = start
    left = start + 1
    right = end
    while left <= right:
        while left <= end and array[left] <= array[pivot]:
            left += 1
        while right > start and array[right] >= array[pivot]:
            right -= 1
        if left > right:
            array[right], array[pivot] = array[pivot], array[right]
        else:
            array[left], array[right] = array[right], array[left]
    
    quick_sort(array, start, right - 1)
    quick_sort(array, right + 1, end)

quick_sort(array, 0 , len(array)-1)
print(array)
[1, 2, 3, 4, 5, 6]

 

퀵정렬 소스코드 2

array = [3, 4, 1, 6, 2, 5]

def quick_sort(array):
    # 리스트가 하나 이하의 원소만을 담고 있다면 종료
    if len(array) <= 1:
        return array 

    pivot = array[0]    # 피벗은 첫 번째 원소
    tail = array[1:]    # 피벗을 제외한 리스트

    left_side = [x for x in tail if x <= pivot]     # 분할된 왼쪽 부분
    right_side = [x for x in tail if x > pivot]     # 분할된 오른쪽 부분

    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬을 수행하고, 전체 리스트를 반환
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)

print(quick_sort(array))
[1, 2, 3, 4, 5, 6]

 

퀵정렬 시간복잡도

O(NlogN)

 

데이터의 개수가 많을수록 선택 정렬, 삽입 정렬에 비해 압도적으로 빠르게 동작한다.

하지만 리스트의 데이터가 거의 정렬되어 있는 상태라면 최악의 경우 O(N^2) 의 시간복잡도를 가진다.

 

 

계수 정렬 (Count sort)

계수 정렬은 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다.

계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용할 수 있다. 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다. 왜냐하면 계수 정렬을 이용할 때는 모든 범위를 담을 수 있는 크기의 리스트(배열)를 선언해야 하기 때문이다.

 

계수 정렬은 선택 정렬, 삽입 정렬, 퀵 정렬처럼 데이터를 비교하며 위치를 변경하는 비교 기반의 정렬 알고리즘이 아니다. 계수 정렬은 일반적으로 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다.

 

 

예)

데이터 :  7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

 

가장 큰 데이터가 '9' 이고 가장 작은 데이터가 '0'이다. 따라서 우리는 0부터 9까지의 범위를 포함할 수 있게 크기가 10인 리스트를 선언하면 된다. 값은 0으로 초기화한다.

그다음 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시키면 계수 정렬이 완료된다.

 

7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

0 1 2 3 4 5 6 7 8 9
0 0 0 0 0 0 0 1 0 0

7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

0 1 2 3 4 5 6 7 8 9
0 0 0 0 0 1 0 1 0 0

7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

0 1 2 3 4 5 6 7 8 9
0 0 0 0 0 0 0 1 0 1

...

7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

0 1 2 3 4 5 6 7 8 9
2 2 2 1 1 2 1 1 1 2

 

결과 : 리스트에는 각 데이터가 몇 번 등장했는지 그 횟수가 기록된다. 이 리스트에 저장된 데이터 자체가 정렬된 형태 그 자체이다.

 

 

정렬된 리스트를 보려면 리스트의 첫번째 데이터부터 하나씩 그 값만큼 인덱스를 출력하면 된다.

0 1 2 3 4 5 6 7 8 9
2 2 2 1 1 2 1 1 1 2

출력 : 0 0

0 1 2 3 4 5 6 7 8 9
2 2 2 1 1 2 1 1 1 2

출력 : 0 0 1 1

...

0 1 2 3 4 5 6 7 8 9
2 2 2 1 1 2 1 1 1 2

출력 : 0 0 1 1 2 2 3 4 5 5 6 7 8

 

 

계수 정렬 소스코드

array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]

count = [0] * (max(array) + 1)

for i in range(len(array)):
    count[array[i]] += 1

for i in range(len(count)):
    for j in range(count[i]):
        print(i, end=' ')
0 0 1 1 2 2 3 4 5 5 6 7 8 9 9

 

계수 정렬 시간 복잡도

모든 데이터가 양의 정수인 상황에서 데이터의 개수를 N, 데이터 중 최대값의 크기를 K라고 할 때, 계수 정렬의 시간 복잡도는 O(N + K) 이다.

 

 

계수 정렬 공간 복잡도

O(N + K)

 

계수 정렬은 때에 따라서 심각한 비효율성을 초래할 수 있다.

  • 비효율적인 예 : 데이터가 0 과 999,999 두개 일 때에도 리스트의 크기가 100만 개가 되도록 선언해야 한다.
  • 효율적인 예 : 성적의 경우 100점을 맞은 학생이 여러명일 수 있기 때문에 효율적이다.

따라서 계수 정렬은 동일한 값을 가지는 데이터가 여러 개 등장할 때 적합하다. 

 

출처

나동빈, 『이것이 취업을 위한 코딩테스트다 with 파이썬』, 한빛미디어(주), 2020년

'자료구조 알고리즘' 카테고리의 다른 글

[알고리즘] Greedy Algorithm 탐욕 알고리즘 / 파이썬  (0) 2021.07.13
[자료구조 알고리즘] 순차 탐색 / 이진 탐색 / 트리(Tree) / 이진 탐색 트리  (0) 2021.06.23
[파이썬 Python] 탐색 알고리즘 : DFS (깊이 우선 탐색) / BFS (너비 우선 탐색)  (0) 2021.05.27
[자료구조] 그래프 (Graph)  (0) 2021.05.27
[자료구조] 자료구조 기초 : 스택 / 큐 / 재귀함수  (0) 2021.05.27

'자료구조 알고리즘'의 다른글

  • 현재글[알고리즘] 정렬 (Sorting) / 코드 Python / 선택정렬, 삽입정렬, 퀵정렬, 계수정렬

관련글

댓글

티스토리툴바