StudyData Structure

Sort Algorithm 복습

Sort Algorithm 복습 정리

  1. bubble sort
  • Comparison sort의 한 종류
  • 두 수를 비교해서 정렬하는 방법
  • O(n^2)
  • simple sort
  • 마지막 전 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬
  • 한번 순회가 끝나면 가장 큰 자료가 맨뒤로 이동
  • 2번째 순회에서는 맨 끝에 있는 자료를 정렬에서 제외되는 방식
  • 순회할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어남
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    """
    for문이 2개 = n^2
    데이터가 종속적
    """

    def bubble_sort(arr):
        n = len(arr)

        for i in range(n - 1):
            for j in range(n - 1- i):
                if arr[j] > arr[j+1]:
                    arr[j], arr[j+1] = arr[j+1], arr[j]

    # test code
    if __name__ == "__main__":
        arr = [7, 2, 5, 12, 6]
        bubble_sort(arr)

        print(arr)
  1. insertion sort
  • Comparison sort의 한 종류
  • 두 수를 비교해서 정렬하는 방법
  • O(n^2)
  • Comparison sort 중에 그나마 나음
  • simple sort
  • 두 번째 자료부터 시작하여 그 앞 자료들과 비교하면서 삽입할 위치를 지정
  • 지정한 후, 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 방식
  • 처음 key 값은 두번째 자료부터 시작한다.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    """
    simple sort 중에 insertion sort가 제일 낫다.

    if문을 비교하는데 있어서 insertion sort는 더 적게 사용할 수 있다.
    """

    def insertion_sort(arr):
        n = len(arr)

        for i in range(1, n):
            temp = arr[i]
            j = i-1
            while j!=-1:
                if arr[j] > temp:
                    arr[j+1] = arr[j]
                    j-=1
                else:
                    break
            
            # 이미 있는 j의 다음 위치에 존재하기 위해
            arr[j+1] = temp 

    # test code
    if __name__ == "__main__":
        arr = [7, 2, 5, 12, 6]
        insertion_sort(arr)

        print(arr)
  1. selection sort
  • Comparison sort의 한 종류
  • 두 수를 비교해서 정렬하는 방법
  • O(n^2)
  • simple sort
  • 제자리 정렬 알고리즘의 하나
  • 입력 리스트(정렬되지 않은 값들) 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법
    1
    2
    3
    4
    1) 주어진 배열 중에서 최솟값을 찾는다.
    2) 그 값을 맨 앞에 위치한 값과 교체한다.(두 수를 비교하여 pass도 가능)
    3) 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
    4) 하나의 원소만 남을 때까지 위의 1~3 과정을 반복한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def selection_sort(arr):
    n = len(arr)

    for i in range(n-1):
        min_idx = i

        for j in range(i+1, n):
            if arr[min_idx] > arr[j]:
                min_idx = j

        arr[i], arr[min_idx] = arr[min_idx], arr[i]
        
# test code
if __name__ == "__main__":
    arr = [7, 2, 5, 12, 6]
    selection_sort(arr)

    print(arr)
  1. quick sort
  • Comparison sort의 한 종류
  • 두 수를 비교해서 정렬하는 방법
  • divide and conquer(분할 정복 알고리즘)
  • O(nlogn)
  • 맨 앞의 데이터를 기준으로 선택했을 경우
  • 모든 데이터가 정렬되었을 때, 오히려 많은 시간이 걸리게 된다.(O(n^2))
  • 따라서 이 문제를 해결하는 방법은 기준을 선택할 때 중간 값을 기준으로 선택한다.
    1
    2
    3
    4
    1) 리스트의 중간 원소 pivot을 기준으로 pivot보다 큰 원소는 오른쪽으로 옮긴다.
    2) 리스트의 중간 원소 pivot을 기준으로 pivot보다 작은 원소는 왼쪽으로 옮긴다.
    3) pivot의 오른쪽 리스트와 왼쪽 리스트를 분할하여 재귀를 통해 다시 정렬 반복한다.
    4) 리스트의 크기가 0이나 1이 될때까지 반복한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
"""
patition : pivot을 기준으로 왼쪽에 작은 값이, 오른쪽에 큰 값이 정렬되는 것
"""

def quick_sort(arr, start, end):
    # base case
    if start >= end:
        return
    
    left = start
    right = end
    pivot = arr[(left + right)//2]

    # patition
    # left, right가 교차하기 전이라면
    while left <= right:
        # left가 언제 멈춰야 하는지
        while arr[left] < pivot:
            left+=1

        while pivot < arr[right]:
            right-=1

        # left와 right가 교차하지 않았다면
        # 교환
        if left <= right:
            arr[left], arr[right] = arr[right], arr[left]
            left+=1
            right-=1

    quick_sort(arr, start, right)
    quick_sort(arr, left, end)
        
# test code
if __name__ == "__main__":
    arr = [7, 2, 5, 12, 6, 1, 7, 6, 3, 10, 11]
    quick_sort(arr, 0, len(arr)-1)

    print(arr)
  1. merge sort
  • Comparison sort의 한 종류
  • 두 수를 비교해서 정렬하는 방법
  • divide and conquer(분할 정복 알고리즘)
  • O(nlogn)
  • 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다.
  • 그렇지 않을 경우에는 정렬되지 않는 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
  • 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
  • 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    def merge(arr, start, mid, end):
        left = start
        right = mid + 1
        temp = []

        # 둘 중에 하나라도 범위를 벗어나기 전까지
        while left <= mid and right <= end:
            if arr[left] < arr[right]:
                temp.append(arr[left])
                left+=1
            else:
                temp.append(arr[right])
                right+=1
            
        
        # 만약에 left가 남아있다면
        # temp에다가 넣는다.
        while left <= mid:
            temp.append(arr[left])
            left+=1
            

        while right <= end:
            temp.append(arr[right])
            right+=1
        
        print("arr:"+str(arr))

        # arr에 temp를 업데이트한다.
        arr[start:end+1] = temp

        print("temp:"+str(temp))


    def merge_sort(arr, start, end):
        #base case
        if start >= end:
            return

        mid = (start + end) // 2

        # divide 시점
        merge_sort(arr, start, mid)
        merge_sort(arr, mid+1, end)

        # conquer 시점
        merge(arr, start, mid, end)

    # test code
    if __name__ == "__main__":
        arr = [7, 2, 5, 12, 6, 1, 7, 6, 3, 10, 11]
        merge_sort(arr, 0, len(arr)-1)

        print(arr)
Share