졸지말고..

저번 포스팅에서 언급했듯이 정렬에 대해서 알아보도록 하겠습니다.

우선 정렬 알고리즘을 배우기 전에 정렬의 안정적 특성에 대해서 알아야 할 필요가 있습니다.

이 특성을 모르고 정렬 알고리즘을 선택한다면, 우리가 원하는 결과를 얻지 못할 수 있기 때문입니다.

정렬의 안정적 특성이란?

정렬의 안정적 특성이란 "정렬되지 않은 상태에서 같은 키값을 가진 원소의 순서가 정렬 후에도 유지되느냐" 입니다.

이러한 정렬의 안정적 특성에 따라서 정렬 알고리즘은 안정 정렬과 불안정 정렬로 구분 할 수 있습니다.

예를 들어, 아래와 같은 포커 카드에 대해서 번호를 키값으로 하여 오름차순으로 정렬하고자 합니다

이때, 우리는 약간 이상한 성향으로 인해(?) 같은 숫자카드의 무늬 순서를 유지시키고자 합니다.

즉, 아래 그림의 경우 정렬 후에도 하트4 뒤쪽에 스페이스4가 위치하게 하고 싶다는 의미입니다.

"당연히 유지되는게 정상 아니야?" 라고 생각 하실 수 있지만, 정렬 알고리즘에 따라서 정렬 후에 이 순서가 바뀔 수도 있습니다.

안정 정렬(Stable Sort) 

안정 정렬의 경우에는 정렬 후에도 원래의 순서가 유지되며, 결과는 다음과 같습니다.

정렬된 결과에서 하트4와 스페이스4의 순서가 그대로 유지되고 있음을 확인 할 수 있습니다.

불안정 정렬(Unstable Sort)

불안정 정렬의 경우에는 정렬 후에도 원래의 순서가 유지된다는 보장을 할 수 없으며, 결과는 다음과 같을 수 있습니다.

안정 정렬의 결과와는 달리 스페이스4와 하트4의 순서가 바뀐 모습을 확인 할 수 있습니다.

앞으로 배울 정렬 알고리즘에는 안정 정렬 알고리즘도 있고, 불안정 정렬 알고리즘도 있습니다.

따라서 이를 구분해서 학습을 해야 합니다. 너무 걱정하지는 마세요! 정렬 알고리즘을 설명할 때 같이 하도록 하겠습니다.

이번 포스팅은 여기까지며 다음 글부터 본격적으로 정렬 알고리즘에 대해서 알아보도록 하겠습니다!

알고리즘(Algorithm)?

우리는 컴퓨터로 많은 문제를 해결합니다.

여기서 문제를 해결한다는 의미는 우리가 아는 흔한 수학 문제일 수도 있고 실생활에 필요한 요구사항일 수도 있습니다.

하지만 컴퓨터는 사람처럼 똑똑하지 않아서 시키는 일만 수행합니다.

그렇기 때문에 컴퓨터로 사람이 요구 하는 문제를 해결하기 위해서는 그 문제에 대한 해결 방법을 함께 제시해줘야 합니다.

그것을 알고리즘이라고 부릅니다. 더불어 한 가지 문제에대한 여러 가지 해결 방법이 있을 수 있고,

이러한 상황 속에서 성능 분석을 통해서 가장 좋은 알고리즘을 선택해야 합니다.

공간 복잡도(Space Complexity)와 시간 복잡도(Time Complexity)

컴퓨터에게 명령을 내리는 알고리즘의 성능의 척도에는 공간 복잡도와 시간 복잡도가 있습니다.

공간 복잡도는 해당 알고리즘을 수행하는 데 있어서 필요한 메모리 양이며,

시간 복잡도는 해당 알고리즘을 수행하는 데 필요한 시간입니다.

그리고 이러한 복잡도를 우리는 세 가지 점근적 표기법을 활용해 나타냅니다.

점근적 표기법

점근적 표기법은 아래와 같이 세 가지로 표시하며 뜻은 다음과 같습니다.

점근적 상한을 나타내며, "아무리 심해야 이 정도다." 라는 의미입니다. (최악의 경우)

점근적 하한을 나타내며, "최소한 이 정도다" 라는 의미입니다.(최선의 경우)

점근적 하한을 나타내며, "대략 이 정도다" 라는 의미입니다.(평균적인 경우)

이러한 표기법들은 보통 문제 해결에 대한 입력 n에 대해서 표기합니다.

앞으로 다양한 알고리즘을 소개할 때, 보통 Oh 표기법을 많이 활용할 것 입니다.

왜냐하면 많은 시스템에서 성능을 보장하기 위해서는 최악의 경우를 고려하는 것이 올바르기 때문입니다.

이번 포스팅은 여기까지 진행하도록 하겠습니다!

추가적으로 설명이 필요한 부분이 있다면, 언급해주시고 계속 수정하도록 할게요

그리고 다음 포스팅에서는 , 의 시간 복잡도를 가지는 정렬 알고리즘에 대해서 알아보도록 하겠습니다.