문자열을 입력하면 알파벳순으로 정렬하여 출력하는 알고리즘

문자열을 알파벳순으로 정렬하는 알고리즘

알파벳순으로 문자열을 정렬하는 알고리즘은 많은 프로그래밍 문제에서 필요한 기능 중 하나입니다. 이번 포스팅에서는 문자열을 입력하면 알파벳순으로 정렬하여 출력하는 알고리즘에 대해 다루어 보겠습니다.

예시

입력: "banana"

출력: "aaabnn"

알고리즘 설명

이 알고리즘은 대표적인 정렬 알고리즘 중 하나인 "버블 정렬(Bubble Sort)"을 이용하여 구현할 수 있습니다. 버블 정렬은 인접한 두 값을 비교하여 필요에 따라 위치를 바꿔가며 정렬하는 방식입니다.

1. 입력된 문자열을 배열로 변환합니다.
2. 배열을 반복하여 인접한 두 원소를 비교합니다.
3. 비교한 결과 더 작은 원소가 앞에 오도록 위치를 교환합니다.
4. 이 과정을 배열의 크기의 제곱 만큼 반복합니다.
5. 정렬이 완료된 배열을 문자열로 변환하여 출력합니다.

def alphabet_sort(string):
    arr = list(string)
    length = len(arr)

    for i in range(length):
        for j in range(length - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

    return "".join(arr)

시간 복잡도

이 알고리즘의 시간 복잡도는 O(n^2)입니다. 문자열의 길이를 n이라고 할 때, 반복문의 중첩으로 인해 최악의 경우 문자열 길이의 제곱에 비례하는 시간이 소요됩니다.

마무리

이번 포스팅에서는 문자열을 알파벳순으로 정렬하는 알고리즘에 대해 알아보았습니다. 이 알고리즘은 프로그래밍에서 문자열 정렬 기능을 구현하는 데 유용하게 사용될 수 있습니다. 이러한 기본적인 알고리즘을 숙지하고 활용하는 것은 프로그래밍 능력 향상에 도움이 될 것입니다.