알고리즘 6주차 - 정렬 알고리즘

Keywords : 선택 정렬,  퀵 정렬, 삽입 정렬, 쉘 정렬

 

선택 정렬 알고리즘

• 모든 항목 파악 후 원하는 순서대로 기입
• 시간 복잡도 : O(n^2)

# 배열을 작은 정수에서 큰 정수로 정렬하는 코드

def findSmallest(arr):
    smallest = arr[0]
    smallest_index = 0
    for i in range(len(arr)):
        if arr[i] < smallest:
            smallest = arr[i]
            smallest_index = i
    return smallest_index

def selectionSort(arr):
    newArr = []
    for i in range(len(arr)):
        smallest_index = findSmallest(arr)
        newArr.append(arr.pop(smallest_index))
    return newArr

nowarr = [5, 3, 6, 2, 10]
print (selectionSort(nowarr))

 

퀵 정렬 알고리즘

• 기준 원소 선택하여 나머지 원소를 비교하여 분류
• 하위 배열에 대해 재귀적으로 호출한다는 특징 (후에 합쳐서 전체 배열 구함)
• 시간 복잡도 : 
  • 첫 번째 원소를 기준 원소로 선택 : O(n)
  • 가운데 원소를 기준 원소로 선택 : O(logn)
  • 최선의 경우 : O(n) * O(logn) = O(nlogn)
  • 최악의 경우 : O(n) * O(n) = O(n^2)

# 방법 1 =====================================
def quickSort(array):
    if len(array) < 2:
        return array
    else:
        pivot = array[0]
        less = [i for i in array[1:] if i < pivot]
        greater = [i for i in array[1:] if i > pivot]
        return quickSort(less) + [pivot] + quickSort(greater)

print(quickSort([10, 5, 2, 3]))

# 방법 2 =====================================
def quickSort(a, start, end):
    if end - start <= 0:
        return
    
    pivot = a[end]  #기준값 = 5
    i = start   #0
    for j in range(start, end): #0~9
        if a[j] <= pivot:
            a[i], a[j] = a[j], a[i]
            i += 1

    a[i], a[end] = a[end], a[i]
    quickSort(a, start, i - 1)
    quickSort(a, i + 1, end)

arr = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]
quickSort(arr, 0, len(arr) - 1)
print(arr)

 

삽입 정렬 알고리즘

• 배열을 정렬된 부분과 안 된 부분으로 나눔
• 정렬 안 된 부분의 가장 왼쪽 원소를 정렬된 부분의 적절한 위치로 삽입
• 마지막엔 정렬 안 된 부분에 원소 없어짐
• 시간 복잡도 :
  • 최선의 경우 : 정렬 되어 있을 때, while 안 돌아가므로 O(n)
  • 최악의 경우 : O(n^2)

# 방법 1 =====================================
def find_ins_idx(r, v): 
    # 결과 리스트와 값을 입력하여, 값을 결과 리스트 중 어디에 넣을지를 판별
    for i in range(0, len(r)):
        if v < r[i]:
            return i
    return len(r)

def ins_sort(a):
    # a 리스트를 pop 해오면서 결과 리스트 중 적절한 곳에 배치 반복
    result = []
    while a:
        value = a.pop(0)
        ins_idx = find_ins_idx(result, value)
        result.insert(ins_idx, value)
    return result

d = [2, 4, 5, 1, 3]
print(ins_sort(d))

# 방법 2 =====================================
def ins_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

d = [2, 4, 5, 1, 3]
ins_sort(d)
print(d)

 

쉘 정렬 알고리즘

• 삽입 정렬을 이용하여 배열 뒷 부분에 있는 작은 숫자 앞으로, 그 반대 작업도 해주며 빠르게 수행
• 간격 (Gap) 을 이용하여 그룹을 이룸, 마지막에는 1로 해야 함
• 입력 크기가 크지 않은 경우 매우 좋은 성능
• 임베디드 시스템에서 주로 사용 : 간격에 따른 그룹 별 정렬 방식이 매우 적합하기 때문
• 시간 복잡도 :
  • 간격 선정에 따라 좌우됨
  • 히바드 간격의 경우 : O(n^1.5)
  • 일반적인 경우 : O(n^1.25), Marcin Ciura 간격 : 1, 4, 10, 23, 57, ...
  • 최악의 경우 : O(n^2)

def shell_Sort(a):
    h = 4
    while h >= 1:
        # print("while 안에서의 h: " + str(h))
        for i in range(h, len(a)):
            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)