정렬 알고리즘은 N개의 숫자가 주어졌을 때, 사용자가 지정한 기준에 맞게 정렬하는 알고리즘을 말한다.

🤚🏻 잠깐, 집고 넘어가기

정렬 알고리즘에 대해 설명하기 전에 아래 개념을 알아두자.
Stable는 같은 값을 가지는 요소들이 정렬된 순서가 유지되는 것을 말하며, In Place는 입력 배열 외 추가적인 배열을 사용하지 않는 것을 말한다. Not Stable은 반대로 같은 값을 가지는 요소들의 정렬 순서가 유지되지 않는 것을 말하고, Not In Place는 추가적인 배열을 사용하는 것을 말한다. 정리하면 아래와 같다.

• stable : 중복된 키 값이 있을 때, 해당 값들이 처음 나타난 순서대로 정렬됨
• not stable : 중복된 키 값이 있을 때, 해당 값들의 상대적인 순서가 보장되지 않음
• in place : 추가적인 저장 공간을 상수 시간 내에 고정된 양만 사용함
• not in place : 추가적인 저장 공간을 원소들의 갯수에 비례하여 사용함

Stable이 중요한 이유는 예를 들어 학생들의 성적을 정렬할때, 이름순으로 먼저 정렬하고 같은 이름의 경우 성적 순서로 정렬하면 안정성 있는 정렬 알고리즘이 된다. 따라 Stable 하냐 Not Stable 하냐는 매우 중요한 속성으로 사용할 수 있다.

place 또한 원래 배열을 보존 해야 하는가, 아니면 추가적인 메모리 사용 없이 정렬을 처리 해야 하는가에 따라 사용할 수 있다.

1. Stable, In Place
   • 삽입 정렬, 버블 정렬, 머지 정렬
     머지 정렬은 일반적으로는 Stabel, 추가적인 배열 사용으로 Not in Place가 될 수 있음
2. Not Stable, In Place
   • 선택 정렬 , 퀵 정렬, 힙 정렬 퀵 정렬은 Pivot 선택 방법에 따라 Stable할수도 있고, 추가적인 배열 사용으로 Not in Place가 될 수 있음
3. Stable, Not In Place
   • 계수 정렬, 기수 정렬
4. Not Stable, Not In Place
   • 쉘 정렬

또한 정렬 알고리즘은 실행 방법과 정렬 장소에 따라 아래와 같이 분류할 수 있다.

1. 실행 방법에 따른 분류

정렬 알고리즘 실행 방법에 따라 비교식 정렬(Comparative Sort), 분산식 정렬(Distribute Sort)로 분류할 수 있다.

• Comparative Sort(비교식 정렬) : 비교식 정렬은 비교하고자하는 각 키값들을 한번에 두개씩 비교하는 교환 방식을 말한다. 대부분의 정렬 알고리즘이 비교식 정렬에 해당된다.
  • 버블 정렬, 선택 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬, 힙 정렬 등
• Distribute Sort(분산식 정렬) : 분산식 정렬은 키값을 기준으로 하여 자료를 여러 개의 부분 집합으로 분해하고, 분해한 집합들간의 비교, 교환, 이동 등의 작업을 통해 정렬하는 방식이다. 대부분의 비교식 정렬보다는 더 빠른 속도를 보인다는 장점이 있다.
  • 기수 정렬, 버킷 정렬, 카운팅 정렬 등

2. 정렬 장소에 따른 분류

정렬 알고리즘 장소에 따라 내부 정렬(Internal Sort), 외부 정렬(External Sort)로 분류할 수 있다.

• Internal Sort(내부 정렬) : 내부 정렬은 정렬할 자료를 메인 메모리에 올려서 정렬하는 방식으로, 속도가 빠르지만 자료의 양이 메모리의 용량에 따라 제한된다는 단점이 있다.
  • 버블 정렬, 선택정렬, 삽입 정렬, 퀵 정렬, 병합 정렬, 힙 정렬 등
• External Sort(외부 정렬) : 외부 정렬은 정렬할 자료를 보조 기억 장치에서 정렬하는 방식이다. 내부 정렬보다는 속도는 떨어지지만 대용량의 자료에 대한 정렬이 가능하다는 장점이 있다.
  • 병합 정렬 등

🥕 Bubble Sort(버블 정렬)

정렬 알고리즘의 종류는 여러가지가 있지만 이번 포스팅 시리즈로 버블 정렬, 선택 정렬, 삽입 정렬, 쉘 정렬, 퀵 정렬, 힙 정렬, 머지 정렬, 리덕스 정렬에 대한 이해와 파이썬 구현을 하려고 한다.

버블 정렬은 인접한 두 요소의 크기를 비교하여 서로 교환하는 정렬 알고리즘이다. 버블 정렬은 두 개의 for루프를 사용하여 구현할 수 있으며 첫 번째 for 루프는 정렬할 리스트 길이 만큼 반복하고, 두 번째 for 루프는 인접한 두 요소를 비교하여 정렬을 수행한다.

num_list = [0,7,5,2,8,6,1,10,3]

for lens in range(len(num_list)):
    for idx in range(len(num_list)-1):
        if num_list[idx] >= num_list[idx+1]:
            num_list[idx], num_list[idx+1] = num_list[idx+1], num_list[idx]

파이썬으로 구현하면 이렇게 구현할 수 있다. 이 형태는 버블 정렬의 기본적인 형태이고 많은 곳에서도 볼 수 있는 코드이지만, 이렇게 코드를 작성하게 된다면 정렬이 완료된 이후에는 더 이상 비교하지 않아도 되는데도 불구하고 계속 비교를 수행하게 된다. 그래서 아래와 같이 코드를 수정하면 조금 더 효율성을 높일 수 있다.

num_list = [0, 7, 5, 2, 8, 6, 1, 10, 3]

for i in range(len(num_list)):
    is_sorted = True
    for j in range(len(num_list) - 1 - i):
        if num_list[j] > num_list[j+1]:
            num_list[j], num_list[j+1] = num_list[j+1], num_list[j]
            is_sorted = False
    if is_sorted:
        break

이렇게 수정하게 된다면, 이전과 같이 정렬이 완료되었는지 여부를 확인하기 때문에 불필요한 순회를 종류할 수 있다.

장점

• 구현하기 쉽고 이해하기 쉬움
• 정렬할 데이터가 거의 정렬된 경우에는 다른 정렬 알고리즘보다 빠름
• 추가적인 메모리 공간이 필요하지 않음

단점

• 시간 복잡도가 $O(n^2)$으로 상당히 느리며, 데이터가 많아질수록 더욱 느려짐
• 최악의 경우에는 모든 원소를 비교해야 하므로, 정렬할 데이터의 크기에 비례하여 연산 횟수가 매우 많아짐
• Stabel Sort가 아니므로 같은 값에 대해 상대적인 순서가 보장되지 않음
• 다른 정렬 알고리즘에 비해 정렬 속도가 느리고 효율적이지 않음