1. 버블 정렬 (Bubble Sort)

버블 정렬은 인접한 두 요소를 비교하여 순서를 바꾸는 방식으로 리스트를 정렬하는 알고리즘입니다. 가장 큰 요소가 반복적으로 리스트의 끝으로 이동하는 모습이 거품이 올라가는 것과 유사하여 ‘버블 정렬’이라는 이름이 붙었습니다.

아래는 파이썬으로 구현한 버블 정렬의 예시입니다:

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

이 알고리즘은 간단하고 구현이 쉬우나, 시간 복잡도가 O(n²)으로 효율적이지 않습니다. 그러나 데이터가 거의 정렬되어 있는 경우에는 효율적일 수 있습니다.

2. 선택 정렬 (Selection Sort)

선택 정렬은 리스트에서 가장 작은 요소를 찾아 맨 앞의 요소와 교환하는 과정을 반복하여 정렬하는 알고리즘입니다. 이 과정을 리스트의 끝까지 반복하면 전체 리스트가 정렬됩니다.

아래는 파이썬으로 구현한 선택 정렬의 예시입니다:

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

선택 정렬은 구현이 간단하지만, 시간 복잡도가 O(n²)으로 대규모 데이터에는 비효율적입니다.

3. 삽입 정렬 (Insertion Sort)

삽입 정렬은 리스트를 순차적으로 탐색하면서, 각 요소를 이미 정렬된 부분에 적절한 위치에 삽입하여 정렬하는 알고리즘입니다. 마치 카드 게임에서 손에 든 카드를 정렬하는 방식과 유사합니다.

아래는 파이썬으로 구현한 삽입 정렬의 예시입니다:

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
  

삽입 정렬은 대부분의 요소가 이미 정렬되어 있는 경우에 효율적이며, 시간 복잡도는 평균적으로 O(n²)입니다.

4. 파이썬 내장 정렬 함수: sorted()와 list.sort()

파이썬은 리스트를 정렬하기 위한 두 가지 주요 내장 기능을 제공합니다: sorted() 함수와 list.sort() 메서드입니다. 이 두 가지는 비슷해 보이지만, 사용 방법과 반환 결과에 있어 중요한 차이점이 있습니다.

4.1 sorted() 함수

sorted() 함수는 어떤 반복 가능한(iterable) 객체도 받아서 정렬된 새로운 리스트를 반환합니다. 원래의 데이터는 변경되지 않습니다.

numbers = [3, 1, 4, 1, 5, 9]
sorted_numbers = sorted(numbers)
print(sorted_numbers)  # 출력: [1, 1, 3, 4, 5, 9]
print(numbers)         # 원래 리스트는 변경되지 않음
  

4.2 list.sort() 메서드

list.sort() 메서드는 리스트 객체의 메서드로, 리스트 자체를 정렬합니다. 이 메서드는 리스트를 직접 변경하며, 반환값은 None입니다.

numbers = [3, 1, 4, 1, 5, 9]
numbers.sort()
print(numbers)  # 출력: [1, 1, 3, 4, 5, 9]
  

4.3 주요 차이점 요약

4.4 정렬 기준 지정: key와 reverse 매개변수

두 함수 모두 key와 reverse 매개변수를 사용하여 정렬 기준을 지정할 수 있습니다.

• key: 정렬 기준이 되는 함수를 지정합니다.
• reverse: True로 설정하면 내림차순으로 정렬합니다.

words = ['banana', 'apple', 'cherry']
# 길이를 기준으로 오름차순 정렬
sorted_words = sorted(words, key=len)
print(sorted_words)  # 출력: ['apple', 'banana', 'cherry']

# 알파벳 역순으로 정렬
words.sort(reverse=True)
print(words)  # 출력: ['cherry', 'banana', 'apple']
  

4.5 정렬 알고리즘: Timsort

파이썬의 정렬 함수는 Timsort 알고리즘을 사용합니다. Timsort는 합병 정렬과 삽입 정렬을 결합한 하이브리드 알고리즘으로, 실제 데이터에서 뛰어난 성능을 보입니다.