자료구조 - 정렬 [선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬]

정렬 : 데이터를 특정한 기준에 따라서 순서대로 나열하는 것

 

선택 정렬(Selection sort)

: 여러 데이터들중 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하는 것

 

1. 처음에는 정렬되어 있지 않으므로 가장 작은 1을 선택해서 맨앞의 숫자인 5와 swap

2. 맨앞의 1을 제외하고 나머지 숫자들 중에서 가장 작은 2를 선택해서 맨앞의 숫자인 5와 swap

3. 맨앞의 1, 2를 제외하고 나머지 숫자들 중에서 가장 작은 3을 선택해서 맨앞의 숫자인 3과 swap(이미있다.)

4. 맨앞의 1, 2, 3을 제외하고 나머지 숫자들 중에서 가장 작은 5를 선택해서 맨앞의 숫자인 7과 swap

5. 맨앞의 1, 2, 3, 5를 제외하고 나머지 숫자들 중에서 가장 작은 7을 선택해서 맨앞의 숫자인 7과 swap(이미있다.)

6. 맨앞의 1, 2, 3, 5, 7을 제외하고 나머지 숫자는 9 하나 이므로 swap 안해도된다. (이미있다.)

- 이미 하나 남은 것은 swap할 필요가 없으므로 

 

이처럼 선택정렬은 가장작은 데이터를 앞으로 보내는 과정을 N - 1번 반복하면 정렬이 완료된다.

 

파이썬의 swap

ls = [3, 5]
ls[0], ls[1] = ls[1], ls[0]
print(ls)

[5, 3]

다른언어들은 tmp로 임시로 swap 변수를 만들어야 하지만 파이썬은 위와같이 간단하게 한줄 스왑이 가능하다.

 

그럼 위의 선택정렬을 파이썬으로 만들어보자

ls = [5, 1, 3, 7, 2, 9]

# ls에 들어있는 값 갯수만큼 반복
for i in range(len(ls)):
    # 가장작은 숫자가 들어가야 할 index : 맨 앞부터 하나씩 늘어 나면서 들어가므로
    min_id = i
    # 맨 마지막은 어짜피 가장 큰수 이므로 계산 안해도 된다.
    if i == len(ls) - 1:
        break
    # ls중 에서 가장 작은 값의 index를 찾자
    # -> 맨 앞에 있는 인덱스를 제외하고 가장 작은 것을 찾자 : 만약 스왑이 안된다면 맨앞에 있는 것이 가장 작은 것.
    for j in range(i + 1, len(ls)):
        if ls[min_id] > ls[j]:
            # 가장 작은 값의 인덱스를 저장해놨다가.
            min_id = j
    # 가장 작은 값의 인덱스를 찾았으면 맨앞의 값과 swap
    ls[i], ls[min_id] = ls[min_id], ls[i]

[1, 2, 3, 5, 7, 9]

총 비교횟수 = (시간복잡도)를 계산해보자

N = len(ls)라고 했을 때

 

N - 1 + N - 2 + ... + 2 = (N - 1) * N / 2 - 1 => O(N^2) 라고 할 수 있다.

간단하게 이중 반복문이므로 O(N^2) 이렇게 된다.

선택정렬은 다른 정렬들과는 다르게 매우 비효율적이다. 

왜냐하면 최선의 경우(이미 정렬되어 있는경우)조차 모두 비교하기 때문이다. 

 

위 선택정렬은 가장 기본적으로 리스트에서 가장 작은 값을 찾는 알고리즘이다. 

가장 기본적인 만큼 많은 반복을 통해 익숙해져야 한다.

 

삽입정렬(Insertion sort)

: 데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입한다.

1.  특정한 데이터가 적절한 위치에 들어가기전에 그 앞까지의 데이터는 이미 정렬되어 있다고 가정

2.  정렬되어 있는 데이터리스트에서 적절한 위치를 찾은 후 해당 위치에 삽입 

 

1. 첫번째 데이터 5는 그자체로 정렬되어 있다고 판단하고 두번째 데이터인 1이 어떤위치로 들어갈지 판단,

   1은 5보다 작으므로 5의 왼쪽으로 들어간다.

2. 그다음 데이터인 3은 그앞의 데이터 1,5는 정렬되어 있다고 판단하고 어떤 위치로 들어갈지 판단,  

   3은 1보다 크고 5보다 작기 때문에 1의 바로 오른칸에 삽입

3. 그다음 데이터인 7은 그앞의 1, 3, 5는 정렬되어 있다고 판단하고 어떤위치로 들어갈지 판단,

   7은 5보다 크기 때문에 5의 바로 오른칸에 삽입

4. 그다음 데이터인 2는 그앞의 1, 3, 5, 7는 정렬되어 있다고 판단하고 어떤위치로 들어갈지 판단,

   2은 1보다 크기 때문에 1의 바로 오른칸에 삽입

5. 그다음 데이터인 9은 그앞의 1, 2, 3, 5, 7가 정렬되어 있다고 판단하고 어떤위치로 들어갈지 판단,

   9는 7보다 크기 때문에 7의 오른칸에 삽입(이미 올바른 곳에 있다.)

 

이를 파이썬 코드로 작성해보자

ls = [5, 1, 3, 7, 2, 9]

# 2번째 숫자 부터 시작하기 때문에
for i in range(1, len(ls)):
    # 이미 앞에는 정렬되어 있다고 판단해서 정렬된 맨 앞 부터
    for j in range(i):
        # 2번째 숫자가 작다면 해당칸과 자리를 바꿈으로서 왼쪽으로 이동
        if ls[i] < ls[j]:
            ls[i], ls[j] = ls[j], ls[i]
            print(ls)
        # 2번째 숫자가 크다면 자리를 바꿀필요가 없다.
        else:
            continue

[1, 5, 3, 7, 2, 9]
[1, 3, 5, 7, 2, 9]
[1, 2, 5, 7, 3, 9]
[1, 2, 3, 7, 5, 9]
[1, 2, 3, 5, 7, 9]

- 선택 정렬과 마찬가지로 이중 반복문이 사용되었으므로 시간복잡도는 O(N^2) 이다.

- 최선의 경우(이미정렬되어 있는경우) O(N)의 시간복잡도를 가진다.

- 필요할 때만 위치를 바꾸므로 '데이터가 거의 정렬되어 있을 때 '매우 효율적'

 

퀵 정렬(Quick sort)

- 기준 데이터를 설정하고 기준보다 큰 데이터와 작은 데이터의 위치를 바꾼다.

: 기준(pivot)을 설정하여 큰 숫자와 작은 숫자를 교환하고 리스트를 분할 한다.

 

- 호어분할

: 리스트에서 첫 번쨰 데이터를 피벗으로 정한다.

1. 왼쪽에서 부터 피벗 보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다.

2. 큰 데이터와 작은 데이터의 위치를 서로 교환해준다. (1 - 2 반복)

3. 큰 데이터와 작은 데이터가 위치를 바꾸고 맞물린다. 이중 작은 데이터와 피봇의 위치를 변경한다.

4. 변경된 피봇의 위치로 부터 좌측과 우측은 분할된 리스트가 된다.

- (변경된 피봇의 위치는 정렬이 끝날 때까지 변경되지 않는다. 정렬된 것이다.)

5. 분할 된 리스트들 각각 (1 - 4 반복)을 하며 계속 리스트들이 분할되며 정렬된다. 

- 재귀적으로 리스트들이 정렬된다.

 

 

1. 가장 처음인 5가 피봇이된다. 

2. 피봇을 기준으로 좌측부터 피봇보다 큰 수 8을 찾고 우측은 피봇보다 작은 수 2을 찾았다.

- 8과 2의 위치를 교환한다.

3. 피봇을 기준으로 변경된 위치들부터 좌측과 우측 각각 큰 수 9와 작은수 1을 찾았다.

- 9와 1의 위치를 교환한다.

4. 좌측과 우측의 순서가 엇갈리므로 피봇인 5와 작은 수 1의 위치를 교환한다.

5. 피봇인 5를 기준으로 좌측과 우측의 리스트를 분할하고 각 리스트마다 (1 - 5)를 반복한다.

- 재귀적인 반복이다.

 

위와 같은 설명을 기준으로 파이썬으로 작성해보자

def quick_sort(arr, start, end):
    if start >= end:
        return
    pivot = start
    left = start + 1
    right = end
    # 엇갈릴 때까지 반복
    while left <= right:
        # left값이 pivot값보다 큰 값이 나올 때 까지 left를 찾는다. / pivot값이 가장 클경우 left는 end까지 진행
        while left <= end and arr[left] <= arr[pivot]:
            left += 1
        # right값이 pivot값보다 작은 값이 나올 때 까지 right를 찾는다. / pivot값이 가장 작은 경우 right은 start + 1까지 진행
        while right > start and arr[right] >= arr[pivot]:
            right -= 1
        # 일반적인 경우 left와 right 자리 swap
        if left <= right:
            arr[left], arr[right] = arr[right], arr[left]
        # 엇갈렸을 경우 left > right : 바뀐 자리의 right값이 left값보다 작으므로 pivot과 right값을 swap
        else:
            arr[right], arr[pivot] = arr[pivot], arr[right]
            # 새로운 피봇은 right위치이다.
            pivot = right

    # pivot을 기준으로 pivot을 제외하고 리스트를 분할해서 다시 반복
    quick_sort(arr, start, pivot - 1)
    quick_sort(arr, pivot + 1, end)


ls = [5, 3, 2, 4, 9, 1, 6, 8, 7]
quick_sort(ls, 0, len(ls) - 1)
print(ls)

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

 

퀵정렬에서 시간복잡도를 알아보자 

 

참고로 컴퓨터분야에서 logN 의 의미는 아래와 같다.

총 숫자가 N개라고 하자.

분할이 일어날 때마다 정확히 왼쪽과 오른쪽이 절반씩 분할된다면 

재귀 함수의 깊이 : logN

총 수행되는 재귀함수의 호출 횟수 : N * logN

즉 O(N * logN) 이다.

 

최악의 경우 : 1개와 나머지 로 나눠지는 경우

재귀함수의 호출 횟수 : N + (N - 1) + ... + 1 

이경우 O(N^2) 의 시간복잡도를 가진다.

 

계수 정렬 (Counting sort)

특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘 

- 리스트 원소의 값의 범위를 알고 있을 경우 정렬할 때 쓸수 있다.

- 리스트 원소의 값의 범위 만큼 새로운 배열을 만들어 리스트의 원소가 몇번 나왔는지

센다.

- 인덱스가 0인 것부터 차례대로 나온횟수 만큼 나열한다.

->0011122233 

 

이를 파이썬으로 구현해보자

ls = [2, 1, 0, 2, 2, 1, 3, 1, 0, 3]

index = [0 for _ in range(max(ls) + 1)]
for i in ls:
    index[i] += 1

for i in range(len(index)):
    for _ in range(index[i]):
        print(i, end = ' ')

0 0 1 1 1 2 2 2 3 3 

계수 정렬의 시간복잡도

 

데이터의 갯수를 N, 데이터중 최대크기를 K라고 했을 때

계수 정렬의 시간복잡도는 O(N + K)이다.

 

앞에서 부터 갯수를 하나씩 확인하고 최대크기 만큼 한번더 확인하기 때문이다.

 

계수 정렬의 공간복잡도(잡아먹는 메모리의 크기)

일반 배열 하나, 가장 큰 값만큼의 인덱스 배열 하나 따라서 O(N + K)