[cs50] 삽입정렬, 각 정렬의 시간복잡도 비교(Big-O 표기법)

삽입 정렬

자료를 정렬하는 또 다른 알고리즘 중 하나인데, 자료를 여러 번 비교하거나 교환할 필요가 없는 방법이 있습니다. 삽입정렬은 자료가 정렬된 부분과 정렬되지 않은 부분으로 나누어집니다. 정렬되지 않은 부분의 자료가 정렬된 부분의 자리로 삽입되는 형태의 정렬 방법입니다.

 

 -> 삽입정렬은 이전에 말한 버블정렬, 선형탐색(선택정렬)과는 다른 방식이다. 삽입정렬은 각 원소 값에 맞는 공간을 만들어 이동시킨다. 모든 원소가 정렬될 때까지 값이 완벽해지지 않는다. 왼쪽에서 오른쪽으로만 정렬을 수행하기 때문에 시간을 두고 실행해야 한다. 살펴본 정렬 방식들을 통해 각 알고리즘이 각자의 장단점을 가지고 있고, 개발자가 어떤 알고리즘을 선택해야 하는지 고민이 필요함을 느낀다.

 

실행

삽입 정렬은 배열을 정렬된 부분과 정렬되지 않은 부분, 두 개의 부분으로 나누면서 동작합니다. 만약 5, 1, 6, 2, 4, 3 이라는 값을 삽입정렬을 이용하여 정렬해주어야 한다면 다음과 같이 의사코드를 작성할 수 있습니다.

 

정렬된 배열

삽입 정렬은 특정 실행 단계에서, 어떤 원소가 정렬된 배열 내에 자리를 찾았다고 해서 그것이 최종적인 제자리라는 보장은 없습니다. 다음 단계가 진행되면서 다른 자료에 의해 위치가 바뀔 수 있기 때문입니다. 따라서 삽입 정렬은 자료의 양이 적을 때 성능이 우수하며 자료 대부분이 이미 정렬이 되어있는 경우 효율적입니다. 삽입정렬은 이미 정렬된 자료에 새로운 자료를 삽입해야 하는 경우가 발생하면, 정렬된 자료들이 자리를 이동해야 하므로 안정성이 낮습니다.

 

 

---

시간 복잡도

시간 복잡도란알고리즘을 수행할 때 걸리는 시간을 기준으로 효율성을 분석하는것입니다. 시간의 효율성이란 결국 알고리즘에서 비교와 교환 등이 일어날 때 연산자의 처리 횟수가 적다는 의미이며, 연산자의 처리 횟수가 적다는 건 시간의 복잡도가 낮다는 의미입니다. 따라서 시간 복잡도가 낮을수록, 연산자의 사용 횟수가 적을수록 효율성이 높은 알고리즘이 됩니다.

 

 -> 프로그램을 짤 때 데이터가 많을수록 단순화하여 작은값은 무시하고 중요한값을 이용하여 효율적으로 작동시키는 것이 중요하다. 이를 위해 시간복잡도를 알아야한다. 

 

 

Big-O 표기법

Big-O 표기법은 컴퓨터 과학에서 “대략”을 나타내는 공식적인 개념으로 최악의 경우에 대한 시간 복잡도를 나타내는 표현입니다. 

선형 탐색은 비교적 간단한데 찾는 값이 배열의 맨 끝에 있는 최악의 상황의 경우 이 값을 찾는데 n번의 단계를 거치면 됩니다. 이 개념은 O(n)으로 나타납니다. 

버블 정렬에서는 인접해 있는 자료와 쌍을 이루어 비교하기 때문에, n개의 자료를 갖는 배열은 n-1쌍을 비교합니다. n개의 자료가 있을때 n-1번 비교해주면, n번째의 자료가 정렬되어있습니다. 그 이후로 n-1개의 자료를 다시 비교하게 됩니다. 전체 비교 횟수는 (n-1) + (n-2) + … + 1은 n(n-1)/2이며, n2n^2n2/2−n/2n^2/2 - n/2n2/2−n/2 로 나타낼 수 있습니다. 시간 복잡도는 가장 중요한(가장 지수가 큰) 부분만 남기고, 계수를 삭제합니다. 따라서 만약 n2/2−n/2 의 가장 중요한 부분은 n2/2이 되며 이것은 (1/2)n2입니다. 계수를 제외하면 n2이 남고 O( n2)으로 표현합니다.

선택 정렬은 가장 작은 값(혹은 가장 큰 값)을 찾아 제 자리를 찾아줍니다. n개의 자료가 있다면 첫 번째 자료와 나머지 n-1개의 자료 중 가장 작은 값의 자리를 교환해주어야 합니다. n-1개의 자료 중에서 가장 작은 값을 찾기 위해서는 n-1번의 비교가 필요합니다. 즉 비교 횟수는 버블 정렬과 마찬가지로 (n-1) + (n-2) + … + 1이며, 시간복잡도는 O( n2)으로 표현합니다.

삽입 정렬은 n개의 자료가 있다면 첫 번째 자료는 정렬이 되었다고 생각하고, n-1개의 자료 중 첫 번째 자료와 정렬된 자료를 비교합니다. 이때 정렬된 자료는 1개이기 때문에 비교 횟수는 1입니다. 정렬되지 않은 부분에 1개의 자료가 남게 되면, 정렬된 자료의 수 n-1개 만큼의 비교가 필요합니다. 따라서 비교 횟수는 1 + 2 + … + (n-1)이며, 시간복잡도는 O( n2)으로 표현합니다.

 

-> Big-O 표기법 관련 포스팅 : https://juyeongpark.tistory.com/24