알고 나면 유용한 알고리즘 정보... #2. 정렬 알고리즘

알고 나면 유용한 알고리즘 정보... #2. 정렬 알고리즘: 김가언 / 기사승인 : 2021-06-08 17:07:36

성적, 출석부, 평점 순, 가격순 등 대다수 데이터는 오름차순, 내림차순으로 정렬해야 사용하기 편리하다.
데이터 정렬 방법은 매우 다양하지만, 이번 기사에서는 단순한 정렬 알고리즘인 버블정렬, 선택정렬, 삽입정렬을 알아보자. 모두 오름차순을 기준으로 정렬한다고 가정해보자.

먼저 버블정렬에 대해 알아보자. 버블 정렬은 첫 번째 데이터와 두 번째 데이터, 두 번째 데이터와 세 번째 데이터를 비교하고 교환하면서 정렬하는 방법이다. 처음 정렬이 이루어지면 가장 큰 데이터부터 정렬되는 방식으로 모든 데이터를 정렬하기 위해서는 (데이터의 개수 - 1) 번 만큼 정렬해야 한다.

[5, 11, 8, 3, 1]을 버블 정렬로 정렬해보자.
1. [5, 11, 8, 3, 1] -> [5, 8, 11, 3, 1] -> [5, 8, 3, 11, 1] -> [5, 8, 3, 1, 11] : 11 정렬됨
2. [5, 8, 3, 1, 11] -> [5, 3, 8, 1, 11] -> [5, 3, 1, 8, 11] : 8, 11 정렬됨
3. [3, 5, 1, 8, 11] -> [3, 1, 5, 8, 11] : 5, 8, 11 정렬됨
4. [1, 3, 5, 8, 11] : 정렬 완료

위와 같이 모든 원소를 하나씩 비교하기 때문에 데이터 정밀 비교가 가능하다는 장점이 있다. 하지만, 데이터의 수가 많아질수록 정렬 과정에 오랜 시간이 걸린다는 단점이 있다.

이제 선택정렬에 대해 알아보자. 선택정렬은 첫 번째 데이터와 두 번째부터 마지막 데이터를 비교해 가장 작은 값을 첫 번째 자리로 교환하고, 두 번째 데이터와 세 번째부터 마지막 데이터를 비교한다. 그리고, 그중 가장 작은 값을 두 번째 자리로 교환하면서 정렬한다. 처음 정렬이 이루어지면, 가장 작은 값부터 정렬되는 방식으로 모든 데이터를 정렬하기 위해서는 버블 정렬과 같이 (데이터 개수 - 1) 번 만큼 정렬해야 한다.

[5, 11, 8, 3, 1]을 선택정렬로 정렬해보자.
1. [5, 11, 8, 3, 1] -> 1이 가장 작음 -> 5와 1 교환 -> [1, 11, 8, 3, 5] : 1 정렬됨
2. [1, 11, 8, 3, 5] -> 3이 가장 작음 -> 11과 3 교환 -> [1, 3, 8, 11, 5] : 1, 3 정렬됨
3. [1, 3, 8, 11, 5] -> 5가 가장 작음 -> 8과 5 교환 -> [1, 3, 5, 11, 8] : 1, 3, 5 정렬됨
4. [1, 3, 5, 11, 8] -> 8이 가장 작음 -> 11과 8 교환 -> [1, 3, 5, 8, 11] : 정렬 완료

예시처럼 데이터를 비교하는 횟수 자체는 많지만, 데이터를 교환하는 횟수가 적다는 특징이 있다. 데이터를 교환하는 횟수가 적기 때문에 교환이 많을수록 효율적으로 사용할 수 있다. 예를 들어, 오름차순으로 정렬된 데이터를 내림차순으로 정렬한다면, 교환을 많이 하지 않고도 정렬이 가능하다. 하지만, 비교 횟수가 많고 자료가 추가되면, 오랜 시간이 걸린다는 단점이 있다.

마지막으로 알아볼 정렬방법은 삽입정렬이다. 삽입정렬은 두 번째 데이터부터 시작해 그 왼쪽에 나열된 데이터를 비교해나가며 정렬하는 방식이다. 두 번째 데이터를 첫 번째 데이터와 비교해 데이터가 삽입될 위치를 찾아 삽입하고, 세 번째 데이터를 첫 번째 데이터 및 두 번째 데이터와 비교해, 데이터가 삽입될 위치를 찾아 삽입하는 방식으로 정렬이 이루어진다.

[5, 11, 8, 3, 1]을 삽입정렬로 정렬해보자.
1. [5, 11, 8, 3, 1] -> 11과 5 비교 -> 유지 -> [5, 11, 8, 3, 1]
2. [5, 11, 8, 3, 1] -> 8과 5, 11 비교 -> 5와 11 사이에 삽입 -> [5, 8, 11, 3, 1]
3. [5, 8, 11, 3, 1] -> 3과 5, 8, 11 비교 -> 5 왼쪽에 삽입 -> [3, 5, 8, 11, 1]
4. [3, 5, 8, 11, 1 ] -> 1과 3, 5, 8, 11 비교 -> 3 왼쪽에 삽입 -> [1, 3, 5, 8, 11] : 정렬 완료

버블정렬과 선택정렬과는 달리 빠른 정렬이 가능하다. 삽입정렬은 버블정렬의 비교회수를 줄이기 위해 고안된 정렬이므로 크기가 작은 데이터를 효율적으로 정렬할 수 있다.

세 가지 정렬 방법 모두 각각 장단점이 다르고 데이터의 수에 따라 걸리는 시간, 사용되는 메모리 크기 모두 다르다. 따라서 데이터의 수, 메모리의 크기 등 여러 상황을 고려하여 선택해야 한다.