목차
정렬의 정의
정렬이란?
정렬(sort)은 데이터를 특정 기준에 따라서 정렬하는 과정이다. 주로 오름차순, 내림차순으로 정리하며 문자열의 경우에는 알파벳순, 한글순과 같은 방식으로 정렬한다.
데이터를 효율적으로 탐색하고 관리하기 위한 대표적인 알고리즘이다.
시간복잡도
정렬은 정렬의 방식, 입력 값의 크기 따라서 수행시간이 천차만별이다. 이러한 정렬을 해결하는 것에 걸리는 시간과 연산 횟수의 상관관계를 나타내는 척도가 시간복잡도이다.
간단하게, 정렬을 하는데 걸리는 시간이 얼마정도인지를 파악할때 쓴다고 생각해도 좋다.
시간복잡도는 보통 빅오표기법으로 표기하는데 O(n)과 같은 방식으로 표기한다.
최선 평균 최악
시간복잡도를 계산할때, 알고리즘의 최악의 경우를 기준으로 계산하다. 아래는 최악의 경우가 무엇인지, 최선과 평균은 무엇인지에 대해 기술한 내용이다.
-
최선의 경우
최선의 경우는 배열이 미리
기준에 맞게 정렬되어있을때를 의미한다.
예를 들어, [1, 2, 3, 4, 5]라는 배열이 있고, 이를 오름차순으로 정렬하려 한다면, 이미 정렬이 되어있음으로 최선의 경우이다. -
평균의 경우
평균의 경우는 입력 데이터가 들어왔을 때의 평균적인 수행 성능을 의미한다.
-
최악의 경우
이는 알고리즘이 가장 많은 연산을 수행하는 경우이다.
안정정렬
이는 동일한 값을 가진 데이터를 정렬했을때, 입력된 데이터의 순서를 유지하는것을 의미한다.
안정정렬은 안정 정렬이라는 의미 그대로 안정하게 정렬하는 것이라고 생각하면 편하다.
예를 들어,
(90, A학생)
(80, B학생)
(80, C학생)라는 데이터가 있다고 가정해보자.
이를 점수를 기준으로 정렬할경우
(80, B학생)
(80, C학생)
(90, A학생)이처럼 입력순서에 따라 B이후에 C가 정렬된다.
하지만 불안정정렬의 경우에는
(80, C학생)
(80, B학생)
(90, A학생)이와 같이 점수로 정렬은 됐지만, 데이터의 입력순서는 지켜지지 않는다.
