[알고리즘] 선택, 버블, 삽입, 계수 정렬

💡 정렬 알고리즘의 종류와 특징

1. 선택 정렬(Selection Sort)

맨 앞 인덱스부터 기준이 된다. 기준보다 뒤에 있는 값들을 기준과 비교하면서 기준보다 작을 경우 기준과 해당 값을 swap해준다. swap 후에는 기준이 그 다음 인덱스로 바뀐다.

a=[4,7,1,3,5,2]

for i in range(len(a)-1):
    for j in range(i+1,len(a)):
        if a[i]>a[j]:
            a[i],a[j]=a[j],a[i] # swap

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

• 장점
  • 구현이 간단하고, 정밀 비교 가능하다.
  • 교환 횟수가 적어 내림차순 데이터 → 오름차순 데이터로 바꿀 때 효율이 좋다.
• 단점
  • 시간이 오래 걸린다. (O(N^2)의 시간 복잡도를 가짐)
  • 정렬된 상태에서 데이터가 추가되면 효율이 좋지 않다.

2. 버블 정렬(Bubble Sort)

버블 정렬은 첫번째 원소부터 인접한 원소와 비교하며 자리를 바꾸면서 맨 끝부터 정렬하는 방식이다.

a = [8, 3, 12, 10, 1]

for i in range(len(a)-1,0,-1):  # 4 3 2 1
    for j in range (0,i): # i가 4일때 0 1 2 3
        if a[j]>a[j+1]:
            a[j],a[j+1]=a[j+1],a[j]

• 장점
  • 구현이 간단하고, 정밀한 비교가 가능하다.
• 단점
  • 데이터를 하나씩 비교하기 때문에 배열의 길이가 길어지면 성능이 저하된다.
  • 최선의 경우 O(N)의 시간 복잡도를 가지지만 최악의 경우 O(N^2)의 시간 복잡도를 가진다.

3. 삽입 정렬(Insertion Sort)

새로운 배열에 값을 하나씩 삽입하여 마지막부터 직전의 값과 비교하여 정렬하는 알고리즘이다. 버블정렬의 비교 횟수를 줄이기 위해 고안된 정렬이다. 비교 대상이 정렬되어 있을 경우 비교를 하지 않아도 된다.

a=[4,7,1,3,5,2]
result=[]
for i in range(len(a)):
    result.append(a[i]) # 삽입
    for j in range(i,0,-1): # 뒤 -> 앞
        if result[j-1]>result[j]: # 현재 vs 직전값 비교
            result[j],result[j-1]=result[j-1],result[j]
        else:
            break

• 장점
  • 비교 대상이 정렬되어있을 경우 비교를 중단할 수 있다.
• 단점
  • 최선의 경우 O(N)의 시간 복잡도를 가지지만 최악의 경우 O(N^2)의 시간 복잡도를 가진다.
  • 입력으로 들어오는 배열이 역순으로 정렬된 경우 성능이 안 좋다.
  • 데이터의 상태와 크기에 따라 성능의 편차가 큰 정렬 방법이다.

4. 계수 정렬(Counting sort)

계수 정렬은 요소들을 비교하지 않고 요소들의 개수를 세어서 정렬하는 방식이다. 이 때문에 계수 정렬을 셈 정렬이라고도 한다.

n=int(input())
a=list(map(int,input().split())) # 1~100사이의 숫자들을 받음

bucket=[0]*101
# dat 등록
for i in range(n):
    bucket[a[i]]+=1

# 누적합 구하기
for i in range(1,len(bucket)):
    bucket[i]+=bucket[i-1]
    # bucket[i]=bucket[i]+bucket[i-1]

# 값넣기
result=[0]*101
for i in range(n):
    index=a[i]
    result[bucket[index]-1]=a[i]
    bucket[index]-=1

for i in range(n):
    print(result[i],end=' ')

• 장점
  • 비교하지 않고 정렬할 수 있어서 O(N)의 효율적인 시간 복잡도를 가지게 된다.
  • 중복된 값이 많이 분포된 배열을 정렬할 때 효과적이다.
• 단점
  • 숫자 개수를 저장해야 될 별도의 공간, 또 결과를 저장할 별도의 공간 등 추가적인 메모리가 필요하다.
  • 카운트를 위한 충분한 공간을 할당하기 위해서는 집합 내의 가장 큰 정수를 알아야 한다.
  • 양의 정수에 대해서만 적용이 가능하다는 단점이 있다.