정렬

기본 정렬 알고리즘

1. 버블 정렬(Bubble Sort)

• 인접한 원소끼리 비교하여 자리를 교환하는 방식.
• 1회 순회하면 배열의 가장 마지막 원소는 가장 큰 원소가 된다(오름차순 가정)
• 시간 복잡도: 최악, 평균 모두 O(n^2). 여기서 n은 배열의 길이

<전체 과정(오름차순 가정)>
1. 전체 배열에서 인접한 원소끼리 비교하여 순차적으로 자리 교환
2. 전체 배열을 한 번 순회할 때마다 마지막 원소는 가장 큰 원소가 위치하게 된다
3. 가장 큰 원소가 놓인 인덱스 전까지 1, 2번 과정 반복

def bubble_sort(arr):
    n = len(arr)
    for i in range(n): # 0 ~ n-1
        for j in range(n-i-1): # 0 ~ n-i-2
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

    return arr

arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("Sorted array is:", arr)

실행 결과

2. 선택 정렬(Selection Sort)

• 전체 배열을 순회하며 각 위치에 올바른 값을 찾아서 배치하는 원리
• 시간복잡도: O(n^2)
• 안정성: 동일 값의 원소가 있을 때 두 원소의 위치는 무작위로 배치되므로 선택정렬은 안정적인 정렬 방법이 아니다
• 메모리: 추가적인 메모리 공간을 거의 사용하지 않으므로 인플레이스(in-place)정렬 알고리즘으로 분류
• 구현이 단순하며, 추가 공간이 필요하지 않다는 장점이 있지만, 큰 데이터셋에 대해서는 효율적이지 않다.

<전체 과정(오름차순 가정)>
1. 배열 전체에서 최솟값 탐색
2. 스왑(swap): 최솟값을 배열의 현재 위치와 교체
3. 다음 위치로 이동
4. 반복

def selection_sort(arr):
    n=len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[min_idx] > arr[j]:
                min_idx = j
        arr[min_idx], arr[i] = arr[i], arr[min_idx]
    return arr

arr = [64, 34, 25, 12, 22, 11, 90]
selection_sort(arr)
print("Sorted array is:", arr)

3. 퀵 정렬(Quick Sort)

• 평균 시간 복잡도: O(nlogn). 피벗이 균등하게 분할되는 경우
• 최악 시간 복잡도: O(n^2). 피벗이 항상 최솟값이거나 최댓값으로 선택되어 분할이 불균등하게 이루어지는 경우
  -> 피벗을 어떻게 선택하느냐가 알고리즘 효율성에 큰 영향을 미친다. ,
• 안정성: 동일한 값을 가진 요소의 상대적 순서가 변경될 수 있기 때문에 안정적이지 않다
• 장점
  - 평균적으로 매우 빠른 실행 시간(O(nlogn))을 가진다
  • 추가적인 메모리 사용이 거의 없으며 제자리 정렬이 가능하다
  • 대규모 데이터셋에 대해 효율적으로 작동하며, 실제 상황에서 자주 사용된다
• 단점
  - 최악의 경우 시간복잡도 매우 증가
  • 안정 정렬이 아니다

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot] # arr 안에서 pivot보다 작은 값들로 새 리스트를 만든다
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]

    return quick_sort(left) + middle + quick_sort(right)

arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = quick_sort(arr)
print("Sorted array is:", sorted_arr)

파이썬 정렬 기법

1. sort()와 sorted()

• sort는 리스트만 한정, sorted는 모든 형태 정렬 가능

>>> a = [5, 2, 3, 1, 4]
>>> a.sort()
>>> a
[1, 2, 3, 4, 5]

sorted({1: 'D', 2: 'B', 3: 'B', 4: 'E', 5: 'A'})
[1, 2, 3, 4, 5]

.sort()는 값을 반환하지 않고 원본을 수정한다.
반면에, sorted()는 정렬된 값을 반환하고 원본은 수정하지 않는다.

2. 키 함수

student_tuples = [
    ('john', 'A', 15),
    ('jane', 'B', 12),
    ('dave', 'B', 10)
]

# student는 리스트 안의 한 튜플을 의미하는 임의의 변수
sorted(student_tuples, key = lambda student: student[2]) # student[2]순 정렬(나이순)
                                         
# 출력 결과: [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

cf) lambda는 익명함수를 만들 때 쓰는 문법
형태: lambda 매개변수: 반환값

sorted(student_tuples, key=lambda student: student[2]) 
에서 람다를 쓰지 않으면 아래와 같이 변경할 수 있다.

def get_age(student):
    return student[2]

sorted(student_tuples, key=get_age)

참고문헌
https://docs.python.org/ko/3/howto/sorting.html
https://wikidocs.net/233711