파이썬에서는 다양한 정렬 메서드를 제공하여 리스트를 쉽게 정렬할 수 있습니다. 하지만 때로는 반복문을 사용하여 리스트를 정렬하는 것이 필요할 수도 있습니다. 이번 포스팅에서는 반복문을 사용하여 리스트를 정렬하는 방법에 대해 알아보겠습니다.
1. 버블 정렬(Bubble Sort)
버블 정렬은 인접한 두 원소를 반복적으로 비교하며 위치를 교환하는 정렬 알고리즘입니다. 이 알고리즘을 사용하여 리스트를 정렬하는 코드는 다음과 같습니다.
def bubble_sort(lst):
n = len(lst)
for i in range(n-1):
for j in range(n-i-1):
if lst[j] > lst[j+1]:
lst[j], lst[j+1] = lst[j+1], lst[j]
위 코드에서는 먼저 리스트의 길이를 구하고, 바깥쪽 반복문에서는 리스트의 길이 - 1 만큼 반복하며 안쪽 반복문에서는 인접한 원소를 비교하여 위치를 교환합니다. 이렇게 반복하면서 가장 큰 원소는 맨 뒤로 이동하게 되므로, 매 반복마다 리스트의 마지막부터 정렬된 원소들이 하나씩 쌓이게 됩니다.
2. 선택 정렬(Selection Sort)
선택 정렬은 주어진 리스트 중에서 최소값을 선택하여 앞으로 이동시키는 정렬 알고리즘입니다. 이 알고리즘을 사용하여 리스트를 정렬하는 코드는 다음과 같습니다.
def selection_sort(lst):
n = len(lst)
for i in range(n-1):
min_idx = i
for j in range(i+1, n):
if lst[j] < lst[min_idx]:
min_idx = j
lst[i], lst[min_idx] = lst[min_idx], lst[i]
위 코드에서는 외부 반복문에서는 정렬된 부분리스트의 길이를 늘리며, 내부 반복문에서는 가장 작은 원소를 찾아 앞으로 이동시킵니다. 이렇게 하면 매 반복마다 가장 작은 원소가 정렬된 부분리스트 제일 뒤에 쌓이게 됩니다.
3. 삽입 정렬(Insertion Sort)
삽입 정렬은 리스트를 정렬된 부분과 정렬되지 않은 부분으로 나누고, 정렬되지 않은 부분의 첫 번째 원소를 정렬된 부분에 적절한 위치에 삽입하는 정렬 알고리즘입니다. 이 알고리즘을 사용하여 리스트를 정렬하는 코드는 다음과 같습니다.
def insertion_sort(lst):
n = len(lst)
for i in range(1, n):
key = lst[i]
j = i-1
while j >= 0 and lst[j] > key:
lst[j+1] = lst[j]
j -= 1
lst[j+1] = key
위 코드에서는 외부 반복문에서는 정렬되지 않은 부분의 첫 번째 원소를 선택하고, 내부 반복문에서는 선택한 원소를 정렬된 부분에 적절한 위치에 삽입합니다. 이렇게 하면 매 반복마다 한 원소씩 정렬된 부분이 늘어나게 됩니다.
마무리
위에서 소개한 세 가지 정렬 알고리즘은 모두 반복문을 사용하여 리스트를 정렬하는 방법입니다. 각각의 알고리즘은 서로 다른 원리를 가지고 있지만, 모두 원리를 이해하고 구현하는 것은 어렵지 않습니다. 리스트를 정렬해야 할 때, 파이썬의 내장 정렬 메서드 외에도 자신만의 정렬 알고리즘을 구현해보면 좋습니다.