알고리즘

[알고리즘과 자료 구조] 정렬(feat. 손코딩)

framecreator 2021. 11. 16. 15:28

*** 아래의 내용은 패스트 캠퍼스 알고리즘 강의 자료(이준희 강사님 저)를 강의를 들으면서 정리한 내용입니다. ***

1. 정렬 (sorting) 이란?

정렬 (sorting): 어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 것
정렬은 프로그램 작성시 빈번하게 필요로 함
다양한 알고리즘이 고안되었으며, 알고리즘 학습의 필수

2. 버블 정렬 (bubble sort) 이란?

두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘

버블 정렬

https://visualgo.net/en/sorting

for num in range(len(data_list)) 반복
swap = 0 (교환이 되었는지를 확인하는 변수를 두자)
반복문 안에서, for index in range(len(data_list)-num-1) n-1번 반복해야 하므로
반복문안의 반복문 안에서, if data_list[index] > data_list[index + 1] 이면
data_list[index], data_list[index + 1] = data_list[index + 1], data_list[index]
swap += 1
반복문 안에서, if swap == 0 이면, break 끝

버블 정렬 코드로 구현하기

def bubblesort(data):
    for index in range(len(data) - 1):
        swap = False
        for index2 in range(len(data) - index - 1):
            if data[index2] > data[index2 + 1]:
                data[index2], data[index2 + 1] = data[index2 + 1], data[index2]
                swap = True
        
        if swap == False:
            break
    return data

알고리즘 분석

반복문이 두 개 O(𝑛제곱)
최악의 경우, 𝑛∗(𝑛−1)/2
완전 정렬이 되어 있는 상태라면 최선은 O(n)

3. 선택 정렬 (selection sort) 이란?

다음과 같은 순서를 반복하며 정렬하는 알고리즘

주어진 데이터 중, 최소값을 찾음
해당 최소값을 데이터 맨 앞에 위치한 값과 교체함
맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복함

https://visualgo.net/en/sorting

선택정렬

for stand in range(len(data_list)-1) 로 반복
lowest = stand 로 놓고,
for num in range(stand, len(data_list)) stand 이후부터 반복

내부 반복문 안에서 data_list[lowest] > data_list[num] 이면,
lowest = num
data_list[num], data_list[lowest] = data_list[lowest], data_list[num]

선택정렬 코드로 구현하기

def selection_sort(data):
    for stand in range(len(data) - 1):
        lowest = stand
        for index in range(stand + 1, len(data)):
            if data[lowest] > data[index]:
                lowest = index
        data[lowest], data[stand] = data[stand], data[lowest]
    return data

알고리즘 분석

반복문이 두 개 O(𝑛의2제곱)

실제로 상세하게 계산하면, 𝑛∗(𝑛−1)/2

4. 퀵 정렬 (quick sort) 이란?

정렬 알고리즘의 꽃
기준점(pivot 이라고 부름)을 정해서, 기준점보다 작은 데이터는 왼쪽(left), 큰 데이터는 오른쪽(right) 으로 모으는 함수를 작성함
각 왼쪽(left), 오른쪽(right)은 재귀용법을 사용해서 다시 동일 함수를 호출하여 위 작업을 반복함
함수는 왼쪽(left) + 기준점(pivot) + 오른쪽(right) 을 리턴함.

quicksort 함수 만들기
만약 리스트 갯수가 한개이면 해당 리스트 리턴
그렇지 않으면, 리스트 맨 앞의 데이터를 기준점(pivot)으로 놓기
left, right 리스트 변수를 만들고,
맨 앞의 데이터를 뺀 나머지 데이터를 기준점과 비교(pivot)
기준점보다 작으면 left.append(해당 데이터)
기준점보다 크면 right.append(해당 데이터)
return quicksort(left) + pivot + quicksort(right) 로 재귀 호출
리스트로 만들어서 리턴하기: return quick_sort(left) + [pivot] + quick_sort(right)

알고리즘 분석

병합정렬과 유사, 시간복잡도는 O(nlogn)
단, 최악의 경우 맨 처음 pivot이 가장 크거나, 가장 작으면 모든 데이터를 비교하는 상황이 나옴 O(𝑛의 2제곱)

퀵정렬 코드로 구현하기

def qsort(data):
    if len(data) <= 1:
        return data
    
    pivot = data[0]

    left = [ item for item in data[1:] if pivot > item ]
    right = [ item for item in data[1:] if pivot <= item ]
    
    return qsort(left) + [pivot] + qsort(right)

5. 병합 정렬 (merge sort)이란?

재귀용법을 활용한 정렬 알고리즘

리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

https://visualgo.net/en/sorting

병합정렬

데이터가 네 개 일때

예: data_list = [1, 9, 3, 2]
먼저 [1, 9], [3, 2] 로 나누고
다시 앞 부분은 [1], [9] 로 나누고
다시 정렬해서 합친다. [1, 9]
다음 [3, 2] 는 [3], [2] 로 나누고
다시 정렬해서 합친다 [2, 3]
이제 [1, 9] 와 [2, 3]을 합친다.
1 < 2 이니 [1]
9 > 2 이니 [1, 2]
9 > 3 이니 [1, 2, 3]
9 밖에 없으니, [1, 2, 3, 9]

mergesplit 함수 만들기

만약 리스트 갯수가 한개이면 해당 값 리턴
그렇지 않으면, 리스트를 앞뒤, 두 개로 나누기
left = mergesplit(앞)
right = mergesplit(뒤)
merge(left, right)

merge 함수 만들기

리스트 변수 하나 만들기 (sorted)
left_index, right_index = 0
while left_index < len(left) or right_index < len(right):
만약 left_index 나 right_index 가 이미 left 또는 right 리스트를 다 순회했다면, 그 반대쪽 데이터를 그대로 넣고, 해당 인덱스 1 증가
if left[left_index] < right[right_index]:
sorted.append(left[left_index])
left_index += 1
else:
sorted.append(right[right_index])
right_index += 1

병합정렬 코드로 구현하기

def merge(left, right):
    merged = list()
    left_point, right_point = 0, 0
    
    # case1 - left/right 둘다 있을때
    while len(left) > left_point and len(right) > right_point:
        if left[left_point] > right[right_point]:
            merged.append(right[right_point])
            right_point += 1
        else:
            merged.append(left[left_point])
            left_point += 1

    # case2 - left 데이터가 없을 때
    while len(left) > left_point:
        merged.append(left[left_point])
        left_point += 1
        
    # case3 - right 데이터가 없을 때
    while len(right) > right_point:
        merged.append(right[right_point])
        right_point += 1
    
    return merged


def mergesplit(data):
    if len(data) <= 1:
        return data
    medium = int(len(data) / 2)
    left = mergesplit(data[:medium])
    right = mergesplit(data[medium:])
    return merge(left, right)

알고리즘 분석

단계별 시간 복잡도 O(n) * O(log n) = O(n log n)

6. 삽입 정렬이란?

삽입 정렬 (insertion sort) 란?

삽입 정렬은 두 번째 인덱스부터 시작
해당 인덱스(key 값) 앞에 있는 데이터(B)부터 비교해서 key 값이 더 작으면, B값을 뒤 인덱스로 복사
이를 key 값이 더 큰 데이터를 만날때까지 반복, 그리고 큰 데이터를 만난 위치 바로 뒤에 key 값을 이동

https://visualgo.net/en/sorting

insertion sort

데이터가 네 개 일때

예: data_list = [9, 3, 2, 5]
처음 한번 실행하면, key값은 9, 인덱스(0) — 1 은 0보다 작으므로 끝: [9, 3, 2, 5]
두 번째 실행하면, key값은 3, 9보다 3이 작으므로 자리 바꾸고, 끝: [3, 9, 2, 5]
세 번째 실행하면, key값은 2, 9보다 2가 작으므로 자리 바꾸고, 다시 3보다 2가 작으므로 끝: [2, 3, 9, 5]
네 번째 실행하면, key값은 5, 9보다 5이 작으므로 자리 바꾸고, 3보다는 5가 크므로 끝: [2, 3, 5, 9]

for stand in range(len(data_list)) 로 반복
key = data_list[stand]
for num in range(stand, 0, -1) 반복

내부 반복문 안에서 data_list[stand] < data_list[num — 1] 이면,
data_list[num — 1], data_list[num] = data_list[num], data_list[num — 1]

삽입 정렬 코드로 구현하기

def insertion_sort(data):
    for index in range(len(data) - 1):
        for index2 in range(index + 1, 0, -1):
            if data[index2] < data[index2 - 1]:
                data[index2], data[index2 - 1] = data[index2 - 1], data[index2]
            else:
                break
    return data

알고리즘 분석

반복문이 두 개 O(𝑛의2제곱)
최악의 경우, 𝑛∗(𝑛−1)/2
완전 정렬이 되어 있는 상태라면 최선은 O(n)

*** 위의 내용은 패스트 캠퍼스 알고리즘 강의 자료(이준희 강사님 저)를 강의를 들으면서 정리한 내용입니다. ***

7. 힙정렬 (Heap Sort)

힙 정렬은 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법이다. 이진 완전 나무를 배열에다 접목시킨 절묘한 알고리즘이다. 처음에는 나무 아래에서 위로 각 원소들을 최대값 힙 조건에 맞게 정리한 뒤, 나무 뿌리에 있는 자료를 차례차례 나무 뒤로 옮기면서 힙을 정렬된 배열로 바꾼다. 뿌리에는 힙 나무 맨 뒤에 있던 원소가 왔다가, 다시 힙 조건에 맞는 위치로 내려간다. 시간복잡도가 O(nlogn)인 정렬 알고리즘 중에서는 부가적인 메모리를 요하지 않는다는 게 큰 장점인 정렬 방식이다.

8. 쉘 정렬 (Shell Sort)

삽입정렬의 개념을 확대하여 일반화한 정렬방법이다. 알고리즘이 간단하여 프로그램으로 쉽게 구현할 수 있다. 수행 능력도 삽입 정렬보다 우수한 것으로 평가된다. 멀리 있는 레코드들끼리 비교 및 교환될 수 있으므로, 어떤 데이터가 제 위치에서 멀리 떨어져 있다면 여러 번의 교환이 발생하는 버블정렬 방식의 단점을 해결할 수 있다.

9. 기수 정렬(Radix Sort)

데이터의 비교를 통한 정렬이 아닌 분산 정렬을 이용한 정렬 방법이며 자릿수가 있는 데이터(정수, 문자열 등)에만 사용 가능하다. 각 자리수를 기준으로 점차 정렬을 진행한다.

10. 정렬 별 장단점 비교

11. 정렬 별 시간 복잡도 비교

참조

https://velog.io/@jaeyunn_15/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B0%81-%EC%A0%95%EB%A0%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B9%84%EA%B5%90

https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html