Python 69 - 정렬 _ 기준에 따라 데이터를 정렬 (개요)

정렬 알고리즘 개요

정렬(Sorting)이란, 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다.

프로그램에서 데이터를 가공할 때 오름차순이나 내림차순 등 대부분 어떤 식으로든 정렬해서 사용하는 경우가 많기에 정렬 알고리즘은 프로그램을 작성할 때 가장 많이 사용되는 알고리즘 중 하나다. 정렬 알고리즘은 이진 탐색의 전처리 과정이기도 하니 제대로 알고 넘어가자. 정렬 알고리즘은 굉장히 다양한데 이 중에서 많이 사용하는 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬만 이 언급하려 한다. 더불어 파이선에서 제공하는 기본 정렬 라이브러리를 적용하여 좀 더 효과적인 정렬 수행 방법도 다루여 한다.

 

보통 정렬부터 공부하면  '알고리즘의 효율성'을 쉽게 이해할 수 있어 알고리즘 개론서 초반에 정렬 알고리즘을 설명하는 경우가 많다. 또한 일반적으로 문제에서 요구하는 조건에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다. 상황에 적절하지 못한 정렬 알고리즘을 이용하면 당연히 프로그램은 비효율적으로 동작하며 필요이상으로 시간을 많이 소요한다. 그래서 정렬 알고리즘을 공부하다보면 자연스럽게 알고리즘 효율의 중요성을 깨닫는다.

 

공부한 책에 대한 내용은 코딩 테스트 합격을 주 목적으로 하기 때문에, 그리디 유형과 구현 유형에 대해서 먼저 다루었지만 정렬 알고리즘 또한 매우 중요하다. 면접에서도 단골 문제로 출제된다는 점을 기억하자.

이제 문제 상황에 대해서 생각해보자. 여기 숫자가 하나씩 적힌 카드가 10장의 카드를 오름차순으로 정렬하자.

어떻게 이 데이터(카드)를 정렬할 수 있을까?

보통은 카드를 빠르게 훑고 숫자가 0부터 9까지로 구성된 걸 눈치챈 다음 카드를 0부터 9까지 순차적으로 나열할 것이다. 이러한 과정 속에서 우리의 뇌는 우리도 모르게 데이터의 규칙성을 파악한다.

 

하지만 우리에게 쉽다고 컴퓨터에도 쉬운 일은 아니다. 컴퓨터는 인간과 다르게 데이터의 규칙성을 직관적으로 알 수 없으며, 어떻게 정렬을 수행할지에 대한 과정을 소스코드로 작성하여 구체적으로 명시해야한다.

 

이 카드 예제를 기준으로 이번 장에서는 정렬 알고리즘을 설명하겠다. 또한 이 장에서 다루는 예제는 모두 오름차순 정렬을 수행한다고 가정한다. 내림차순 정렬은 오름차순 정렬을 수행하는 알고리즘에서 크기 비교를 반대로 수행하면 된다. 또한 파이썬에서는 특정한 리스트의 원소를 뒤집는 메서드를 제공한다. 그래서 내림차순 정렬은 오름차순 정렬을 수행한 뒤에 그결과를 뒤집기(Reverse)하여 내림차순 리스트를 만들 수 있다. 리스트를 뒤집는 연산은 O(N)의 복잡도로 간단히 수행할 수 있으므로 이 책에서는 오름차순을 위한 소스코드만 다루도록 한다.

 

 

---

본 포스팅은 ‘이것이 코딩 테스트다 with 파이썬’을 읽고 공부한 내용을 바탕으로 작성하였습니다.

 

 

 

작성자 : 엄코딩 eomcoding