[자료구조] 정렬 알고리즘 (버블, 선택, 삽입)

들어가며

정렬은 물건이나 숫자, 글자 등을 일정한 순서대로 나열하는 것을 말한다. 예를 들어, 집에서 장난감을 크기순으로 줄을 세운다고 생각해 보면 크기순, 알파벳 순서 등으로 나열하는 것을 정렬이라고 한다.

버블 정렬 (Bubble Sort)

버블 정렬이란 버블 정렬은 옆에 있는 숫자와 비교해서 큰 숫자를 뒤로 보내는 방법이다.

그렇다면 어떻게 하냐 질문 할 수 있다.

1. 첫 번째 숫자부터 시작해서 바로 옆의 숫자와 비교한다.
2. 첫 번째 숫자가 더 크면, 두 숫자의 위치를 바꿔준다.
3. 이런 식으로 계속해서 맨 끝까지 가면, 가장 큰 숫자가 맨 뒤로 가게 된다.
4. 이제 가장 큰 숫자는 제 자리를 찾았으니, 나머지 숫자들도 같은 방법으로 정렬해주면 된다.

선택 정렬 (Selection Sort)

선택 정렬이란 선택 정렬은 가장 작은 숫자를 찾아서 맨 앞에 놓는 방법이다.

이또한 어떻게 하냐 질문 할 수 있다.

1. 처음부터 끝까지 모든 숫자를 확인해서 가장 작은 숫자를 찾는다.
2. 그 작은 숫자를 맨 앞과 바꿔준다.
3. 맨 앞의 숫자는 제 자리를 찾았으니, 다음 숫자부터 또 가장 작은 숫자를 찾아서 바꿔주면 된다.

삽입 정렬 (Insertion Sort)

삽입 정렬이란 삽입 정렬은 숫자를 하나씩 뽑아서, 알맞은 자리에 넣는 방법이다.

어떻게 하냐 물어본다면

1. 두 번째 숫자부터 시작한다. 첫 번째 숫자는 이미 정렬된 것으로 간주한다.
2. 두 번째 숫자를 뽑아서, 첫 번째 숫자와 비교한다. 뽑은 숫자가 더 작으면 앞에, 크면 뒤에 둔다.
3. 세 번째 숫자도 같은 방법으로 알맞은 자리에 놓고, 이런 식으로 끝까지 계속한다.

정렬은 마치 우리가 방 정리를 할 때, 옷을 크기 순이나 색깔 순으로 정리하는 것과 비슷하다. 이 세 가지 방법 중 어떤 방법이 좋을지는 상황에 따라 다르니, 여러 방법을 알고 있으면 언제든지 적절한 방법을 선택할 수 있다.

코드 시연

버블 정렬 (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]
    return arr

선택 정렬 (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]
    return arr

삽입 정렬 (Insertion Sort) 삽입 정렬은 현재 위치에서, 그 이전의 배열을 보면서 자신의 위치를 찾아 삽입하는 방식이다.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        # 현재 위치의 이전 위치부터 시작
        j = i-1
        # key 값을 이전의 배열에서 적절한 위치에 삽입
        while j >=0 and key < arr[j]:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key
    return arr

결론

우리는 매일매일 여러 가지를 선택하고 정렬한다. 이런 일들은 생각보다 쉽지 않다. 그래서 컴퓨터는 우리에게 도와주려고, 여러 가지 마법 같은 방법들을 사용한다. 그 중에서도 오늘 우리가 배운 세 가지 방법인 ‘버블 정렬’, ‘선택 정렬’, ‘삽입 정렬’은 특별한 마법처럼 동작하면서 숫자들을 정렬해 준다.

하지만 중요한 건, 어떤 방법이 최고다!라고 할 수는 없다. 모든 방법에는 각각의 장점과 단점이 있다. 그래서 우리는 상황에 맞게 가장 좋은 방법을 선택해야 한다. 마치, 여름에는 시원한 음료를, 겨울에는 따뜻한 음료를 선택하는 것처럼 말이다.

그리고 이런 정렬 방법을 배우는 것은 그냥 숫자를 정렬하는 것뿐만 아니라, 우리 일상에서도 많은 도움이 된다. 예를 들면, 방 청소를 할 때나, 과제를 할 때도, 어떤 순서로 해야 효율적일지 고민하게 매번 고민을 한다. 그럴 때마다 오늘 공부한 정렬의 원리를 생각해보면, 더 쉽고 빠르게 일을 할 수 있을거라고 생각한다.

정렬 알고리즘의 세부 결론

1. 버블 정렬 (Bubble Sort) 특징: 각각의 요소를 바로 옆에 있는 요소와 비교하여 큰 값을 뒤로 보내는 방식으로 정렬한다. 이 과정을 반복하면서 리스트 전체를 정렬한다. 장점: 코드가 간단하며, 알고리즘을 이해하기 쉽다. 단점: 이중 반복문을 사용하여 성능이 좋지 않다. 실제로 많은 데이터를 정렬할 때는 다른 알고리즘에 비해 비효율적이다.

2. 선택 정렬 (Selection Sort) 특징: 리스트에서 최소값(또는 최대값)을 찾아 맨 앞(또는 맨 뒤)에 위치시키는 방식으로 정렬된다. 매 회차마다 그 다음으로 작은 값을 찾아 위치를 교환한다. 장점: 불필요한 데이터의 교환 작업이 줄어든다. 단점: 마찬가지로 이중 반복문을 사용하므로 대규모의 데이터에서는 비효율적이다.

3. 삽입 정렬 (Insertion Sort) 특징: 정렬된 부분에 현재의 요소를 올바른 위치에 ‘삽입’하면서 리스트 전체를 정렬한다. 장점: 이미 어느 정도 정렬된 데이터에 대해서는 빠르게 동작한다. 데이터가 적을 때 효율적이다. 단점: 이중 반복문을 사용하므로 데이터가 많으면 비효율적이다.

이렇게 각 정렬 알고리즘이 가진 특징과 장단점을 더 구체적으로 알아봤다. 그러나 실제로는 여러 상황과 요구 사항에 따라 이보다 더 발전된 정렬 알고리즘들, 예를 들면 퀵 정렬, 병합 정렬, 힙 정렬 등이 사용된다. 이 알고리즘들은 데이터의 크기나 상태에 따라 더 빠르게 동작하며, 대규모의 데이터를 정렬할 때 훨씬 더 효율적이다.

맨 위로 올라가기