6/28(수) IT 자료구조(11일차) / 11. 정렬 알고리즘

 

11. 정렬 알고리즘

주어진 데이터를 특정 기준에 따라 순서대로 정렬하는 알고리즘

 

11-1. 정렬 알고리즘의 종류

1) 기본 정렬 알고리즘 (O(n^2) 시간 복잡도):
선택 정렬(Selection Sort):

가장 작은 값을 선택하여 정렬되지 않은 부분의 맨 앞에 위치시키는 방식으로 정렬.
버블 정렬(Bubble Sort):

인접한 두 원소를 비교하여 필요한 경우 위치를 교환하여 정렬.
삽입 정렬(Insertion Sort):

정렬되지 않은 부분의 첫 번째 원소를 이미 정렬된 부분에 적절한 위치에 삽입하여 정렬.

2) 고급 정렬 알고리즘 / 분할 정복 (O(nlogn) 시간 복잡도):
병합 정렬(Merge Sort):

리스트를 반으로 나누고, 나누어진 부분 리스트를 재귀적으로 정렬하여 병합.
퀵 정렬(Quick Sort):

피벗(pivot)을 기준으로 리스트를 분할하고, 각 부분 리스트를 재귀적으로 정렬.
힙 정렬(Heap Sort):

힙 자료구조를 사용하여 리스트를 정렬.
셸 정렬(Shell Sort):

리스트를 일정한 간격으로 나누어 부분 리스트를 정렬하고, 간격을 점차 줄여가며 정렬을 반복.

3) 특수 정렬 (선형 시간 복잡도 O(n)):
계수 정렬(Counting Sort):

정수들의 개수를 세어 정렬하는 방식으로, 입력값의 범위가 제한적일 때 효율적임.
기수 정렬(Radix Sort):

가장 낮은 자리수부터 비교하여 정렬하는 방식으로, 정렬할 값의 특정 자리수를 기준으로 정렬.
버킷 정렬(Bucket Sort):

입력 값을 동일한 크기의 버킷에 할당하고, 각 버킷을 개별적으로 정렬하여 합침.

 

12. 기본 정렬 알고리즘

 

12-1. 선택 정렬 (Selection Sort)

주어진 데이터 중 최대값/최소값을 찾은 후, 해당 데이터를 맨 앞이나 맨 뒤로 보냄. 이후, 같은 과정을 반복.

출처: https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html

 

12-1-1. 구현 

def selection_sort(alist):
  # last가 항상 최대값이 되도록 함 → 이후의 반복에서 범위를 하나씩 줄여준다.

(이유 : 정렬된 상태이기 때문)
  for last in range(len(alist)-1, 0, -1):
    # k <- 가장 큰 원소가 있는 인덱스 -> 인덱싱으로 값을 찾을 수 있다.
    k = find_largest_index(alist, last)
    # 찾은 최댓값을 리스트 맨 뒤로 보내 정렬
    alist[k], alist[last] = alist[last], alist[k]

 

alist: 정렬할 리스트
last: 정렬 범위의 마지막 인덱스.
def find_largest_index(alist, last: int) -> int:
  # 초기값 0번부터 시작
  largest_index = 0
  # 해당 마지막 범위까지
  for i in range(last + 1):
    # 특정 인덱스의 값이 기존(초기 0번 인덱스)인덱스의 값보다 크면 변수를 overwrite
    if alist[i] > alist[largest_index]:
      largest_index = i
  return largest_index

 

12-1-2. 테스트

%%time

import random as r

ss_list = [r.randint(1,1000) for i in range(5000)]
print(ss_list)

selection_sort(ss_list)
print(ss_list)

 

12-2. 버블 정렬 (Bubble Sort)

인접한 두 원소를 비교하고 필요에 따라 위치를 교환하여 리스트를 정렬하는 간단한 정렬 알고리즘

 

12-2-1. 구현 

def bubble_sort(alist):
  for last in range(len(alist), 0, -1):
    for i in range(last-1):
      if alist[i] > alist[i+1]:
        alist[i], alist[i+1] = alist[i+1], alist[i]

 

12-2-2. 테스트

%%time

import random as r

bs_list = [r.randint(1,1000) for i in range(5000)]
print(bs_list)

bubble_sort(bs_list)
print(bs_list)

 

 

참고 웹사이트

시각화 자료를 참고할 수 있는 웹사이트
Visualgo: https://visualgo.net/en

visualising data structures and algorithms through animation - VisuAlgo