정렬

데이터를 특정한 기준에 따라 순서대로 나열하는 것을 말하고 프로그램을 작성할 때 가장 많이 사용하는 알고리즘 중 하나다.

정렬 알고리즘은 매우 다양하고 요구하는 문제에 대해서 효과적인 정렬 알고리즘을 선택해 사용하는 것이 프로그램에 효율적인 동작구동에 큰 도움을 준다. 

 

 

선택 정렬 

가장 작은 데이터를 선택해서 맨 앞에 놔두고 이러한 과정을 연속해서 진행하는 정렬로, 작은 값들을 앞에서부터 차곡차곡 쌓는다고 생각하면 좋다. 이 방법은 가장 원시적인 방법으로 매번 가장 작은 것을 선택한다라는 뜻으로 선택 정렬이라 이름 붙게 되었다. 따라서 마지막 요소를 제외한 모든 데이터를 작은 순서로 접근해야 하고 N-1 번 자리교체가 이루어져야 한다. 

 

선택 정렬은 N -1 번 만큼 자리이동을 하고 , 매번 작은 수를 찾기 위해 비교 연산이 필요하다

따라서 연산횟수는  N + ( N -1 ) + ( N - 2) + .... + 2 로 볼 수 있다.

이는 곧    N x ( N - 1) / 2  =>        O(N^2)         의 시간 복잡도를 가진다고 볼 수 있다. 

N^2은 상당히 큰 시간복잡도로 데이터의 개수가 100개가 늘어나면 , 이론적으로 수행 시간은 10000배로 늘어난다.

다른 정렬들과 비교해보면 데이터가 커질수록 상당히 큰 수행시간을 가진다는 것을 확인 할 수 있다

데이터 개수(N)	선택 정렬	퀵 정렬	기본 정렬 라이브러리
N = 100	0.0123 s	0.00156 s	0.00000753 s
N = 1,000	0.354 s	0.00343 s	0.0000365 s
N = 10,000	15.475 s	0.0312 s	0.000248 s

 

 

 선택 정렬 코드.py

 

array = [ 4, 3, 1, 6, 2, 9 ] for i in range( len(array) ):      min_index = i               for j in range( i + 1 , len(array) :             if array[min_index]  >  array[j] :                 min_index = j              array[i] , array[min_indx]  =  array[min_index] , array[i]     print(array)

 

 

 

 

 

삽입 정렬

삽입 정렬은 데이터를 하나씩 확인하여 작은값을 밑에서 쌓는 것이 아닌 적절한 위치에 삽입하는 정렬이다. 

특히 삽입정렬은 필요한 데이터의 위치만 바꾸기 때문에 "데이터가 거의 정렬되어 있을 때" 사용하면 효율적이다.

삽입 정렬은 특저한 데이터가 적절한 위치에 들어가기 전에 , 그 앞 까지의 데이터는 이미 정렬되어 있다고 가정한다. 그 정렬되어 있는 데이터에서 적절한 위치를 찾아서 삽입된다는 특징을 가지고 있다.

또한 삽입정렬은 정렬이 이루어진 원소는 항상 오름차순을 유지한다. 즉 내가 들어갈 위치에 왼쪽 ( 낮은 원소들 ) 은 이미 정렬되어 있음이 보장되어 있다.

 

삽입 정렬의 경우 선택 정렬과 마찬가지로 N이 2번 중첩되어 최악이나 평균의 경우 O(N^2)으로 선택 정렬과 유사한 수행 시간이 소요되지만 데이터가 거의 정렬된 경우에는 O(N)에 가까운 수행 시간 복잡도를 가진다.

따라서 정렬이 거의 되어있는 상황에서 정렬을 수행할 때 퀵 정렬보다 효율적으로 실행될 수 있다. 

 

==> 거의 정렬되어 있는 상태의 리스트인 경우 여타 정렬 알고리즘보다 삽입 정렬이 효율적으로 동작한다. 하지만 대부분의 경우 비효율적이다.

 

 

삽입 정렬 코드.py

 

array = [ 7 , 3,  2, 1, 5, 9, 8 ] for i in range(1, len(array)):       for j  in  range(i , 0, -1):   인덱스 i부터 0까지 감소하면서 진행             if array[j] < array[j - 1]:                      array[j] , array[j - 1]  =  array[j - 1] , array[j]              else:                      break print(array)

 

 

 

 

 

퀵 정렬

 

병합 정렬과 함께 가장 자주 사용되는 정렬 알고리즘으로 , 이 두개의 정렬 알고리즘은 프로그래밍 언어의 정렬 라이브러리에 근간이 되는 알고리즘이다. 

퀵 정렬은 기준 데이터(pivot)를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾼다. 

이 때 기준데이터를 어떻게 설정하냐에 따라서 정렬에 영향을 크게 받기 때문에 기준 데이터에 대해 확실히 설정하고 명시해야 한다.

 

대표적인 방법으로는 리스트의 첫 번째 데이터를 피봇(기준 데이터)로 정한다.

그 후 왼쪽에서부터 원소를 탐색하여 피봇보다 데이터가 큰 데이터를 찾는다, 오른쪽에서는 피봇보다 작은 데이터를 찾는다. 그 후 두개의 조건이 만족된다면 두 개의 데이터의 위치를 바꾼다.

이렇게 반복해나가면 피봇을 기준으로 왼쪽에는 피봇보다 작은 데이터가 오른쪽에는 큰 데이터가 정렬되어 있지 않은 상태로 존재하지만 각 부분에서는 피봇보다 크고 작음이 보장된다. 

그 후 피봇을 제외하여 각 부분을 분할하여 반복해서 위의 작업을 진행한다. 리스트의 개수가 1개가 된다면 더 이상 정렬할 필요가 없으므로 종료한다.

 

퀵 정렬의 시간 복잡도는 O( n log n ) 이고, 매우 빠른편이다. 분할을 할 수록 단계가 나눠지고 이 단계의 높이는 log N 정도로 판단할 수 있다. log의 지수는 평군적으로 2를 나타내고 데이터의 개수가 1000일 때 , logN은 10으로 상대적으로 매우 작은 수를 이해할 수 있다

이러한 log 복잡도는 데이터가 클수록 매우 극명하게 드러난다.

 

하지만 피봇의 적절하게 선택되지 못하고 가장 낮은 피봇이 선택될 때 다시 말해서 데이터가 정렬되어 있다면 하나 하나 검사하고 위치를 바꾸기 때문에 N^2정도로 느리게 동작할 수 도 있다. 그러나 c++과 같이 퀵 정렬을 기반으로 작성된 정렬 라이브러리를 제공하는 프로그래밍 언어들은 최악의 경우에도 시간 복잡도가 O(n log n)이 되는 것을 보장할 수 있도록 피벗값을 설정하도록 추가적인 로직을 더해준다. 

피봇을 선택하는 로직도 퀵 정렬에서 중요한 요소이다 ! 

 

데이터의 개수(N)	N ( 선택 정렬, 삽입 정렬 )	N log N ( 퀵 정렬 )
N = 1,000	1.000.000	10.000
N = 1,000,000	1,000,000,000,000	20,000,000

 

 

퀵 정렬 소스코드 .py

 

(1)

def quick_sorty(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]:                    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 ) qucik_sort(array, 0 , len(array) - 1) print(array)

 

(2)

def qucik_sort( array, start, end):                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) )

 

 

 

 

계수 정렬

 

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

계수 정렬은 최악의 경우에도 수행 시간이 O( N + K )를 보장한다.     ( N: 데이터 개수, K: 최대값 )

이 때 정렬은 빠르게 동작할 뿐만 아니라 원리 또한 매우 간단하다. 그러나 , 계수 정렬은 특정한 리스트에 대해서만 수행이 가능하다.

특정한 조건은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있는 데이터의 모임에서만 사용 가능하다. 무한대의 실수형 데이터에 대해서는 무한한 범위를 가지므로 계수정렬을  사용하기 어렵다. 

 

일반적으로 가장 큰 데이터와 작은 데이터의 값의 차가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다. 예를 들어 0이상 100이하인 성적 데이터를 정려하는 경우 계수 정렬은 효과적으로 정렬할 수 있다. 

이러한 차이가 발생하는 이유는 , 계수 정렬을 이용할 때는   " 모든 범위를 담을 수 있는 크기의 리스트(배열)을 선언해야 하기 때문이다. "

예를 들어 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000개 라면 1,000,001개의 데이터가 들어갈 수 있는 공간의 리스트를 초기화 해야한다. 1이 추가된 이유는 0을 포함하여 초기화하기 때문이다. 

 

계수 정렬은 앞서 다룬 알고리즘처럼 직접 값을 비교한 뒤 위치를 변경하는 정렬방식이 아니다.

별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는 특징을 가진 정렬방식이다. 즉 각 칸의 인덱스 0, 1, 2 , 3에 위치에 카운트 되는 요소의 개수를 저장한다 그 후에 카운트 된 만큼 출력이나 저장을하게 되면 정렬된 리스트가 만들어진다.  즉 데이터의 등장 횟수를 리스트에 저장하는 것이다. 

 

계수 정렬의 시간복잡도는 O( N+K)로 앞에서부터 데이터를 하나씩 확인하면서 Count 리스트에 인덱스 값을 1씩 증가시키는데 N의 시간이 그리고 마지막으로 최대값 K 데이터까지 요소들을 check하므로 K의 시간이 추가로 들게된다. 따라서 데이터의 범위만 한정되어 있다면 효과적으로 사용할 수 있으며 항상 빠르게 동작한다. 사실상 현존하는 정렬 알거리즘 중 기수 정렬(Radix sort)와 함께 가장 빠르다.

 

하지만 계수정렬은 시간복잡도면에서는 뛰어나지만 공간 복잡도에서는 심각한 비효율성을 초래할 수 있다. 예를 들어 데이터의 범위가 0 ~ 999,999일 때 데이터가 0 아니면 999,999로 이분되어 저장되어 있을 때 사용하지도 않는 100만개의 리스트를 초기화해야한다. 

따라서 항상 사용할 수 있는 정렬 알고리즘은 아니며, 동일한 값은 가지는 데이터가 여러개 등장할 때 효과적이다. 데이터의 특성을 파악할 수 있다면 계수정렬을 고려해 볼 만 하다. 

 

(ex)

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

1 1 1 2 3 3 4 4 5 6 6 6 1

 

 

 

계수 정렬 소스코드 .py

 

array = [ 1, 2, 1 , 2 , 20, 3, .. ] 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 = ' ')

 

 

---

파이썬의 정렬 라이브러리 

파이썬은 기본 정렬 라이브러리인 sorted() 함수를 제공한다. sorted()는 퀵 정렬과 동작 방식이 비슷한 병합 정렬을 기반으로 만들어 졌다. 일반적으로 퀵 정렬보단 느리지만 최악의 경우에도 O(nlogn)을 보장하기 때문에 안정적이다.
이러한 sorted()함수는 리스트나 딕셔너리 자료형 등을 입력을 ㅗ받아 결과를 출력한다. 반환 값은 항상 리스트 자료형이다.

리스트 변수 자체에 대해서 바로 정렬을 제공하는  sort( ) 함수도 있다. 이를 이용하면 반환이 아닌 리스트 자체 내부 원소가 바로 정렬된다.

정렬 라이브러리는 항상 최악의 경우에도 시간 복잡도 O(n log n)을 보장한다.  파이썬의 경우 병합 정렬을 기반으로 만들어 졌지만 정확히는 병합 정렬과 삽입 정렬을 리스트에 대해 판한하여 둘 중 하나를 적용하는 하이브리드 방식의 정렬 알고리즘을 사용하고 있다. 

 

---

 

(ex) sorted()

---

array = [7, 5, 9 ..]

res = sorted(array)

print ( res ) 

       0, 1, 2 ...

 

 

 

 

(ex) sort()

---

array = [7, 5, 9 ..]

array.sort() 

print(array) 

 

 

 

 

(ex) sorted()  , key

---

array = [('바나나' , 2) , ('사과' , 5) , ('당근" , 3) ]

 

def setting(data) : 

       return data[1]

 

res = sorted( array, key = setting ) 

print(res)

 

      [('바나나' , 2) , ('당근' , 3) , ('사과" , 5) ]