정렬

정렬(Sort)

---

정렬이란, 어떤 리스트가 주어졌을 때, 그 리스트를 정해진 순서대로 가지런히 나열하는 것을 의미한다. 정해진 순서로 다양한 방법이 있겠지만, 일반적으로 오름차순(Ascending) 혹은 내림차순(Descending)을 주로 사용한다.

오름차순이란 뒤로 갈수록 값이 커지는 순서로, 그래프에 표시했을 때 뒤로 갈수록 올라가기 때문이라고 이해하면 편하다. 반대로 내림차순이란 뒤로 갈수록 값이 작아지는 순서로, 오름차순과 마찬가지로 그래프를 떠올리면 쉽게 이해할 수 있다.

숫자 배열 { 9, 10, 108, 72, 66, 45, 62 }

문자열 { ‘A’, ‘a’, ‘C’, ‘K’, ‘b’, ‘z’, ‘F’ }

두 배열을 오름차순으로 정렬하면

{ 9, 10, 45, 62, 66, 72, 108 }, { ‘A’, ‘C’, ‘F’, ‘K’, ‘a’, ‘b’, ‘z’ } 로 정렬되고

내림차순으로 정렬하면

{ 108, 72, 66, 62, 45, 10, 9 }, { ‘z’, ‘b’, ‘a’, ‘K’, ‘F’, ‘C’, ‘A’ } 로 정렬된다.

컴퓨터에서 문자를 오름차순으로 정렬하는 것은 사전 순으로 정렬하는 것과 같은 의미라고 볼 수 있다. 또한, 영어에서 소문자가 대문자보다 뒤에 있는 이유는 아스키코드(ASCII Code)에서

‘A’ = 65 부터 시작되고, ‘a’ = 97 부터 시작되기 때문인데, 이는 정렬 방법을 조금만 조작하면 손쉽게 반대로 바꿀 수 있다.

정렬의 중요성

---

현재까지 알려진 정렬방법에 소요되는 시간복잡도는 O($n^2$) ~ O($n$ $log$ $n$)정도인데, 굳이 데이터를 이런 시간을 소요하여 정렬시켜 저장하는 가장 큰 이유가 바로 탐색의 효율성을 높이기 위함이다. 데이터가 정렬되어있지 않으면 어떠한 데이터에 접근하기 위해서는 순차탐색 혹은 랜덤접근이라는 시간복잡도가 O($n$)인 방법 밖에 없는데, 정렬되어있는 데이터에 대해서는 이진탐색(Binary Search)이라는 시간복잡도 O($log$ $n$)의 굉장히 강력한 알고리즘을 사용할 수 있게 된다. 요즘 대부분 빅 데이터를 다루고, 데이터베이스 내부의 무수히 많은 데이터에 대해 삽입이나 삭제보다 조회하는 횟수가 훨씬 많음을 고려하면 순차탐색만큼 비효율적인 탐색이 없을 것이다. 그렇기에 데이터를 정렬해두고 이진탐색을 활용하여 조회하는 것은 빅 데이터에서 시간을 줄이는 데에 필수적이라 볼 수 있다. 극단적인 예시를 들어서, 43억개의 데이터에서 어떤 데이터에 접근하기 위해서 순차탐색은 최악의 경우 42억회 비교를 해야하지만, 이진탐색은 O($log$ $n$)의 시간복잡도를 가졌기 때문에 최악의 경우에도 log 42억 = 약 32회 밖에 비교를 하지 않아도 된다. 바꿔 말하면 33회의 탐색만 하더라도 약 86억개의 데이터에서 어떤 값을 찾아낼 수 있다. 이진탐색에서 더 발전한 알고리즘인 비례탐색을 이용하면 시간을 더 줄일 수도 있다.

컴퓨터 과학을 공부하는 사람이라면 정렬 방법에 대해서는 기본적으로 학습하여 어떠한 알고리즘인지

이해해두는 것이 중요하다. 그만큼 자료구조를 효율적으로 관리하기 위한 가장 기본적인 방법이기 때문이다.

정렬의 구분

---

▶ 비교정렬    - 정렬 방법에서 값을 직접적으로 비교하느냐 하지 않느냐로 구분

▶ 제자리정렬    - 배열의 정렬을 위해 추가적인 공간을 사용하느냐 하지 않느냐로 구분

▶ 온라인정렬    - 원소들이 주어지지 않고 차례대로 주어지더라도 처리할 수 있느냐 없느냐로 구분

비교, 제자리, 온라인 정렬 등의 자세한 정렬 방법들은 추후에 소스코드와 함께 게시할 것이다.

출처 : 나무위키(정렬 알고리즘)