[알고리즘 설명][Python] 정렬(sort)

이 게시글은 CS(컴퓨터공학) 프로그래밍 기초를 어느 정도 알고 있다고 가정하고 아주 간단하게 설명하는 게시글입니다.

혹시나 모르는 부분이 있으면 댓글로 질문해주세요.

 

한 줄 요약 : 정렬은 오름차순 정렬, 내림차순 정렬로 이루어져 있으며 문자열 사전순 정렬은 index 0을 1순위 정렬 기준으로 하고 그 뒤 index 1, index 2 순으로 정렬을 하는 방식입니다. 추가로 Python에서는 L.sort() 혹은 L2 = sorted(L1) 형식으로 정렬 함수를 사용할 수 있으며 이 때 오름차순이면 sort(), 내림차순이면 sort(reverse=True) 형식으로 해주시고 우선순위를 정해서 정렬하고 싶다면 key=lambda 형식을 사용해주세요.

그냥 정렬 알고리즘은 데이터들을 큰 순서대로 혹은 작은 순서대로 일렬로 쫙 재배치한다고 생각하시면 됩니다.

 

정렬은 데이터를 정해진 순서대로 나열하는 알고리즘입니다.

정렬은 오름차순 정렬(ASC sorting)과 내림차순 정렬(DESC sorting)이 있습니다.

숫자가 [2, 4, 1, 5, 3]이 있다면 오름차순 정렬이면 [1, 2, 3, 4, 5], 내림차순 정렬이면 [5, 4, 3, 2, 1]이 됩니다.

이것을 Python으로 구현해 봅니다.

import sys

input = sys.stdin.readline

ASC:list = [2, 4, 1, 5, 3]
DESC:list = [2, 4, 1, 5, 3]

ASC.sort() # 오름차순 정렬
DESC.sort(reverse=True) # 내림차순 정렬

print(ASC) # 결과 : [1, 2, 3, 4, 5]
print(DESC) # 결과 : [5, 4, 3, 2, 1]

 

그리고 정렬을 할 때 key=lambda를 활용하여 튜플 혹은 리스트 형식으로 이루어진 원소들도 정렬할 수 있습니다.

예시를 한 번 확인합니다.

import sys

input = sys.stdin.readline

L:list = [
    (1, 2),
    (3, 4),
    (1, 1),
    (2, 5),
    (2, 2),
    (3, 3)
]

L.sort(key=lambda x : (x[0], x[1]))
print(L)

결과 : [(1, 1), (1, 2), (2, 2), (2, 5), (3, 3), (3, 4)]

이 코드의 의미는 해당 리스트의 원소 x(여기서는 튜플)에서 x[0]을 1번째로 정렬하고 그 다음 x[0]이 같은 경우 x[1]을 2번째로 정렬한다는 의미입니다.

x[0] 기준으로 보면 1, 2, 3이 존재하고, 그 다음 x[0] = 1인 원소들이 (1, 2), (1, 1)이 존재하고 그 다음 x[1] 기준으로 정렬하면 (1, 1), (1, 2)가 됩니다.

같은 원리로 정렬를 진행하면 위와 같은 결과가 나옵니다.

이건 MySQL이나 OracleSQL을 공부해본 분들이라면 이 파트를 금방 이해할 수 있을 것입니다.

 

문자열 사전순으로 정렬하는 것도 크게 다르지가 않는데요.

예를 들어 이런 소스 코드가 있다고 가정합니다.

import sys

input = sys.stdin.readline

L:list = ["a", "ab", "b", "bbb", "abc"]

L.sort()

print(L)

결과 : ['a', 'ab', 'abc', 'b', 'bbb']

 

각 문자열들을 C언어의 char 2차원 배열로 표현하면 다음과 같습니다.

#include <stdio.h>

int main() {
    // 행(Row) 개수 : 5개, 열(Column) 개수 : 4개 (최장 길이 3 + '\0')
    char L[5][4] = {
        {'a', '\0', '\0', '\0'}, // "a"
        {'a', 'b',  '\0', '\0'}, // "ab"
        {'b', '\0', '\0', '\0'}, // "b"
        {'b', 'b',  'b',  '\0'}, // "bbb"
        {'a', 'b',  'c',  '\0'}  // "abc"
    };

    // 출력 테스트 (정상적으로 문자열로 인식하는지 확인)
    for (int i = 0; i < 5; i++) {
        printf("L[%d] : %s\n", i, L[i]);
    }

    return 0;
}

Python하다가 왜 뜬끔없이 C언어가 튀어나왔냐면 문자열들을 사전 순으로 정렬할 때 로우 레벨까지 내려가야 설명이 되거든요.

우선 각 문자열마다 index 0부터 정렬합니다. 그러면 'a' 그룹과 'b' 그룹으로 나누어 떨어지는데 각각 (a, ab, abc), (b, bbb)로 나누어집니다.

그 다음으로 index 1 기준으로 정렬하면 ("a ", ("ab", "abc")), ("b ", "bbb")로 나누어집니다.

마지막으로 index 2 기준으로 정렬하면 ("a  ", ("ab ", "abc")), ("b  ", "bbb")로 나누어 떨어지고 괄호들을 모두 없애고 리스트로 표현하면 아까 전에 나왔던 ['a', 'ab', 'abc', 'b', 'bbb']가 나오게 됩니다.

이것이 바로 문자열들을 사전 순으로 정렬하는 원리입니다.

문자열들을 정렬할 때 주로 기수 정렬 혹은 트라이(Trie) 알고리즘 등을 사용해서 이를 차례대로 저장하는 방식입니다.

참고로 영어이든 한글이든 index 0을 최우선 정렬 기준으로 하여 index +1씩 하면서 유니코드(영문자인 경우 아스키 코드) 오름차순으로 정렬됩니다.

 

이제 정렬 알고리즘에 대해 두려움이 없어졌나요?

그 외에도 정렬 알고리즘을 구현하는데 버블 소트나 머지 소트 등 뭐 다양한 정렬 알고리즘들이 다수 존재하지만 Python에서는 그냥 sort() 혹은 sorted()만 사용하면 Python에서 알아서 정렬해줍니다.(심지어 문자열 사전순 정렬도 sort() 하나만 붙여주면 알아서 다 해줍니다!)

만약 원본 리스트 자체를 정렬하고 싶다면 sort(), 원본 리스트는 변하지 않고 복사 리스트에 정렬된 결과를 넣고 싶다면 sorted()를 사용합니다.

 

즉, L.sort()이냐 아니면 L2 = sorted(L1)이냐의 차이일 뿐 둘 다 정렬해주는 알고리즘입니다.