정렬(Sort)

  • 선택정렬
  • 삽입정렬
  • 쉘정렬
  • 힙정렬
  • 합병정렬
  • 퀵정렬
  • 기수정렬
  • 외부정렬

선택정렬(Selection Sort)

  • 배열에서 아직 정렬되지 않은 부분의 원소들 중에서 최솟값을 ‘선택’하여 정렬된 부분의 바로 오른쪽 원소와 교환하는 정렬알고리즘
In [1]:
def selection_sort(a):
    for i in range(0, len(a)-1):
        minimum = i
        for j in range(i, len(a)):
            if a[minimum] > a[j]:
                minimum = j
        a[i], a[minimum] = a[minimum], a[i]

a = [54,88,77,26,93,17,49,10,17,77,11,31,22,44,17,20]
print('정렬 전:\t', end='')
print(a)
selection_sort(a)
print('정렬 후:\t', end='')
print(a)

정렬 전:	[54, 88, 77, 26, 93, 17, 49, 10, 17, 77, 11, 31, 22, 44, 17, 20]
정렬 후:	[10, 11, 17, 17, 17, 20, 22, 26, 31, 44, 49, 54, 77, 77, 88, 93]

삽입정렬(Insertion Sort)

  • 리스트가 정렬된 부분과 정렬 안된 부분으로 나뉘며, 정렬 안된 부분의 가장 왼쪽 원소를 정렬된 부분에 ‘삽입’하는 방식의 정렬알고리즘
In [2]:
def insertion_sort(a):
    for i in range(1, len(a)):
        for j in range(i, 0, -1):
            if a[j-1] > a[j]:
                a[j], a[j-1] = a[j-1], a[j]
     
a = [54,88,77,26,93,17,49,10,17,77,11,31,22,44,17,20]
print('정렬 전:\t', end='')
print(a)
insertion_sort(a)
print('정렬 후:\t', end='')
print(a)

정렬 전:	[54, 88, 77, 26, 93, 17, 49, 10, 17, 77, 11, 31, 22, 44, 17, 20]
정렬 후:	[10, 11, 17, 17, 17, 20, 22, 26, 31, 44, 49, 54, 77, 77, 88, 93]

쉘정렬(Shell Sort)

  • 삽입 정렬에 전처리과정을 추가한 것
  • 전처리과정이란 작은 값을 가진 원소들을 배열의 앞부분으로 옮기며 큰 값을 가진 원소들이 배열의 뒷부분에 자리잡도록 만드는 과정
  • 삽입정렬이 현재 원소를 앞부분에 삽입하기 위해 이웃하는 원소의 숫자끼리 비교하며 한 자리씩 이동하는 단점 보완
  • 대표적인 간격 순서(h-Sequence)
    • Shell : N/2, N/4, ..., 1 (나누기 2를 계속하여 1이 될 때까지의 순서)
    • Hibbard : 2k-1, 2k-1-1, ..., 7, 3, 1
    • Knuth : (3k - 1)/2, ..., 13, 4, 1
    • Sedgewick : ..., 109, 41, 19, 5, 1
    • Marcin Ciura : 1750, 701, 301, 132, 57, 23, 10, 4, 1
In [3]:
def shell_sort(a):
    h = 4       # 3x+1 간격: 1, 4, 13, 40, 121,... 중에서 4 와 1만 사용
    while h >= 1:        
        for i in range(h, len(a)):  # h-정렬 수행
            j = i
            while j >= h and a[j] < a[j-h]: 
                a[j], a[j-h] = a[j-h], a[j]
                j -= h 
        h //= 3  
   
a = [54,88,77,26,93,17,49,10,17,77,11,31,22,44,17,20]
print('정렬 전:\t', end='')
print(a)
shell_sort(a)
print('정렬 후:\t', end='')
print(a)

정렬 전:	[54, 88, 77, 26, 93, 17, 49, 10, 17, 77, 11, 31, 22, 44, 17, 20]
정렬 후:	[10, 11, 17, 17, 17, 20, 22, 26, 31, 44, 49, 54, 77, 77, 88, 93]

힙 정렬(Heap Sort)

  • 힙정렬(Heap Sort)은 이진힙을 이용하는 정렬
  • 먼저 배열에 저장된 데이터의 키를 우선순위로 하는 최대힙(Max Heap)을 구성
  • 루트를 힙의 가장 마지막 노드와 교환한 후
  • 힙 크기를 1 감소시키고
  • 루트로 의 이동으로 인해 위배된 힙속성을 downheap연산으로 복원
  • 힙정렬은 이 과정을 반복하여 나머지 원소들을 정렬
In [4]:
def downheap(i, size):
    while 2*i <= size: 
        k = 2*i     
        if k < size and a[k] < a[k+1]: 
            k += 1 
        if a[i] >= a[k]:
            break      
        a[i], a[k] = a[k], a[i]
        i = k 

def create_heap(a): # 초기 힙 만들기 
    hsize = len(a) - 1   
    for i in reversed(range(1, hsize//2+1)):
        downheap(i, hsize)

def heap_sort(a):
    N = len(a) - 1
    for i in range(N):
        a[1], a[N] = a[N], a[1]
        downheap(1, N-1)
        N -= 1

a = [-1,54,88,77,26,93,17,49,10,17,77,11,31,22,44,17,20]
print('정렬 전:\t', end='')
print(a)
create_heap(a)  # 힙 만들기
print('최대힙 : \t', end='')
print(a)
heap_sort(a)   
print('정렬 후 :\t', end='')
print(a)

정렬 전:	[-1, 54, 88, 77, 26, 93, 17, 49, 10, 17, 77, 11, 31, 22, 44, 17, 20]
최대힙 : 	[-1, 93, 88, 77, 26, 77, 31, 49, 20, 17, 54, 11, 17, 22, 44, 17, 10]
정렬 후 :	[-1, 10, 11, 17, 17, 17, 20, 22, 26, 31, 44, 49, 54, 77, 77, 88, 93]
In [5]:
import heapq
a = [54,88,77,26,93,17,49,10,17,77,11,31,22,44,17,20]
print('정렬전:\t', a)

heapq.heapify(a)
print('힙:\t', a)
 
s = []
while a:
    s.append(heapq.heappop(a))
print('정렬후:\t', s)

정렬전:	 [54, 88, 77, 26, 93, 17, 49, 10, 17, 77, 11, 31, 22, 44, 17, 20]
힙:	 [10, 11, 17, 17, 54, 17, 44, 20, 88, 77, 93, 31, 22, 77, 49, 26]
정렬후:	 [10, 11, 17, 17, 17, 20, 22, 26, 31, 44, 49, 54, 77, 77, 88, 93]

합병 정렬(Merge Sort)

  • 합병 정렬(Merge Sort)은 크기가 N인 입력을 1/2N크기를 갖는 입력 2 개로 분할하고, 각각에 대해 재귀적으로 합병 정렬을 수행한 후, 2 개의 각각 정렬된 부분을 합병하는 정렬알고리즘
  • 합병(Merge)이란 두 개의 각각 정렬된 입력을 합치는 것과 동시에 정렬하는 것
  • 분할 정복(Divide-and-Conquer) 알고리즘: 입력을 분할하여 분할된 입력 각각에 대한 문제를 재귀적으로 해결한 후 취합하여 문제를 해결하는 알고리즘들
In [6]:
def merge(a, b, low, mid, high):
        i = low
        j = mid+1
        for k in range(low, high+1): # a의 앞/뒷부분을 합병하여 b에 저장
            if i > mid:             
                b[k] = a[j] # 앞부분이 먼저 소진된 경우
                j += 1
            elif j > high:
                b[k] = a[i] # 뒷부분이 먼저 소진된 경우
                i += 1
            elif a[j] < a[i]:
                b[k] = a[j] # a[j]가 승자
                j += 1
            else:
                b[k] = a[i] # a[i]가 승자
                i += 1
        for k in range(low, high+1):
            a[k] = b[k]  # b를 a에 복사    
            
def merge_sort(a, b, low, high):
    if high <= low: 
        return
    mid = low + (high - low) // 2
    merge_sort(a, b, low, mid) # 앞부분 재귀호출
    merge_sort(a, b, mid + 1, high) # 뒷부분 재귀호출
    merge(a, b, low, mid, high) # 합병 수행

a = [54,88,77,26,93,17,49,10,17,77,11,31,22,44,17,20]
b = [None] * len(a)
print('정렬 전:\t', end='')
print(a)
merge_sort(a, b, 0, len(a)-1)   
print('정렬 후 :\t', end='')
print(a)

정렬 전:	[54, 88, 77, 26, 93, 17, 49, 10, 17, 77, 11, 31, 22, 44, 17, 20]
정렬 후 :	[10, 11, 17, 17, 17, 20, 22, 26, 31, 44, 49, 54, 77, 77, 88, 93]

퀵정렬(Quick Sort)

  • 입력의 맨 왼쪽 원소(피벗, Pivot)를 기준으로 피벗보다 작은 원소들과 큰 원소들을 각각 피벗의 좌우로 분할한 후, 피벗보다 작은 원소들과 피벗보다 큰 원소들을 각각 재귀적으로 정렬하는 알고리즘
In [7]:
def qsort(a, low, high):
    if low < high:
        pivot = partition(a,low,high)
        qsort(a, low, pivot-1)
        qsort(a, pivot+1, high)

def partition(a, pivot, high):
    i = pivot + 1
    j = high
    while True:
        while i < high and a[i] < a[pivot]:
            i += 1
        while j > pivot and a[j] > a[pivot]:
            j -= 1
        if j <= i:
            break
        a[i], a[j] = a[j], a[i]
        i += 1
        j -= 1

    a[pivot], a[j] = a[j], a[pivot]
    return j

a = [54,88,77,26,93,17,49,10,17,77,11,31,22,44,17,20]
print('정렬 전:\t', a)  
qsort(a, 0, len(a)-1)
print('정렬 후:\t', a)

정렬 전:	 [54, 88, 77, 26, 93, 17, 49, 10, 17, 77, 11, 31, 22, 44, 17, 20]
정렬 후:	 [10, 11, 17, 17, 17, 20, 22, 26, 31, 44, 49, 54, 77, 77, 88, 93]

기수정렬(Radix Sort)

  • 기수 정렬(Radix Sort)은 키를 부분적으로 비교하는 정렬
    • 키가 숫자로 되어있으면, 각 자릿수에 대해 키를 비교
    • 기(radix)는 특정 진수를 나타내는 숫자들 :
      • 10진수의 기 = 0, 1, 2,, 9,
      • 2진수의 기 = 0, 1
  • LSD(Least Significant Digit) 기수 정렬: 자릿수 비교를 최하위 숫자로부터 최상위 숫자 방향으로 정렬
  • MSD(Most Significant Digit) 기수 정렬: 반대 방향으로 정렬
In [8]:
def lsd_sort(a):
    WIDTH = 3  # 스트링의 문자 수
    N = len(a) # 입력 크기
    R = 128    # radix 크기
    temp = [None] * N
    for d in reversed(range(WIDTH)): # d번째 문자 처리 , d  =2, 1, 0    
        count = [0] * (R+1)
        for i in range(N): # 빈도수 계산
            count[ord(a[i][d])+1] += 1  # ord() 인자의 unicode 값 리턴            
        for j in range(1, R): # 빈도수 누적 계산  
            count[j] += count[j-1]                
        for i in range(N): # data 복사
            p = ord(a[i][d])
            temp[count[p]] = a[i]
            count[p] +=  1
        for i in range(N): # t를 a로 복사 
            a[i] = temp[i]
        print('%d번째 문자:\t ' % d, end='')
        for x in a: print(x, ' ', end='')
        print()
a = ['ICN', 'SFO', 'LAX', 'FRA', 'SIN', 'ROM', 'HKG', 'TLV', 
     'SYD', 'MEX', 'LHR', 'NRT', 'JFK', 'PEK', 'BER', 'MOW']
print('정렬 전:\t ', end='')
for x in a: print(x, ' ', end='')
print()
lsd_sort(a)

정렬 전:	 ICN  SFO  LAX  FRA  SIN  ROM  HKG  TLV  SYD  MEX  LHR  NRT  JFK  PEK  BER  MOW  
2번째 문자:	 FRA  SYD  HKG  JFK  PEK  ROM  ICN  SIN  SFO  LHR  BER  NRT  TLV  MOW  LAX  MEX  
1번째 문자:	 LAX  ICN  PEK  BER  MEX  JFK  SFO  LHR  SIN  HKG  TLV  ROM  MOW  FRA  NRT  SYD  
0번째 문자:	 BER  FRA  HKG  ICN  JFK  LAX  LHR  MEX  MOW  NRT  PEK  ROM  SFO  SIN  SYD  TLV