간혹 문자와 숫자를 정렬을 해야할 때가 있습니다.
그런 기능을 구현하려면 컴퓨터에게 "정렬해라" 이렇게 명령주면 되는데
근데 컴퓨터는 아쉽게도 "정렬해라" 이렇게 말하면 모르기 때문에 여러분이 하나하나 정렬하는 법을 알려줘야합니다.
그 방법들을 "정렬 알고리즘"이라고 부르는데 여러가지가 있습니다.
참고로 컴퓨터에선 문자도 숫자로 표현하기 때문에 숫자만 정렬할 수 있으면 문자도 정렬이 가능합니다.
Bogo sort라고 해서 그냥 무작위로 숫자들을 섞고 정렬되었나 확인하는 알고리즘도 있습니다.
100년 동안 해도 정렬이 안될 수도 있겠군요.
Stalin sort라고 하는 알고리즘은 그냥 왼쪽숫자, 오른쪽 숫자를 비교해서
오른쪽이 왼쪽보다 작은 숫자면 제거해버리는 알고리즘입니다.
숫자가 일부 없어지긴 하겠지만 정렬은 잘 되겠군요.
Quicksort
굉장히 효율적인 알고리즘도 있습니다.
Quicksort가 가장 유명할텐데 60년 전에 나온건데 쉽고 빨라서 아직까지도 배리에이션이 널리 쓰이고 있습니다.
[7, 2, 1, 6, 8, 5, 3, 4]이런 숫자들을 123 순으로 정렬해보도록 합시다.
퀵소트를 요약하자면
1. pivot용 숫자를 하나 정하고
2. 그거보다 작은 숫자는 pivot 왼쪽,
3. 그거보다 큰 숫자는 pivot 오른쪽에 이동시키는 식으로 정렬합니다.
4. 이걸 pivot 양옆에 있는 숫자들끼리 또 1번부터 3번을 적용해보는 식으로 재귀적으로 반복하면 정렬이 완성됩니다.
그림으로 상세히 설명하자면
우선 a, b라는 화살표를 차례로 -1번칸, 0번칸에 표시해놓습니다.
그리고 pivot도 하나 정해야하는데 편의상 가장 오른쪽에 있는 숫자를 pivot이라고 정하도록 합시다.
그 다음에 턴마다 b 화살표 위치를 하나씩 옮기면서 pivot 숫자와 비교해봅니다.
그래서 b 화살표 숫자가 pivot보다 작으면 그걸 왼쪽으로 보내버리면 되겠습니다.
왼쪽으로 보낸다는건 그냥
1. a 화살표 위치를 우선 +1 하고
2. b와 a가 가리키는 숫자를 서로 스왑하는 식으로 왼쪽으로 보내면 되겠습니다.
예를 들어 b가 움직이다가 7을 만나면 이건 pivot 4보다 크니까 스킵하고
b가 움직이다가 2를 만나면 이건 pivot 4보다 작으니까 a위치를 +1 하고나서 스왑해버립니다.
이번엔 b가 움직이다가 1을 만나면 이건 pivot 4보다 작으니까 a위치를 +1 하고나서 스왑해버립니다.
마지막까지 와서 b의 다음 숫자가 pivot이라면
pivot 숫자와 a+1 위치에 있던 숫자를 바꿔서
pivot을 중앙으로 옮겨줍니다.
그럼 이렇게 숫자가 배치됩니다.
pivot 기준으로
왼쪽은 pivot보다 작은 숫자,
오른쪽은 pivot보다 큰 숫자가 배치됩니다.
그래서 지금까지 했던 분류과정을 pivot 왼쪽 오른쪽에 있는 숫자그룹들끼리 또 해주면
결국 정렬이 완성됩니다.
이게 그 유명한 quicksort 알고리즘이 되겠습니다.
Quick Sort Visualizer
입력 후 정렬 버튼을 누르세요.
▲ 잼민이로 비주얼라이저도 만들어봤습니다.
단점
quicksort는 항상 빠른게 아니고 특정 상황에선 느릴 수 있습니다.
- 숫자갯수가 적으면 quicksort보다 다른 방식이 빠를 수도 있음
- 정렬이 이미 많이 되어있는 숫자들 같은 경우에는 pivot을 가장 오른쪽에 잡으면 비효율이 발생하고 그러는데
그래서 운이 나쁘면 정렬까지 n 제곱 만큼의 시간이 걸릴 수도 있습니다.
그래서 퀵소트를 하다가 중간에 너무 오래걸리는거 같으면 Heap sort라는 알고리즘으로 전환하기도 하고
숫자 갯수가 적으면 처음부터 Insertion sort 알고리즘을 사용하는게 더 빠를 수도 있습니다.
그걸 반영한게 C++ 등과 같은 프로그래밍언어 기본 정렬함수에서 사용하는 알고리즘이라고 보면 되겠습니다.
그래서 우리는 sort()만 소환하면 쉽고 빠르게 정렬이 가능한 것입니다.
