[Algorithm 이론] Sort 알고리즘 정리 | (ft. Bubble / Counting Sort)


 








Bubble/Counting Sort 방식에 대한 정리;


Sort 알고리즘3

정렬(Sort)이란?

“2개 이상의 자료를 특정 기준에 의해 작은 값부터 큰 값(오름차순: ascending), 또는 그 반대의 순서대로(내림차순: descending) 재배열하는 것”

[관련용어] Key: 자료를 정렬할 때 기준이 되는 특정 값

(ex1) 서류 번호대로 정렬하기 ⇒ key := 서류 번호

(ex2) 카드 번호대로 정렬하기 ⇒ key := 카드 번호

(대표적인) 정렬 방식의 정류

  • 버블 정렬 (Bubble Sort)
  • 카운팅 정렬 (Counting Sort)
  • 선택 정렬 (Selection Sort)
  • 퀵 정렬 (Quick Sort)
  • 삽입 정렬 (Insertion Sort)
  • 병합 정렬 (Merge Sort)

https://youtu.be/ZZuD6iUe3Pc

1. Bubble Sort

“인접한 두 개의 원소를 비교하며 자리를 계속 교환하는 방식”

[Process]

  1. 첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리까지 이동
  2. 한 단계가 끝나면 가장 큰 원소 또는 가장 작은 원소가 마지막 자리로 정렬됨

※ 교환하며 자리를 이동하는 모습이 물 위에 올라오는 거품모양(bubble) 같아서 버블 정렬이라고 함

※ 시간복잡도 = O(n2)O(n^{2})

EXAMPLE: {55, 7, 78, 12, 42}를 버블 정렬하는 과정

# 첫 번째 패스 (첫 번째 원소인 55부터)
| 55 | 7 | 78 | 12 | 42 | ; 55와 인접한 7를 비교했을 때 7 < 55 이므로, 자리 바꿈 
| 7  | 55 | 78 | 12 | 42 | ; 55와 인접한 78을 비교했을 때 55 < 78 이므로, 자리 안 바꿈 
| 7  | 55 | 78 | 12 | 42 | ; 77과 인접한 12를 비교했을 때 12 < 78 이므로, 자리 바꿈 
| 7  | 55 | 12 | 78 | 42 | ; 78과 인접한 42를 비교했을 때 42 > 78 이므로, 자리 바꿈 

# output: 첫 번째 패스 결과 
| 7  | 55 | 12 | 42 | 78 |
  • 정렬된 원소 = 78
  • 미정렬된 원소 = { 7, 55, 12, 42}
# 두 번째 패스 (첫 번째 원소인 7부터)
| 7  | 55 | 12 | 42 | 78 | ; 7과 인접한 55를 비교했을 때 7 < 55 이므로, 자리 안 바꿈 
| 7  | 55 | 12 | 42 | 78 | ; 55와 인접한 12를 비교했을 때 12 < 55 이므로, 자리 바꿈 
| 7  | 12 | 55 | 42 | 78 | ; 55와 인접한 42를 비교했을 때 42 < 55 이므로, 자리 바꿈 
| 7  | 12 | 42 | 55 | 78 | ; 55와 인접한 78을 비교했을 때 55 < 78 이므로, 자리 안 바꿈 

# output: 두 번째 패스 결과 
| 7  | 12 | 42 | 55 | 78 |
  • 정렬된 원소 = {55, 78}
  • 미정렬 원소 = {7, 12, 42}
# 세 번째 패스 (첫 번째 원소인 7부터)
| 7  | 12 | 42 | 55 | 78 | ; 7과 인접한 12를 비교했을 때 7 < 12 이므로, 자리 안 바꿈 
| 7  | 12 | 42 | 55 | 78 | ; 12와 인접한 42를 비교했을 때 12 < 42 이므로, 자리 안 바꿈 

# output: 세 번째 패스 결과 
| 7  | 12 | 42 | 55 | 78 |
  • 정렬된 원소 = {42, 55, 78}
  • 미정렬 원소 = {7, 12}
# 네 번째 패스 (첫 번째 원소인 7부터)
| 7  | 12 | 42 | 55 | 78 | ; 7과 인접한 12를 비교했을 때 7 < 12 이므로, 자리 안 바꿈 

# output: 네 번재 패스 결과 
| 7  | 12 | 42 | 55 | 78 |
  • 정렬된 원소 = {12, 42, 55, 78}
  • 미정렬 원소 = 7
# 다섯 번째 패스 
미정렬 원소가 한 개 이므로 정렬 끝 

# output 
| 7  | 12 | 42 | 55 | 78 |

Pseudo Code

# === 정의 === # 
def BubbleSort(input:list):
    for step, i in enumerate(range(len(input)-1, 0, -1)): 
        for j in range(0, i): 
            if input[j] > input[j+1]: # 인접한 원소끼리 비교 
                input[j], input[j+1] = input[j+1], input[j] # swap 

        print(f"Step{step+1} results={input}")

# === 실행 === # 
input = [55, 7, 78, 12, 42]

BubbleSort(input)

# === 출력 === # 
Step1 results=[7, 55, 12, 42, 78]
Step2 results=[7, 12, 42, 55, 78]
Step3 results=[7, 12, 42, 55, 78]
Step4 results=[7, 12, 42, 55, 78]

BubbleSort() 의 명령어 개수 = 3n+3(n−1)+3(n−2)+⋯+3=(n−1)×3n+⋯=3n2+⋯3n + 3(n-1) + 3(n-2) + \cdots + 3 = (n-1)\times3n + \cdots=3n^{2}+\cdots


Big-O 표기법으로 표현하면:

O(3n2+⋯ )=O(3n2)=O(n2)O(3n^{2}+\cdots)=O(3n^{2})=O(n^{2})


2. Counting Sort

“항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하여, 선형 시간에 정렬하는 효율적인 알고리즘”

[Process]

  1. 정수(int)나 정수로 표현할 수 있는 자료에 대해서만 적용 가능함 (각 항목의 발생 회수를 기록하기 위해, 정수 항목으로 인덱스되는 카운트들의 리스트를 사용하기 때문)
  2. 카운트들을 위한 충분한 공간을 할당하려면 집합 내의 가장 큰 정수를 알아야 함

※ 시간복잡도 = O(n+k)O(n+k) : nn은 리스트의 개수, kk는 정수의 최대값


EXAMPLE: {0, 4, 1, 3, 1, 2, 4, 1} 을 카운팅 정렬하는 과정

[step1] Data에서 각 항목들의 발생 회수를 세고, 정수 항목들로 직접 인덱스 되는 카운트 리스트 COUNTS에 저장

DATA = [0, 4, 1, 3, 1, 2, 4, 1]  
COUNTS = [0] * 5  # 발생 횟수를 저장하는 리스트 

# ==== 발생 횟수 카운트 === # 
			 | 0 | 1 | 2 | 3 | 4 |  # 숫자 항목 
COUNTS | 1 | 3 | 1 | 1 | 2 |  # 발생 횟수

[step2] 정렬된 집합에서 각 항목의 앞에 위치할 항목의 개수를 반영하기 위해 COUNTS의 원소를 조정

DATA = [0, 4, 1, 3, 1, 2, 4, 1] 
COUNTS = [1, 3, 1, 1, 2]

0 앞에 오는 항목의 개수 0개 
1 앞에 오는 항목의 개수 1개 
2 앞에 오는 항목의 개수 4개 
3 앞에 오는 항목의 개수 5개 
4 앞에 오는 항목의 개수 6개  

# COUNTS 리스트 조정 
COUNTS = [1+0, 3+1, 1+4, 1+5, 2+6]

[step3] DATA 의 마지막 항목부터 데이터 정렬하기

DATA   | 0 | 4 | 1 | 3 | 1 | 2 | 4 | 1 |
COUNTS | 1 | 4 | 5 | 6 | 8 | 

# COUNTS[1]을 1 감소시키고 TEMP에 1을 삽입 
COUNTS | 1 | 3 | 5 | 6 | 8 | 
TEMP   |   |   |   | 1 |   |   |   |   |
  • DATA[-1] 의 원소는 1 이다 ⇒ COUNTS[1] 로 이동
  • COUNTS[1] 의 원소가 4임을 확인 ⇒ 해당 원소를 1 감소 시키고 (-1) TEMP 리스트의 4번째 칸에 1 을 삽입
DATA   | 0 | 4 | 1 | 3 | 1 | 2 | 4 | 1 |
COUNTS | 1 | 3 | 5 | 6 | 8 |

# COUNTS[4]를 감소시키고 TEMP에 4를 삽입 
COUNTS | 1 | 3 | 5 | 6 | 7 | 
TEMP   |   |   |   | 1 |   |   |   | 4 |
  • DATA[-2] 의 원소가 4 이다 ⇒ COUNTS[4]로 이동
  • COUNT[4] 의 원소가 8임을 확인 ⇒ 해당 원소를 1 감소 시키고 TEMP 리스트의 8번째 칸에 4를 삽입
DATA   | 0 | 4 | 1 | 3 | 1 | 2 | 4 | 1 |
COUNTS | 1 | 3 | 5 | 6 | 7 | 

# COUNTS[2]를 감소시키고 TEMP에 2를 삽입 
COUNTS | 1 | 3 | 4 | 6 | 7 | 
TEMP   |   |   |   | 1 | 2 |   |   | 4 |
  • DATA[-3] 의 원소가 2 이다 ⇒ COUNTS[2] 로 이동
  • COUNTS[2] 의 원소가 5임을 확인 ⇒ 해당 원소를 1 감소 시키고 TEMP 리스트의 5번째 칸에 2를 삽입
DATA   | 0 | 4 | 1 | 3 | 1 | 2 | 4 | 1 |
COUNTS | 1 | 3 | 4 | 6 | 7 | 

# COUNTS[1]을 감소시키고 TEMP에 1을 삽입 
COUNTS | 1 | 2 | 4 | 6 | 7 | 
TEMP   |   |   | 1 | 1 | 2 |   |   | 4 |
  • DATA[-4] 의 원소가 1 이다 ⇒ COUNTS[1] 로 이동
  • COUNTS[1] 의 원소가 3임을 확인 ⇒ 해당 원소를 1 감소 시키고 TEMP 리스트의 3번째 칸에 1을 삽입
DATA   | 0 | 4 | 1 | 3 | 1 | 2 | 4 | 1 |
COUNTS | 1 | 2 | 4 | 6 | 7 | 

# COUNTS[3]을 감소시키고 TEMP에 3을 삽입 
COUNTS | 1 | 2 | 4 | 5 | 7 | 
TEMP   |   |   | 1 | 1 | 2 | 3 |   | 4 |
  • DATA[-5] 의 원소가 3 이다 ⇒ COUNTS[3] 로 이동
  • COUNTS[3] 의 원소가 6임을 확인 ⇒ 해당 원소를 1 감소 시키고 TEMP 리스트의 6번째 칸에 3을 삽입
DATA   | 0 | 4 | 1 | 3 | 1 | 2 | 4 | 1 |
COUNTS | 1 | 2 | 4 | 5 | 7 |

# COUNTS[1]을 감소시키고 TEMP에 1을 삽입 
COUNTS | 1 | 1 | 4 | 5 | 7 | 
TEMP   |   | 1 | 1 | 1 | 2 | 3 |   | 4 |
  • DATA[-6] 의 원소가 1 이다 ⇒ COUNTS[1] 로 이동
  • COUNTS[1] 의 원소가 2임을 확인 ⇒ 해당 원소를 1 감소 시키고 TEMP 리스트의 2번째 칸에 1을 삽입
DATA   | 0 | 4 | 1 | 3 | 1 | 2 | 4 | 1 |
COUNTS | 1 | 1 | 4 | 5 | 7 | 

# COUNTS[0]를 감소시키고 TEMP에 0을 삽입 
COUNTS | 1 | 1 | 4 | 5 | 6 | 
TEMP   |   | 1 | 1 | 1 | 2 | 3 | 4 | 4 |
  • DATA[-7] 의 원소가 4 이다 ⇒ COUNTS[4] 로 이동
  • COUNTS[4] 의 원소가 7임을 확인 ⇒ 해당 원소를 1 감소 시키고 TEMP 리스트의 7번째 칸에 4을 삽입
DATA   | 0 | 4 | 1 | 3 | 1 | 2 | 4 | 1 |
COUNTS | 1 | 1 | 4 | 5 | 6 | 

# COUNTS[0]를 감소시키고 TEMP에 0을 삽입 
COUNTS | 0 | 1 | 4 | 5 | 6 | 
TEMP   | 0 | 1 | 1 | 1 | 2 | 3 | 4 | 4 |
  • DATA[-8] 의 원소가 0 이다 ⇒ COUNTS[0] 로 이동
  • COUNTS[0] 의 원소가 1임을 확인 ⇒ 해당 원소를 1 감소 시키고 TEMP 리스트의 1번째 칸에 0을 삽입

TEMP 업데이트 완료하고 정렬 작업을 종료

Pseudo Code

def CountingSort(DATA:list, TEMP:list, k:int): 
    """ DATA : 입력된 데이터 리스트
        TEMP : 정렬해서 저장할 리스트 
        k : 숫자 항목 개수 
    """

    # === Step1. 항목 숫자 발생 횟수 === # 
    COUNTS = [0] * k    # 1회 

    for i in range(0, len(TEMP)): # 2n회 
        COUNTS[DATA[i]] += 1 
    
    print(f"COUNTS= {COUNTS}") # 1회 

    # === Step2. COUNTS의 원소를 조정 === # 
    for i in range(1, len(COUNTS)): # 2(k-1)회 
        COUNTS[i] += COUNTS[i-1]

    print(f"re-COUNTS= {COUNTS}")   # 1회 
    
    # === Step3. DATA 의 마지막 항목부터 데이터 정렬 === # 
    for i in range(len(TEMP)-1, -1, -1):  # 4n 회 
        TEMP[ COUNTS[DATA[i]]-1] = DATA[i]
        COUNTS[DATA[i]] -= 1

        print(f"TEMP = {TEMP}")


DATA = [0, 4, 1, 3, 1, 2, 4, 1]
TEMP = [0]*len(DATA)

CountingSort(DATA, TEMP, len(set(DATA)))


# === output === # 
COUNTS= [1, 3, 1, 1, 2]
re-COUNTS= [1, 4, 5, 6, 8]
TEMP = [0, 0, 0, 1, 0, 0, 0, 0]
TEMP = [0, 0, 0, 1, 0, 0, 0, 4]
TEMP = [0, 0, 0, 1, 2, 0, 0, 4]
TEMP = [0, 0, 1, 1, 2, 0, 0, 4]
TEMP = [0, 0, 1, 1, 2, 3, 0, 4]
TEMP = [0, 1, 1, 1, 2, 3, 0, 4]
TEMP = [0, 1, 1, 1, 2, 3, 4, 4]
TEMP = [0, 1, 1, 1, 2, 3, 4, 4]

CountingSort() 의 명령어 개수 = 1+2n+2(k−1)+1+4n=6n+2k1 + 2n + 2(k-1) + 1 + 4n = 6n+2k


Big-O 표기법으로 표현하면:

O(6n+2k)=O(n+k)O(6n+2k)=O(n+k)

특징

알고리즘 평균 수행시간 최악 수행시간 알고리즘 기법 비고
Bubble sort O(n2)O(n^{2}) O(n2)O(n^{2}) 비교와 교환 코딩이 가장 쉬움
Counting sort O(n+k)O(n+k) O(n+k)O(n+k) 교환 없음 nn 이 비교적 작을 때만 가능

Summary

  • Sort의 정의 - 2개 이상의 자료를 특정 기준에 의해 오름차순/내림차순으로 재배열 하는 것
  • 대표적인 Sort 방식의 종류
  • Bubble / Counting Sort 알고리즘 정리

Reference

[1] https://swexpertacademy.com/main/main.do

위치: 대한민국 서울특별시

댓글

  1. DoranLyong2022년 1월 9일 오후 11:58

    Counting sort 방식이 좀 헷갈린다.
    핵심은
    - 입력된 시퀀스의 각 항목의 발생 빈도를 먼저 센다 (COUNTS 리스트 생성)

    - 각 항목이 차지할 영역중 가장 마지막 칸의 위치를 알기 위해 각 항목별로 앞의 항목들의 개수를 더한다 (COUNTS 리스트 조정)

    - 본격적으로 소팅 시작. DATA의 맨 마지막 인덱스부터 역방향으로 각 항목이 들어갈 위치를 찾는다.
    DATA에서 선택된 숫자가 위치해야할 영역의 맨 마지막 칸을 알기 위해 COUNTS 리스트에서 확인한다.
    위치가 확인되면 TEMP 리스트에 해당 위치로 숫자를 입력한다.
    입력이 끝나면 해당 영역에 자리가 찾다는 의미로 COUNTS 리스트에서 해당 숫자의 발생 수를 -1 해준다.

    답글삭제

댓글 쓰기

이 블로그의 인기 게시물

[DL for CV] Down-Sampling (Encoding)

이미지
  Down-sampling (Encoding)  [DL for CV] Down-Sampling (Encoding) ( source ) Downsampling 은 신호처리(signal processing)에서 사용되는 용어로 sample의 개수를 줄이는 처리 과정을 말한다 . 딥러닝에서는 인코딩(Encoding)과정에서 feature의 개수를 줄이는 처리과정 이라 볼 수 있다. feature 개수를 줄이면 이를 다룰 파라미터도 줄어들기 때문에 차원이 축소되는 효과 를 얻을 수 있다. 이는 곳 overfitting을 방지 하는 효과로 이어진다. 딥러닝 모델 아키텍처에서 사용되는 몇 가지 대표적인 Downsampling 방식을 정리한다. Pooling - 대표값 구하기 커널 영역(kernel scope)에 포함된 data 중에서 대표 값 하나를 샘플링하는 처리 방식 이다. 대표 값을 얻는 방식은 따르는 규칙에 따라 다르다; Max Pooling, Average Pooling, Global Average Pooling, and etc. 보통 Average pooling 보다는 Max pooling을 더 많이 사용한다. Average pooling의 경우 산술평균의 특성 을 가지기 때문에 필연적으로 발생하는 문제 가 있다 . 즉, 신호의 분산이 클 경우 대표 값과 실제 두드러지는 값과의 차이가 커진다 . 반면, Max pooling 연산이 좀더 간단하고 두드러지는 신호를 잘 전달할 수 있기 때문에 더 자주 사용된다. 때문에 논문과 교재에서 별도의 언급이 없이 Pooling layer를 언급한다면 Max pooling 이라 생각하면 된다. (장점) Pooling은 학습 가능한 파라미터 (learnable parameters)가 없기 때문에 kernel size를 키워도 차원의 저주를 피할 수 있는 방법중 하나다. t...
Read more »