둔필승총

정렬Sorting

이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 정렬을 이용해서 이진탐색도 가능해지는 것이다.

선택 정렬(Selection Sort) 

: 가장 먼저 생각이 날 수 있는 자연스러운 정렬 알고리즘

  각 위치에 어떤 값이 들어갈지 찾는다.

가장 작은 값을 찾아서 0번 인덱스에 놓고, 두 번째로 작은 값을 찾아서 1번 인덱스에 놓고, 세 번째로 작은 값을 찾아서 2번 인덱스에 놓고.....

즉, 데이터가 무작위로 여러 개 있을 때, 이중에서 가장 작은 데이터를 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 앞에서 2번째 데이터와 바꾸는 과정을 반복하자.

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

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_index]=array[min_index],array[i]

print(array)

선택 정렬의 시간 복잡도는 N-1번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다. 또한 매번 가장 작은 수를 찾기 위해서 비교 연산이 필요하다. 연산 횟수는 N+(N-1)+(N-2) ... 이렇기 때문에 O(N^2)시간복잡도가 나온다.

삽입 정렬(Insertion Sort)

: 각 값이 어떤 위치에 들어갈지 찾는다

정렬 문제의 경우 "절대적인 좋은 답"이란 없다. 상황에 따른 각 알고리즘의 장단점을 파악해야 올바른 알고리즘을 선택할 수 있다. 

삽입 정렬은 선택 정렬처럼 동작 원리를 직관적으로 이해하기 쉽다. 삽입 정렬은 필요할 때만 위치를 바꾸므로 '데이터가 거의 정렬되어 있을 때' 훨씬 효율적이다. 선택 정렬은 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸는 반면 삽입 정렬은 그렇지 않다. 

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

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

for i in range(1,len(array)):
    for j in range(i,0,-1):#인덱스 i부터 1까지 감소하며 반복하는 문법
        if array[j]<array[j-1]:
            array[j],array[j-1]=array[j-1],array[j]
        else:
            break
print(array)

삽입 정렬의 시간복잡도는 O(N^2)이다. 그러나 최선의 경우 O(N)의 시간 복잡도를 가진다. 모두 정렬되어있으면 O(N)의 시간복잡도를 가진다.

합병 정렬(Merge Sort)

 Divide and Conquer에서 대표적으로 설명하는 정렬 방식이다.

 Divide에서는 리스트를 왼쪽 반, 오른쪽 반으로 나눈다. 왼쪽 반을 정렬하는 부분 문제랑 오른쪽 반을 정렬하는 부분 문제로 나누어 주는 것이다.

 Conquer 단계에서는 왼쪽 리스트와 오른쪽 리스트를 각각 정렬해 준다.

 Combine 단계에서는 정렬된 두 리스트를 하나의 정렬된 리스트로 합병한다.

두 리스트를 하나로 Combine 할 때가 중요하다. 이미 정렬되었다고 가정하였을때 왼쪽이 제일 작게 정렬했다고 생각하자. 그럼 왼쪽과 오른쪽의 첫번째 값을 비교해 주어서 더 작은 것을 Combined된 리스트에 넣어준다.

 계속 하나씩 작은것부터 차례대로 넣어주면 한쪽 리스트만 남을거이다. 이것은 이미 정렬되어 있는 것이기 때문에 남은 것을 왼쪽부터 넣으면 된다. 이렇게 하면 하나의 정렬된 리스트가 된다.

def merge(list1, list2):
    i = 0
    j = 0

    # 정렬된 항목들을 담을 리스트
    merged_list = []

    # list1과 list2를 돌면서 merged_list에 항목 정렬
    while i < len(list1) and j < len(list2):
        if list1[i] > list2[j]:
            merged_list.append(list2[j])
            j += 1
        else:
            merged_list.append(list1[i])
            i += 1

    # list2에 남은 항목이 있으면 정렬 리스트에 추가
    if i == len(list1):
        merged_list += list2[j:]

    # list1에 남은 항목이 있으면 정렬 리스트에 추가
    elif j == len(list2):
        merged_list += list1[i:]

    return merged_list

# 테스트
print(merge([1],[]))
print(merge([],[1]))
print(merge([2],[1]))
print(merge([1, 2, 3, 4],[5, 6, 7, 8]))
print(merge([5, 6, 7, 8],[1, 2, 3, 4]))
print(merge([4, 7, 8, 9],[1, 3, 6, 10]))

[1]
[1]
[1, 2]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 3, 4, 6, 7, 8, 9, 10]

결론적으로 합병 정렬을 재귀적으로 구하면 다음과 같다.

def merge(list1, list2):
    merged_list=[]
    index1=0
    index2=0
    while index1<len(list1) and index2<len(list2):
        if list1[index1]<list2[index2]:
            merged_list.append(list1[index1])
            index1+=1
        else:
            merged_list.append(list2[index2])
            index2+=1
    merged_list=merged_list+list1[index1:]+list2[index2:]
    return merged_list
# 합병 정렬
def merge_sort(my_list):
    return merge(merge_sort(my_list[:len(my_list)//2]),merge_sort(my_list[len(my_list)//2:]))
# 테스트
print(merge_sort([1, 3, 5, 7, 9, 11, 13, 11]))
print(merge_sort([28, 13, 9, 30, 1, 48, 5, 7, 15]))
print(merge_sort([2, 5, 6, 7, 1, 2, 4, 7, 10, 11, 4, 15, 13, 1, 6, 4]))

퀵 정렬 (Quick Sort)

Divide and Conquer를 사용하는 또다른 정렬방법은 퀵 정렬(Quicksort)이다. 합병 정렬은 사실 Divide랑 Conquer단계는 생각하기 쉬우나 Combine이 어렵다. 퀵 정렬은 완전히 반대로 Divide과정이 되게 어렵다. 

1. Divide 

Partition에는 2단계가 있다. 먼저 pivot을 정해주는 것이다. 두 번째 단계는 이 pivot을 기준으로 값들을 새롭게 배치하는 것이다. pivot을 기준으로 더 작은 값들은 왼쪽으로, 더 큰 값들은 오른쪽으로 오게 하는 것이다. 

2. Conquer 

pivot 왼쪽과 pivot 오른쪽을 정렬해 준다. 그리고 왼쪽과 오른쪽을 재귀적으로 sort해주면 된다.

3. Combine

할 일이 없다

Divide 부분을 다시 한 번 살펴보자. 일단 partition함수는 parameter를 3개 받는다.

def partition(my_list,start,end):

변수를 3개 두어야 된다. start, big_index, i, pivot. start는 처음 인덱스, b는 pivot값보다 큰 인덱스, i는 계속 진행해가는 인덱스이다. 

아래는 Divide과정인 Partition 하는 과정을 담고 있다.

# 두 요소의 위치를 바꿔주는 helper function
def swap_elements(my_list, index1, index2):
    # 코드를 작성하세요.
    my_list[index1],my_list[index2]=my_list[index2],my_list[index1]

# 퀵 정렬에서 사용되는 partition 함수
def partition(my_list, start, end):
    # 코드를 작성하세요.
    pivot = end
    big_index=0
    for i in range(len(my_list)-1):
        if my_list[i]>my_list[pivot]:
            continue
        else:
            swap_elements(my_list,i,big_index)
            big_index+=1
    swap_elements(my_list,pivot,big_index)
    pivot=big_index
    return pivot

# 테스트 1
list1 = [4, 3, 6, 2, 7, 1, 5]
pivot_index1 = partition(list1, 0, len(list1) - 1)
print(list1)
print(pivot_index1)

# 테스트 2
list2 = [6, 1, 2, 6, 3, 5, 4]
pivot_index2 = partition(list2, 0, len(list2) - 1)
print(list2)
print(pivot_index2)

partition을 했으면 merge_sort처럼 나머지를 재귀함수를 통해서 구하면 된다.

# 두 요소의 위치를 바꿔주는 helper function
def swap_elements(my_list, index1, index2):
    my_list[index1], my_list[index2] = my_list[index2], my_list[index1]
# 퀵 정렬에서 사용되는 partition 함수
def partition(my_list, start, end):
    i = start
    pivot = end
    big_index = start
    while i < pivot:
        if my_list[i] <= my_list[pivot]:
            swap_elements(my_list, i, big_index)
            big_index += 1
        i += 1
    swap_elements(my_list, big_index, pivot)
    pivot = big_index
    return pivot
# 퀵 정렬 (start, end 파라미터 없이도 호출이 가능하도록 수정해보세요!)
def quicksort(my_list,start=0,end=None):
    if end==None:
        end=len(my_list)-1
    if end-start<1:
        return
    pivot = partition(my_list, start, end)
    quicksort(my_list,start,pivot-1)
    quicksort(my_list,pivot+1,end)
# 테스트 1
list1 = [1, 3, 5, 7, 9, 11, 13, 11]
quicksort(list1) # start, end 파라미터 없이 호출
print(list1)

# 테스트 2
list2 = [28, 13, 9, 30, 1, 48, 5, 7, 15]
quicksort(list2) # start, end 파라미터 없이 호출
print(list2)

# 테스트 3
list3 = [2, 5, 6, 7, 1, 2, 4, 7, 10, 11, 4, 15, 13, 1, 6, 4]
quicksort(list3) # start, end 파라미터 없이 호출
print(list3)