정렬 개요 sorting
이번에는 파이썬 자료구조 정렬과 탐색을 살펴보도록 하겠습니다. 정렬의 개념과 알고리즘 동작, 그리고 집합관련 연산의 효율을 향상시키는 방법을 이해하는 포스팅을 해보겠습니다.
우선 정렬 알고리즘 종류에는 Selection Sort, Bubble Sort, Quick Sort, Insertion Sort, Shell Sort, Merge Sort, Heap Sort, Radix Sort 등이 있습니다.
정렬의 사전적인 의미는 데이터를 순서대로 재배열 하는 것입니다.
정렬은 자료구조에서 가장 기본적이고 중요한 알고리즘으로 비교할 수 있는 모든 속성들은 정렬의 기준이 될 수 있습니다. 그리고 정렬은 크게 두가지로 나누어 지는데 오름차순(ascending order)과 내림차순(descending order)입니다.
요즘은 스마트폰으로 검색하지만 예전 종이사전에서 단어를 찾을때 오름차순정렬이 되어 있으니 쉽게 찾을 수 있지 단어의 순서가 뒤죽박죽 기준이 없다면 거기서 내가 원하는 단어를 찾기 위해서는 단어 갯수만큼의 시간이 걸릴겁니다. 끔찍하지요
정렬을 하기에 단어를 살펴봅시다.
레코드는 정렬시커야 될 대상입니다. 레코드는 꼭 하나의 값을 가질수도 여러 값을 가질수도 있습니다. 이를 여러개의 필드를 가지고 있다고 합니다. 이런 레코드에서 어떤 특정한(구분이 가능하고 정렬이 되는) 키를 가지고 정렬을 하면 이 키가 기준이 되는 정렬 키가 됩니다. 정렬 키는 다시 말해서 정렬의 기준이 되는 필드가 됩니다.
정렬 장소에 따른 분류 내부 정렬(internal sort)와 외부 정렬(external sort)가 있습니다.
내부 정렬은 정렬할 자료를 메인 메모리에 올려서 정렬하는 방식이고 정렬 속도가 빠르지만 정렬할 수 있는 자료의 양이 메인 메모리의 용량에 따라서 제한됩니다. 내부 정렬 방식에는 교환 방식(Selection, Bubble, Quick), 삽입 방식(Insertion, Shell), 병합 방식(2-way 병합, n-way 병합), 분배 방식(Radix), 선택 방식(Heap, Tree) 등이 있습니다.
외부 정렬은 정렬할 자료를 보조 기억장치에서 정렬하는 방식이고 대용량의 보조 기억 장치를 사용하기 때문에 내부 정렬보다 속도는 떨어지지만 내부 정렬로 처리할 수 없는 대용량의 자료에 대한 정렬이 가능하다. 외부 정렬 방식에는 병합 방식(2-way 병합, n-way 병합) 이 있습니다.
단순하지만 비효율적인 방법으로는 삽입, 선택, 버블정렬이 있으며
복잡하지만 효율적인 방법으로는 퀵,힙, 병합, 기수정렬, 팀등이 있습니다.
정렬 알고리즘의 안정성은 얼마나 데이터의 이동이 최소화가 되고 유지하는가 입니다.
여기서 30이라는 값이 똑같은 두 요소가 있지만 정렬후에 위치가 서로 달라졌습니다. 이는 안정성을 충족하지 못했다고 합니다.
지금부터 간다한 정렬 알고리즘에 대해서 살펴봅시다.
선택정렬(selection sort)
선택 정렬은 리스트에서 가장 작은 숫자를 선택해서 앞쪽으로 옮기는 방법을 사용합니다.
정렬된 리스트와 정렬되닞 않은 리스트를 두고 오른쪽 리스트에서 가장 작은 숫자를 선택해서 왼쪽으로 이동하는 작업을 바복하면 초기 리스트가 공백이 될때 까지 반복을 합니다. 사실 여기서 꼭 두 리스트가 필요한 것은 아닙니다.
최솟값이 선택이 되면 배열의 첫번째 요소와 교환을 하고 그다음은 두번째 요소 등등 해서 마지막까지 반복하면 됩니다.
1
2
3
4
5
6
7
8
def selection_srot(A):
n = len(A)
for i in range(n-1):
least = i
for j in range(i+1,n):
if(A[j]<A[least]):
least = j
A[i], A[least] = A[least], A[i]
리스트 A가 있을때 일단 크기를 받아옵시다. 그리고 0번부터 n-2번까지 동작을 반복을 합니다. 왜 리스트의 크기가 n인데, 외부 순환은 n-2만 하는지 계속해서 봅시다.
일단 첫번째 녀석 i=0이 최솟값이라고 가정하고 시작을 합시다. 두번째 내부 순환은 i+1에서 n-1 까지 반복을 돌려줍니다. 최솟값이라고 가정한 i와 그 다음 i+1부터 비교를 하는데 이 때 더 작은 값이 있다면 least를 갱신을 해줍시다.
C언어에서는 두 값을 교환하기 위해서는 다른 임시 저장소가 필요했지만 파이썬은 간단하게 교환이 가능합니다.
전체 비교 횟수는 n-1에서 1까지 이므로 시간복잡도는 O(n^2)이 됩니다. 확실히 이는 효율적이지도 않고 안정성을 만족하지도 않지만, 입력 자료의 구성과 상관없이 자료 이동 횟수가 결정되고 알고리즘이 간단하다는 장점을 가지고 있습니다.
삽입정렬(insertion sort)
삽입정렬은 우리가 카드를 손에 줘었을때 정렬하는 방법과 유사합니다. 손안에 정렬해둔 카드가 있고 카드를 추가로 한장씩 뽑을때 그 카드를 순서에 맞춰서 끼워 넣지요 물론 카드를 모두 받은후(삽입후)에도 전체 카드가 정렬이 되어있어야 합니다.
정렬이 안 된 부분의 숫자를 하나씩 정렬된 부분의 적절한 위치를 찾아 끼워 넣는 과정을 반복합시다. 한 번 삽입이 끝나면 정렬이 안 된 부분의 항목수가 줄어드는데, 항목수가 0이 될때 까지 반복을 합니다. 하지만 리스트에서 삽입이 일어나면 한칸씩 뒤로 밀어야하는 시간복잡도 n의 특성이 여기서도 나타납니다.
1
2
3
4
5
6
7
8
9
def insertion_sort(A):
n = len(A)
for i in range(1,n):
key=A[i]
j = i-1
while j>=0 and A[j] > key :
A[j+1] = A[j]
j-=1
A[j+1] = key
리스트 A를 삽입 정렬을 해보자.
첫번째 순환에서 1부터 n-1까지 반복을 합시다. 리스트에서 첫번째는 1이 아니라 0입니다. 1에서 ~ n-1까지이고 0에서 부터는 n까지가 되는거지요 자 그렇다면 key에는 A[1]이 들어오게 되고 j는 i에서 한칸 뺀값 0이 들어오게 됩니다.
즉 A[1]과 A[0]을 비교하게 되는거지요 기존에 잡았던거보다(key) 더 큰게 들어오면 A[j] 한칸 옆에다가 정렬을 하게 됩니다.A[j+1] 이렇게 쪽 반복을 하게 되고 그렇게 바뀐 key값은 A[j+1]에 삽입을하게 됩니다.
시간 복잡도에 있어서는 최선의 경우(이미 정렬되어 있다면) 총 n-1번
최악의 경우에는 랜덤한것도 아니고 역순으로 정렬될때이다. 이때는 O(n^2)의 시간 복잡도를 가지게 됩니다.
버블 정렬(bubble sort)
삽입정렬에 있어서는 새로 카드를 들어올때마다 정렬하는 것이라면 버블 정렬은 바로 인접한 2개의 레코드를 비교하여 순서대로 서로 교환하게 됩니다. 이렇게 비교-교환 과정을 리스트의 전체에 수행(스캔)하게 되고 한번의 스캔이 완료되면 리스트의 오른쪽 끝에 가장 큰 레코드가 만들어지고. 끝으로 이동한 레코드를 제외하고 다시 스캔 반복하게 됩니다.
1
2
3
4
5
6
7
8
9
def bubble_sort(A):
n = len(A)
for i in range(n-1,0,-1)
bChanged = False
for j in ragne(i):
if(A[j]>A[j+1]):
A[j],A[j+1] = A[j+1], A[j]
bChanged = True
if not bChanged: break
일단 정렬할 리스트 A를 가져옵시다. 그리고 시작은 n-1부터 0까지 -1씩 뒤에서 살펴봅시다.
bChanged로 비교를 했을때 교환이 일어나지 않았다고 주고 시작을 합시다.
두번째 순환에서 j부터 i까지 돌리는데 인접한것중 앞에 있는게 더 클경우에는 둘의 위치를 바꿔주고 교환을 체크하는 변수를 True로 지정을 해줍시다.
그렇다면 False가 나올때 까지 위 과정을 반복하게 됩니다.
버블 정렬은
비교 횟수에 있어서는 최상, 평균, 최악의 경우 모두 시간 복잡도가 동일하다는 특성을 가지고 있습니다.
이동 횟수에 있어서는 역순정렬이라는 최악의 경우 이동횟수 = 비교횟수 x 3 이 되고
이미 정렬된 경우에는 0회, 평균적으로 O(n^2)를 따르게 됩니다.
이동연산은 비교연산 보다 더 많은 시간이 소요되기에 레코도의 이동과다는 단점입니다.
Comments powered by Disqus.