정렬 알고리즘 개요

정렬이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다. 정렬 알고리즘으로 데이터를 정렬하면 이진 탐색(Binary search)이 가능해진다. 이진 탐색의 전처리 과정이기도 하다.

정렬 알고리즘은 크게 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬 등이 있다.

파이썬의 정렬 라이브러리

알고리즘 문제를 풀 때는 정렬 알고리즘들을 직접 작성하게 되는 경우도 있지만 미리 만들어진 라이브러리를 이용하는 것이 효과적인 경우가 더 많다.

파이썬의 기본 라이브러리인 sorted()를 사용하게 되면 최악의 경우에도 시간 복잡도 O(NlogN)을 보장하기 때문이다.

1. 정렬 라이브러리로 풀수 있는 문제: 단순히 정렬 기법을 알고 있는지 물어보는 문제로 기본 정렬 라이브러리의 사용 방법을 숙지하고 있으면 어렵지 않게 풀 수 있다.
2. 정렬 알고리즘의 원리에 대해서 물어보는 문제: 선택 정렬, 삽입 정렬, 퀵 정렬 등의 원리를 알고 있어야 문제를 풀 수 있다.
3. 더 빠른 정렬이 필요한 문제: 퀵 정렬 기반의 정렬 기법으로는 풀 수 없으며 계수 정렬 등의 다른 정렬 알고리즘을 이용하거나 문제에서 기존에 알려진 알고리즘의 구조건인 개선을 거쳐야 풀 수 있다.

ref
이것이 취업을 위한 코딩 테스트다 with 파이썬
나동빈 유튜브 강의