정렬 : 크기 순서대로 나열하기

1. 정렬의 필요성과 알고리즘

대량의 자료 속에서 원하는 정보를 빨리 찾기 위해서는 자료들을 어떤 기준에 의해 정리해 두는 것이 좋다.

자료를 날짜별, 종류별, 장소별과 같은 기준을 정해 분류하고 분류된 데이터(자료)들을 가나다순 혹은 크기순으로 정렬해 놓으면 원하는 정보를 검색하는 데 드는 시간을 훨씬 단축할 수 있다. 이렇게 효율적인 정보 검색을 위한 방법 중 하나인 정렬에 대해 정리할 것이다.

 

1-1. 일상생활에서 사용되는 정렬

과일 이름 목록
사과	파인애플	모과
복숭아	살구	자몽
포도	메론	백도
수박	황도	대추
매실	앵두	토마토
자두	참외	키위

위와 같은 표에서 '수박'을 찾으려면 처으무터 하나하나 과일 이름을 쭉 훑어보아야 한다. 이를 순차 탐색이라고 한다. 그러나 순차 탐색은 시간이 많이 걸리기 때문에 다른 방법으로 검색을 하는 것이 좋다. 이를 위해 위의 '과일 이름 목록' 리스트를 가나다 순으로 정리해봤다.

과일 이름 목록
대추	매실	메론
모과	백도	복숭아
사과	살구	수박
앵두	자두	자몽
참외	키위	토마토
파인애플	포도	황도

'과일 이름 목록' 리스트는 이제 가나다 순으로 정렬이 되었고, '수박' 데이터를 찾기 위해서는 'ㅅ'으로 시작하는 과일 데이터만 살펴보면 된다. 이 예를 봤을 때 정렬은 대량의 자료에서 정보를 검색할 때 검색 시간을 줄여주는 최고의 방법이라고 할 수 있다.

 

1-2. 다양한 정렬 알고리즘

즉, 정렬(sort)이란 데이터를 일정한 규칙에 따라 재배열하는 것을 말하며, 각 리스트의 데이터들을 번호순이나 사전 순서와 같이 일정한 순서대로 정렬하는 알고리즘을 정렬 알고리즘(sorting algorithm)이라고 한다.

단순 정렬(simple sort)	삽입 정렬(insertion sort)
	선택 정렬(selection sort)
효율적 정렬(efficient sort)	병합 정렬(merge sort)
	셸 정렬(Shell sort)
	퀵 정렬(Quicksort)
	휩 정렬(Heap sort)
거품 정렬류	거품 정렬(bubble sort)
	교환 정렬(exchange sort)
	빗질 정렬(comb sort)
분산 정렬(distribution sort)	기수 정렬(radix sort)
	계수 정렬(counting sort)
	버킷 정렬(bucket sort)

삽입 정렬의 예시(출처 : stacktips.com)

삽입 정렬(insertion sort)은 적은 수의 데이터를 가진 리스트와 대부분 정렬된 리스트에 대해 상대적으로 효율적인 단순 정렬 알고리즘으로, 새로운 데이터의 크기를 따져 이미 정렬된 데이터 사이에 삽입하는 방법이다. 이 정렬 알고리즘은 셸 정렬과 같은 변형 형태를 만들어냈다.

 

위의 표에서 숫자 6을 맨 처음 칸에 넣었다. 그리고 그보다 큰 값인 8을 넣었다. 이후 4가 제일 작아 {6, 8}앞에 넣었고, 1 또한 그렇게 넣어 {1,4,6,8}의 목록이 만들어졌다. 그런데 3은 1보다 크고 4보다 작다! 이 때 {1,4,...} 중 {1,  ,4,...}처럼 1과 4 사이에 3이라는 값을 삽입해 {1,3,4,6,8}로 정리했다. 이런 정렬 방식을 삽입 정렬이라고 한다.

 

선택 정렬의 예시 (출처 : https://www.w3resource.com/)

선택 정렬(selection sort)은 제자리 비교 정렬 알고리즘으로, 정렬되지 않은 데이터 중에서 가장 작은 값을 찾아 앞자리 숫자와 교환하는 방법이다. 많은 리스트를 정렬할 때 비효율적이며, 비슷한 정렬 알고리즘 유형인 삽입 정렬보다 성능이 떨어진다. 그러나 이 선택 정렬은 단순성으로 유명하기 때문에 정렬을 이해하는데 도움이 된다.

 

위의 표에서 먼저 리스트의 제일 왼쪽에 있는 29를 기준으로 삼고 나머지 숫자를 본다. 13이 가장 작으니 이를 선택해 둘을 바꾼다. 그 다음에 위치한 72를 기준으로 잡고 나머지 숫자 중 가장 작은 29를 선택해 둘의 위치를 바꾼다. 이렇게 숫자를 차례로 정렬하여 숫자를 순서에 맞게 정렬한다. 이런 정렬 방식을 선택 정렬이라고 한다.

병합 정렬의 예시 (출처 : programiz.com/)

병합 정렬(merge sort)은 이미 정렬된 리스트를 새롭게 정렬된 리스트로 쉽게 병합할 수 있는 비교 기반 분류 알고리즘으로, 정렬할 데이터를 반으로 자르고, 자른 데이터를 다시 반으로 계속해서 자른 후 최소 단위가 되었을 때 두 개씩 정렬해 다시 병합하는 방법이다.

{6,5,12,10,9,1}이라는 리스트를 우선 이등분해 {6,5,12}와 {10,9,1}로 나눈다. 나눈 리스트들은 또 이등분해서 {6}, {5,12}의 한 리스트와 {10}, {9,1}의 다른 리스트로 나눈다. 여기서 이등분할 수 있는 {5,12}와 {9,1}를 또 나눈다.

그렇게 {6}, {5}, {12}, {10}, {9}, {1}로 나눠진 데이터를 다시 순서대로 정렬한다. 우선 분리한 것들을 다시 붙여준다.

{6},{5,12}와 {10},{1,9}처럼 말이다. 이를 다시 상위 리스트로 붙여준다. {5,6,12}와 {1,9,10}. 이제 마지막 원래 리스트를 재배열시키는 것이다. {1,5,6,9,10,12}. 이런 정렬 방식을 병합 정렬이라고 한다.

퀵 정렬의 예시 (출처 : favtutor.com/)

퀵 정렬(Quicksort)은 배열을 분할하기 위한 피벗(pivot)이라는 요소를 가지는 분할정복 알고리즘이면서 제자리 정렬 알고리즘으로, 정렬할 데이터 안에서 임의의 기준값을 선택하고 작은 데이터는 기준값 왼쪽에, 큰 데이터는 기준값 오른쪽에 가져다 놓는 방법이다. 피벗보다 작은 모든 요소가 피벗 이전으로 이동하고 더 큰 모든 요소가 피벗 다음으로 이동한다는 특징이 있다.

위의 표를 보자. 맨 처음 임의의 숫자 13을 피벗(배열 분할 기준값)으로 잡는다. 그리곤 13보다 작은 수들은 13의 왼편에, 13보다 큰 수는 오른편에 둔다. 13보다 작은 수 중에서는 또 임의로 11을 피벗으로 잡고, 13보다 큰 수들은 임의로 16을 피벗으로 잡고 같은 방식을 계속 반복한다. 그렇게 {4,7,11,12,13,15,16,18,19}와 같이 숫자가 순서대로 정렬된다. 이런 식의 정렬 방식을 퀵 정렬이라고 한다.

거품 정렬의 예시 (출처 : technologystrive.com/)

거품 정렬(bubble sort)은 리스트를 통해 단계를 반복하고 인접한 요소를 비교하며 순서가 틀리면 서로 교환하는 단순 정렬 알고리즘으로, 이웃한 데이터끼리 크고 작음을 따져 서로 위치를 교환하는 방법이다. 단순히 양 옆의 데이터의 크기를 비교해서 교환하기 때문에 선택 정렬과 비슷한 특징을 가진다.

위의 표를 보면, 맨 처음, 3과 5를 비교한다. 3보다 5가 크지 않으니 그대로 두었고, 그 다음 5와 2를 비교한다. 그런데 5가 2보다 크므로 2와 5를 바꾼다. 이런 식으로 인접한 두 숫자를 비교해서 큰 수를 뒤로 보내는 방식의 정렬을 거품 정렬이라고 한다.

기수 정렬의 예시 (출처 : programiz.com/)

기수 정렬(radix sort)은 숫자의 각 자리를 기준으로 차례대로 데이터를 정렬하는 비비교 정렬 알고리즘이다.

위의 표를 보면 맨 끝 1의 자리 숫자를 순서대로 정렬했고, 그 다음 10의 자리 숫자를 순서대로 정렬했고, 마지막으로 100의 자리 숫자를 순서대로 정리했는데, 이러한 방식으로 정렬하는 것을 기수 정렬이라고 한다.

버킷 정렬의 예시 (출처 : programiz.com/)

 

버킷 정렬(bucket sort)은 배열을 한정된 수의 버킷(bucket, 양동이)으로 분할하여 계수 정렬을 일반화하는 분할 정복 알고리즘이면서 정렬 알고리즘이다. 첫째자리 수만큼 통을 준비해 그곳에 데이터를 분류하고 정렬하는 방법이다.

위의 표를 보자. 우선 10개의 항목으로 구성된 리스트의 데이터를 숫자 범위별로 나눈 5개의 버킷(양동이)에 집어넣는다. 그리곤 각 버킷 안에서 숫자를 분류하고 이 분류된 숫자를 한 리스트로 다시 모으는 것이다. 이렇게 자료를 조건에 따라 여러 바구니에 나누어 담아 정렬하는 방식을 버킷 정렬이라고 한다.

 

1-3. 정렬이 필요한 정보 검색

그럼 이러한 정렬은 언제 어떻게 쓰이는 것일까?

2022년 6월 30일 네이버게임이 발표한 인기순 게임 순위 TOP5가 발표되었다. 이런 식으로 주변에서 순위(랭킹)이라는 용어로 정리해 놓은 많은 자료를 볼 수 있다. 이렇게 같은 자료라도 의미 있는 순서대로 정리를 해 놓으면 사용자들의 의사 결정에 큰 도움을 줄 수 있다. 또한 특정 기준에 의해 정렬된 대량의 자료를 통해 사용자는 원하는 정보를 더 빠르고 쉽게 찾을 수 있을 뿐 아니라, 보다 가치 있는 정보를 더 많이 생산해 낼 수 있게 되므로 일의 효율성도 높일 수 있다.