정렬(Sorting)

지금까지 형태에 따른 자료구조의 종류와 정의에 대해 알아보았습니다.

이번 포스팅부터는 정렬에 대해 알아보겠습니다.

정렬(Sorting)은 물건을 크기순으로 오름차순(ascending order)이나 내림차순(descending order)으로 나열하는 것을 의미한다.

예를 들어 책들은 제목 순, 저자 순, 발간 연도 순으로 정렬이 가능하다. 

사람도 나이, 키, 이름 등을 이용하여 정렬할 수 있다.

물건뿐만 아니라 어떤 형태의 것도 서로 비교만 가능하면 정렬할 수 있다.

정렬은 컴퓨터 공학을 포함한 모든 과학 기술 분야에서 가장 기본적이고 

중요한 알고리즘 중의 하나로 일상생활에서 많이 사용된다.

또한 정렬은 자료 탐색에 있어서 필수적이다.

예를 들면 영어 사전에서 우리가 단어를 쉽게 찾을 수 있는 것은 사전 안의 단어들이 알파벳 순으로 정렬되어 있기 때문이다.

만약 사전이 알파벳 순으로 정렬되어 있지 않다면 특정 단어를 찾는 것은 거의 불가능 할 것이다.

이는 컴퓨터도 마찬가지다. 

비록 컴퓨터가 사람보다 속도는 더 빠르지만 정렬되어 있지 않은 자료에서는 탐색의 효율성이 크게 떨어진다.

컴퓨터 용어 사전에 기재 된 정렬은

분류하다. 데이터 항목을 지정 된 순서로 나열하는 것을 가리킨다. 라고 정의 되어 있다.

정렬 알고리즘은 비교에 의한 정렬(comparative sort)과 분산에 의한 정렬(distributive sort)로 나누어진다.

차이점에 대해서는 추후 포스팅에서 알아보도록 하겠다.

일반적으로 정렬시켜야 될 대상은 레코드(recode)라고 불린다. 

레코드는 다시 필드(field)라고 하는, 더 작은 단위로 나누어 진다.

위 그림과 같은 경우는 학생의 이름, 주소, 연락처 등이 필드가 될 것이다.

여러 필드 중에서 특별히 레코드와 레코드를 식별해주는 역할을 하는 필드는 키(key)라고 한다.

학생 레코드의 경우에는 학번이 키가 될 수 있다.

정렬이란 결국 레코드들을 키 값의 순서로 재배열하는 것이다.

지금까지 개발 된 정렬 알고리즘은 정말 많다. 

그러나 아직까지 모든 경우에 있어 최상의 성능을 보여주는 최적 알고리즘은 존재하지 않는다.

따라서 다양한 정렬 방법들 중에서 현재의 프로그램 수행 환경에 

가장 효율적인 정렬 알고리즘을 선택해야 한다.

대개 정렬 알고리즘을 평가하는 효율성의 기준으로는 정렬을 위해 필요한 비교 연산의 횟수와 이동 연산의 횟수이다.

이들 횟수를 정확하게 구하기는 힘들기 때문에 이들 횟수를 빅오 표기법을 이요하여 근사적으로 표현한다.

위 그림은 각종 정렬 알고리즘을 시각적으로 표현해 놓은 것입니다.

위에서 말했듯이 각종 정렬 알고리즘들 중에서 현재의 프로그램 수행 환경에 

가장 효율적인 정렬 알고리즘을 선택하는 것이 가장 중요합니다.

그러기 위해선 각 정렬 알고리즘에 대한 이해가 필요 할 것입니다.

다음 포스팅부터는 정렬 알고리즘에 대해 알아보겠습니다.