[Algorithm] 정렬 - 버블정렬, 카운팅 정렬, 선택 정렬

정렬 (Sort)

• 데이터를 정해진 순서대로 나열
• 대표적인 정렬 방식
  1. 버블 정렬
  2. 카운팅 정렬
  3. 선택 정렬
  4. 퀵 정렬
  5. 삽입 정렬
  6. 병합 정렬

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

위와 같은 배열을 오름차순 정렬한다고 할 때, 정렬별로 어떻게 구현할 수 있을까?

 

버블 정렬 (Bubble Sort)

• 인접한 두 개의 원소를 비교하며 자리를 계속 교환하는 방식
• 첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리까지 이동
• (가장 큰 원소부터 맨 마지막 자리에서 점점 앞으로 채워 넣기)
• 비교와 교환
• O(n^2)

# Bubble sort
def BubbleSort(arr):
    for i in range(len(arr)-1, 0, -1):
        for j in range(0, i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

    return arr

print(BubbleSort(arr))

👉 버블정렬 적용해보기

 

카운팅 정렬 (Counting Sort)

• 항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하여, 선형 시간에 정렬하는 효율적인 알고리즘
• 정수나 정수로 표현할 수 있는 자료에 대해서만 적용 가능
  • 각 항목의 발생 횟수를 기록하기 위해, 정수 항목으로 인덱스 되는 카운트들의 배열을 사용하기 때문
  • 카운트를 위한 충분한 공간을 할당하려면 집합 내의 가장 큰 정수를 알아야 함
  • O(n+k) : n은 리스트 길이, k는 정수의 최대값
• 비교환 방식
• n이 비교적 작을 때만 사용 가능

# Counting sort
def CountingSort(arr):
    k = max(arr)
    cnt = [0] * (k+1)
    result = [0] * len(arr)

    for i in range(len(arr)):
        cnt[arr[i]] += 1

    for j in range(1, len(cnt)):
        cnt[j] += cnt[j-1]

    for l in range(len(arr)-1, -1, -1):
        result[cnt[arr[l]]-1] = arr[l]

    return result

print(CountingSort(arr))

👉 카운팅정렬 적용해보기

 

선택 정렬 (Selection Sort)

• 주어진 자료들 중 가장 작은 값의 원소부터 차례대로 선택하여 위치를 교환하는 방식
• 정렬 과정
  1. 주어진 리스트 중에서 최소값 찾기
  2. 그 값을 리스트의 맨 앞에 위치한 값과 교환
  3. 맨 처음 위치를 제외한 나머지 리스트를 대상으로 위의 과정 반복
• 비교와 교환
• 교환의 횟수가 버블, 삽입 정렬보다 작음
• O(n^2)

# Selection sort
def SelectionSort(arr):
    for i in range(len(arr)-1):
        min_idx = i

        for j in range(i, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j

        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    
    return arr

print(CountingSort(arr))

👉 선택정렬 적용해보기