알고리즘 - 정렬

버블 정렬: O(n²) - 가장 단순하지만 가장 비효율적

선택 정렬: O(n²) - 항상 같은 수행 시간

삽입 정렬: O(n²) - 거의 정렬된 배열에서는 매우 효율적이다

퀵 정렬: O(n log n) - 평균적으로 가장 빠르다

선택 정렬 (Selection Sort)

제자리 정렬 알고리즘의 하나 : 입력 배열 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법이다.

해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘. 해당 자리를 선택하고 그 자리에 오는 값을 찾는 것

선택 정렬은 첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고,

두 번째 자료를 세 번째 자료부터 마지막 자료까지와 차례대로 비교하여 그 중 가장 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬을 수행한다.

1회전을 수행하고 나면 가장 작은 값의 자료가 맨 앞에 오게 되므로 그 다음 회전에서는 두 번째 자료를 가지고 비교한다. 마찬가지로 3회전에서는 세 번째 자료를 정렬한다. N회전에 따라 N번째에 있는거 정렬함.

시간 복잡도: O(n²)

외부 루프 : 배열의 첫 번째부터 마지막까지 순회하며 반복 (n번)

내부 루프 : 남은 요소 중에서 최소값을 찾음 (최대 n-1번 반복)

연산 횟수 : n(n−1)/2, 따라서 빅오는 O(n²)

Best, Avg, Worst 같다.

특징

구조가 간단해서 구현이 단순해서 메모리 사용이 적다

데이터 양이 많을수록 속도가 급격히 떨어진다

작동 방식

배열에서 가장 작은 원소를 찾아 N번째 위치와 교환

그 다음 작은 원소를 찾아 두 번째 위치와 교환

이 과정을 반복하여 전체 배열을 정렬

앞에서 부터 정렬됌

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

for i in range(len(array)):
    min_index = i # 가장 작은 원소의 인덱스 저장
    
    for j in range(i + 1, len(array)):
    
        if array[min_index] > array[j]:
            min_index = j # 최소값 위치 갱신
    array[i], array[min_index] = array[min_index], array[i] # 현재 위치와 최소값 위치 교환

print(array)
# 결과: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

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

삽입 정렬 (Insertion Sort)

삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

즉, 삽입 정렬은 2번째 요소부터 시작하여 앞 쪽과 비교하여 위치를 지정한다.

삽입 정렬에서는 정렬할 자료가 2개의 부분집합인 S(Sorted)와 U(Unsorted)로 나뉘어져 있다.

정렬된 앞부분의 요소들은 부분집합 S이고, 정렬되지 않은 나머지 요소들은 부분집합 U이다.

부분집합 U에서 요소를 하나씩 꺼내서 이미 정렬된 부분집합 S의 마지막 원소부터 비교하면서 위치를 찾아 삽입한다.

따라서 S의 요소는 1개씩 늘리고, U의 요소는 1개씩 줄인다.

이렇게 U의 요소를 모두 S에 삽입하여 공집합이 되면 삽입 정렬이 끝난다.

사진 출처 : https://ssdragon.tistory.com/112

시간 복잡도

Avg, Worst : O(n²) (이중 for문)

Best : O(n)

특징

적은 데이터일 때 유리

거의 정렬된 상태에서 매우 빠름

실시간으로 정렬해야 할 때 유용

작동 방식

배열의 두 번째 원소부터 시작하여 앞의 원소들과 비교

자신보다 큰 원소를 만나면 위치를 교환

마치 카드를 정렬하는 것처럼, 새로운 카드를 기존의 정렬된 카드들 사이에 끼워넣는 방식이다.

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

for i in range(1, len(array)):

    for j in range(i, 0, -1): # 현재 원소를 이전 원소들과 비교
    
        if array[j] < array[j - 1]: # 한 칸씩 왼쪽으로 이동
            array[j], array[j - 1] = array[j - 1], array[j]
        else: # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
            break # 요런게 느낌이 삽입하다 중간에 쏘옥 들어간다.

print(array)
# 결과: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 오름차순 정렬

버블 정렬 (Bubble Sort)

서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않는다면 자리를 교환하여 정렬하는 알고리즘.

정렬 과정에서 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어짐

시간 복잡도 : O(n²)

외부 루프 : n-1번 반복

내부 루프 : 각 패스마다 n-i-1번 비교

연산 횟수 : n(n-1)/2, 따라서 빅오는 O(n²)

특징

구현이 매우 간단하다. 소스 코드가 직관적

시간복잡도가 Best, Avg, Worst 모두O(n²) 모든 정렬 알고리즘 중에서 가장 비효율적이다.

정렬하면서 가장 큰 값이 배열 끝으로 "버블"처럼 떠오른다!

작동 방식

첫 번째 원소와 두 번째 원소 비교, 두 번째 원소와 세 번째 원소 비교. 이런식으로 (마지막-1)번째 원소와 마지막 원소 비교

각 패스가 끝나면 가장 큰 원소가 맨 뒤로 이동하게 됨

2회전 끝나면 뒤에서 2번째 원소까지 정렬에서 제외됌.

이 과정을 배열이 정렬될 때까지 반복

def bubble_sort(arr):
    n = len(arr)
    
    for i in range(n):
        for j in range(0, n-i-1):# 마지막 i개는 이미 정렬됨
        
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j] # 크로스
    return arr

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
print(bubble_sort(array))

# 결과: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

퀵 정렬 (Quick Sort)

특정 피벗을 기준으로 배열을 두 부분으로 나누고, 각각을 재귀적으로 정렬하는 알고리즘 (비균등하게 분할)

시간 복잡도

평균 : O(n log n) (피벗을 기준으로 매번 절반으로 나누므로)

최악 : O(n²) (불균형하게 분할될 경우)

특징

분할 정복을 사용하여 빠르게 정렬

비균등하게 분할되면 비효율적

알고리즘

배열의 중간 값을 피벗(기준)으로 선택

피벗보다 작은 값, 같은 값, 큰 값으로 분할

각 부분을 재귀적으로 정렬

분할된 부분들을 다시 합쳐서 전체 배열을 정렬

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    
    return quicksort(left) + middle + quicksort(right)

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
print(quicksort(array))
# 결과: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

개수 정렬

특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘입니다. 계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능합니다.

데이터의 개수가 N, 데이터(양수) 중 최댓값이 K일 때 최악의 경우에도 수행 시간 O(N + K)를 보장한다.

# 모든 원소의 값이 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 # 각 데이터에 해당하는 인덱스의 값 증가

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