배열 정렬하기

06 Nov 2023

python

배열은 자료를 저장하는 자료구조로, 여러 개의 데이터를 순서에 맞게 나열할 수 있습니다. 이때, 배열을 정렬하는 것은 데이터를 특정한 순서대로 재배열하는 작업을 뜻합니다. 정렬된 배열은 데이터를 찾거나 비교하는 데에 효율적이며 많은 알고리즘과 방법을 활용하여 정렬할 수 있습니다.

선택 정렬(Selection Sort)

선택 정렬은 가장 간단하고 직관적인 정렬 알고리즘입니다. 아래는 선택 정렬을 이용하여 배열을 오름차순으로 정렬하는 예제 코드입니다.

def selection_sort(arr):
    # 배열의 길이
    n = len(arr)

    # 배열의 모든 요소를 검사
    for i in range(n-1):
        # 최솟값의 인덱스를 저장할 변수
        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]

# 사용 예시
my_arr = [5, 2, 7, 1, 9]
selection_sort(my_arr)
print(my_arr)  # [1, 2, 5, 7, 9]

선택 정렬은 매번 최솟값을 찾아서 맨 앞으로 이동시키는 방식으로 동작합니다. 시간복잡도는 O(n^2)로, 배열의 크기가 클수록 정렬에 소요되는 시간은 많아집니다.

퀵 정렬(Quick Sort)

퀵 정렬은 분할 정복(Divide and Conquer) 방법을 활용한 정렬 알고리즘입니다. 아래는 퀵 정렬을 이용하여 배열을 오름차순으로 정렬하는 예제 코드입니다.

def quick_sort(arr):
    # 배열의 길이
    n = len(arr)

    # 종료 조건: 배열의 크기가 1보다 작으면 정렬할 필요 없음
    if n <= 1:
        return arr

    # pivot을 설정하고 pivot보다 작은 값, 큰 값들을 분할하여 정렬
    pivot = arr[n // 2]
    less = []
    equal = []
    greater = []

    for x in arr:
        if x < pivot:
            less.append(x)
        elif x == pivot:
            equal.append(x)
        else:
            greater.append(x)

    return quick_sort(less) + equal + quick_sort(greater)

# 사용 예시
my_arr = [5, 2, 7, 1, 9]
sorted_arr = quick_sort(my_arr)
print(sorted_arr)  # [1, 2, 5, 7, 9]

퀵 정렬은 pivot을 기준으로 작은 값과 큰 값으로 분할하여 재귀적으로 정렬하는 방식입니다. 평균적인 시간복잡도는 O(nlogn)이지만 최악의 경우 O(n^2)의 시간복잡도를 가질 수 있습니다.

추가적인 정렬 알고리즘

삽입 정렬 (Insertion Sort)
버블 정렬 (Bubble Sort)
병합 정렬 (Merge Sort)
힙 정렬 (Heap Sort)
기수 정렬 (Radix Sort)
계수 정렬 (Counting Sort)

이외에도 다양한 정렬 알고리즘이 존재합니다. 각 알고리즘의 원리와 구현 방법에 대해 공부하고 실제로 활용해보면 프로그래밍 능력을 향상시킬 수 있습니다.

자세한 설명과 예제 코드는 링크를 참고해주세요.

#sorting #algorithm