[Computer Science] Iterative Sorting(반복 정렬) - Selection Sort(선택정렬), Insertion Sort(삽입정렬), Bubble Sort(버블정렬), Count Sort (계수 정렬) / 시간 측정 비교

모든 알고리즘의 기본 원리는 숫자와 조건을 활용하면서 발전시킨다고 생각하면, 어려운 알고리즘에 대해 배우는 관점이 달라질 수 있다.

Selection Sort(선택정렬)

선택정렬은 가장 작은 노드(최소값)를 선택하고 왼쪽부터 정렬을 하기 위해 알맞은 위치와 교환하는 작업을 반복하는 것.

• 선택정렬 정리 : 최소노드 선택 -> 왼쪽부터 비교 -> 교환
• 단점 :
  버블정렬과 달리 서로 이웃하지 않은 노드를 교환하므로, 안정적이지 않다.

  

'''선택 정렬 소스 코드 ''' 
array = [7, 5, 9, 0, 3, 1, 6, 2, 8, 4]

for i in range(len(array)):
    min_index = i #가장 작은 원소의 인덱스로 지정
    for j in range(i+1, len(array)): #j는 가장작은 원소의 인덱스+1 부터 주어진 리스트의 범위까지 선형탐색 시작
        if array[min_index] > array[j]: # j의 인덱스가 가장 작은 원소의 인덱스보다 작다면
            min_index = j # 최소 원소의 인덱스를 j값으로 바꿔라
    array[i], array[min_index] = array[min_index], array[i] # 인덱스 스와핑

print(array)

선택 정렬의 시간 복잡도

O(n^2)

선택 정렬은 n번 만큼 가장 작은 수를 찾아서 맨 앞으로 보냄.
구현방식에 따라서 사소한 오차는 가능하지만, 전체 연산 횟수는 다음과 같다.
[n + (n-1) + (n-2) + ..... + 2] 이는 (n^2+n-2)/2로 표현 가능 --> 빅오 표기법 O(n^2)

• 선택정렬이 노드값을 비교하는 횟수도 O(n^2)번이다.
  • 외부루프 : (n-1)
  • 내부루프(최소값찾기) : (n-1),(n-2),...,2,1
  • 교환횟수 : 3(n-1)

Insertion Sort(삽입정렬)

처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입.

선택정렬에 비해 구현 난이도가 높은 편이지만, 일반적으로 더 효율적으로 동작. 

삽입정렬은 소량의 데이터를 정렬하기위한 효율적인 알고리즘이다.

https://runestone.academy/runestone/books/published/pythonds/SortSearch/TheInsertionSort.html

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

'''삽입 정렬 소스코드'''            
for i in range(1, len(array)): # 인덱스 1(두번째임)부터 왼쪽으로 이동하는 범위를 지정함
    for j in range(i, 0, -1): #인덱스 j는 i부터 시작하여 인덱스0번부터 -1스텝(왼쪽으로 한칸)으로 이동한다
        if array[j] < array[j-1]:  #인덱스 j가 j의 왼쪽에있는 수보다 작으면
            array[j], array[j-1] = array[j-1], array[j] #작은 j를 왼쪽으로 스와핑
        else: #인덱스j가 왼쪽의 수보다 크면 그위치에서 멈춤
            break
print(array)

삽입 정렬의 시간 복잡도

Worst / Avg (n^2) 
Best O(n)

평균적으로 선택 정렬과 마찬가지로 반복문이 두번 중첩되어 사용되므로. O(n^2)이며.

오름차순으로 정렬해야되는 가정 하에 최악의 경우는 배열이 내림차순(반대로 정렬된 경우)으로 정렬된 경우이다.

내림차순을 오림차순으로 하려면 높은 숫자 항목을 오른쪽으로 이동시키기 위해 최대 반복 횟수를 수행해야하므로

 

최상의 경우(이미 정렬되어 있는 상태) O(n)의 Best 시간 복잡도를 가진다.

이미 정렬되어 있는 상태에서 다시 삽입 정렬을 수행하면 상수시간이 되므로.

Bubble Sort(버블정렬)

서로 이웃한 두 원소의 크기를 비교한 결과에 따라 교환을 반복하는 알고리즘 (단순 교환 정렬이라고도 함)

가장 간단하지만 비효율적

버블 정렬의 시간 복잡도

O(n^2)

• 목록이 이미 정렬되어 있어도 목록의 모든 항목을 검사해야 한다.
• 배열 전체를 쭉 살펴보는 과정을 무조건 n번하기 때문에, (내부 루프 및 외부 루프)가 O(n^2) 시간 복잡도가 걸린다.
• 노드를 비교하는 횟수는 (n-1)+(n-2)+(n-3)+ ... +1 = n(n-1)/2

''' 버블정렬 소스코드 '''

def bubble_sort(li):
    length = len(li) -1
    # 외부 반복문(아래 그림에서 전체 리스트에 대해 정렬이 완료되었는지 검사하고 패스해줌)
    for i in range(length): 
        # 내부 반복문(아래 그림에서 하나의 리스트의 개별 값을 비교하고 교체시킨다)
        for j in range(length - i):
        	# 현재 인덱스의 값과 다음 인덱스의 값 비교
            if li[j]>li[j+1]:
            	# 비교한 것에 따라 정렬을 위한 인덱스 교환 작업
                li[j], li[j+1] = li[j+1], li[j]
    return li

if __name__ == "__main__":
    li = [54, 26, 93, 17, 77, 31]

    bubble_sort(li)
    print(li)   #li의 값이 정렬되어야합니다.

'''
[17, 26, 31, 54, 77, 93]
'''

 

 

 

 

계수 정렬 (count)

특정한 조건이 부합할 때만 사용, 매우 빠르게 동작하는 정렬 알고리즘

계수 정렬은 데이터의 크기 범위가 제한되어이썽

1. 가장 작은 데이터 부터 가장 큰 데이터까지의 범위가 모두 담길 수 있도록 리스트를 생성.

데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가 시킨다. 

결과를 확인할때는 리스트의 첫번째 데이터 부터 하나씩 그 값만큼 반복하여 인덱스를 출력

'''계수 정렬 소스코드'''
#모든 원소의 값이 0보다 크거나 같다고 가정
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]

#모든 범위를 포함하는 리스트를 선언(모든 값은 0으로 초기화)
count = [0] * (max(array)+1)

for i in range(len(array)):
    count[array[i]] += 1 #array의 모든 범위의 인자 하나씩을 count +1해줌 (각 인자가 몇번 등장했는지 count)

for i in range(len(count)): # count 리스트에 기록된 정렬 정보 확인
    for j in range(count[i]): #인덱스 i인자에 해당하는 것을 j라고 함
        print(i, end = ' ') # 띄어쓰기를 구분으로 등장한 횟수 만큼 인덱스를 출력

계수정렬의 시간-공간복잡도

각 인자들을 호출하여 계산하는 반복문과 중첩 반복문이 혼합되어 있기 대문에 O(n+k)

계수정렬은 때에 따라서 심각한 비효율성을 초래함. - 데이터가 0과 999,999로 단 2개만 존재하는경우

계수정렬은 동일한 값을 가지는 데이터가 여러개 등장할 때 효과적으로 사용 할 수 있다.  - 성적의 경우 100점을 맞은 학생이 여러명일 수 있기 때문에 계수 정렬이 효과적

 

https://www.youtube.com/watch?v=KGyK-pNvWos&t=339s

 

수행 시간 측정 및 비교

from random import randint
import time
#배열에 10,000개의 정수를 삽입
array = []

for _ in range(10000):
    #1부터 100사이의 랜덤한 정수
    array.append(randint(1,100))

#선택 정렬 프로그램 성능 측정
start_time = time.time()

#선택 정렬 프로그램 소스코드
for i in range(len(array)):
    min_index = i #가장 작은 원소의 인덱스로 지정
    for j in range(i+1, len(array)): #j는 가장작은 원소의 인덱스+1 부터 주어진 리스트의 범위까지 선형탐색 시작
        if array[min_index] > array[j]: # j의 인덱스가 가장 작은 원소의 인덱스보다 작다면
            min_index = j # 최소 원소의 인덱스를 j값으로 바꿔라
    array[i], array[min_index] = array[min_index], array[i] # 스와핑 인덱스

#측정 종료
end_time = time.time()

#수행 시간 출력
print("선택 정렬 성는 측정: ", end_time - start_time)


# 배열을 다시 무작위 데이터로 초기화
array = []
for _ in range(10000):
    #1부터 100사이의 랜덤한 정수
    array.append(randint(1,100))

#기본 정렬 라이브러리 성능 측정
start_time = time.time()

#기본정렬 라이브러리 (파이썬 내장 메소드)사용 #내장 메소드는 하이브리드 형식으로 worst여도 O(nlogn)임.
array.sort()

#측정 종료
end_time = time.time()

#수행 시간 출력
print("내장 메소드 기본정렬 성능 측정: ", end_time-start_time)

 

ref. 비주얼 알고리즘 : https://visualgo.net/ko/sorting

VisuAlgo - Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix)

ref. https://youtu.be/KGyK-pNvWos