Algorithm - 정렬

정렬

 

• 정렬의 경우 모든 경우에 최적인 알고리즘은 없다
• 정렬 알고리즘 평가 기준
  • 비교 횟수의 많고 적음
  • 이동 횟수의 많고 적음

 

 

정렬 알고리즘의 종류

• 기본 정렬 O(n^2)
  • 선택 정렬
  • 버블 정렬
  • 삽입 정렬
• 고급 정렬 O(nlogn)
  • 병합 정렬
  • 퀵 정렬
  • 힙 정렬
  • 셀 정렬
• 특수 정렬 O(n)
  • 계수 정렬
  • 기수 정렬
  • 버킷 정렬

 

선택 정렬 Selection Sort

 

 

• 초기에는 왼쪽 리스트는 비어있고, 정렬한 숫자들은 모두 오른쪽 리스트에 존재
• 오른쪽 리스트에서 가장 작은 숫자를 선택해서 왼쪽 리스트로 이동하는 작업을 되풀이정렬된 왼쪽 리스트와 정렬 안된 오른쪽 리스트로 가정

 

def selection_sort(arr):
    n = len(arr)
    for i in range(n-1):
        min_idx = i  # 최솟값의 인덱스를 저장하는 변수
        
        # i번째 이후의 요소들 중에서 최솟값을 찾음
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        
        # i번째 요소와 최솟값을 교환
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    
    return arr

# 정렬되지 않은 리스트
unsorted_list = [64, 25, 10, 22, 11]
print("정렬 전:", unsorted_list)

# 선택 정렬 실행
sorted_list = selection_sort(unsorted_list)
print("정렬 후:", sorted_list)

기존 공간외의 추가로 공간을 사용해서 정렬을 하기 때문에 이 경우에는 외부 정렬에 속한다

 

선택 정렬을 내부 정렬을 하는 방법 (제자리 정렬) : 입력 배열 외에 추가 배열을 고려하지 않는 경우

# 수도코드
단위 순환
	최대 원소를 찾는다
        최대 원소와 맨 오른쪽 원소를 자리 바꿈
        맨 오른쪽 자리를 관심 대상에서 제외
    
원소가 1개 남을 때 까지 반복

def selection_sort(arr):
    n = len(arr) # 배열 전체 길이
    for i in range(n-1, 0, -1): # n-1부터 1까지 역순으로 반복 = 맨 오른쪽 인덱스부터 관심 대상 좁혀가기
        max_idx = 0  # 최대 원소의 인덱스를 저장하는 변수

        # 최대 원소를 찾음 
        for j in range(1, i+1): # j를 1부터 i까지 반복 
            if arr[j] > arr[max_idx]: 
            # 각 원소 arr[j]를 현재 최대 원소 arr[max_idx]와 비교
            # 만약 arr[j]가 더 크면 max_idx를 j로 업데이트
                max_idx = j # max_idx는 현재 관심대상 범위안 최대 원소의 인덱스가 됨 

        # 최대 원소와 맨 오른쪽 원소를 자리 바꿈
        arr[max_idx], arr[i] = arr[i], arr[max_idx]

    return arr

# 정렬되지 않은 리스트
unsorted_list = [64, 25, 10, 22, 11]
print("정렬 전:", unsorted_list)

# 선택 정렬 실행
sorted_list = selection_sort(unsorted_list)
print("정렬 후:", sorted_list)

 

버블 정렬 Bubble Sort

• 인접한 두 요소를 비교하여 필요한 경우 위치를 교환하는 알고리즘입니다.
• 반복적으로 인접한 요소들을 비교하여 정렬을 수행하고 1회의 반복이 끝나면 가장 큰 요소가 배열의 마지막으로 이동하는 과정이며 이 과정을 배열이 다 정렬될 때까지 반복합니다.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        swapped = False  # 교환이 한 번도 일어나지 않았는지 체크
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:  # 다음 요소와 비교하여 정렬 순서가 뒤바뀌었다면
                arr[j], arr[j + 1] = arr[j + 1], arr[j]  # 요소의 위치를 교환
                swapped = True  # 교환이 일어났음을 체크
        if not swapped:
            break  # 더 이상 교환이 일어나지 않았으면 정렬 완료
    return arr

 

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]  # 현재 요소를 선택하여 삽입할 위치를 찾음
        j = i - 1  # key를 삽입할 위치를 탐색하기 위해 이전 위치로 이동
        
        while j >= 0 and arr[j] > key:  # key보다 큰 값을 가진 요소를 한 칸씩 뒤로 이동
            arr[j + 1] = arr[j]
            j -= 1
        
        arr[j + 1] = key  # key를 삽입할 위치에 삽입
    
    return arr

1. 주어진 배열 arr의 길이를 n이라고 한다.
2. i를 1부터 n-1까지 반복한다.
    - key = arr[i]
    - j = i-1
    - j가 0보다 크거나 같고 arr[j]가 key보다 큰 동안 반복한다.
        - arr[j+1] = arr[j]
        - j = j-1
    - arr[j+1] = key
3. 정렬된 배열 arr을 반환한다.