알고리즘의 정의와 삽입정렬 InsertionSort 파헤치기

안녕하세요

블레이즈 테크노트 

블레이즈 입니다. 

이번 포스트에서는 알고리즘에 대해서 공부해보고자 합니다. 

 

알고리즘 Algorithm이란 무엇일까요? 

제가 배운 바에 의하면 그 정의는 다음과 같습니다. 

 

An Algorithm is a sequence of computational steps that transform the input into the output. 

이를 보면 input과 output이 굉장히 중요하다는 것을 알 수 있습니다. 

 

 

가장 대표적인 알고리즘이 sorting problem입니다. 

 

이 sorting을 효율적으로 할 수 있기 때문에 컴퓨터가 단순히 계산기를 넘어 그 이상의 가치를 발휘하기 시작했다고 볼 수 있습니다. 

 

 

 

이번 포스트에서 먼저 살펴볼 것은 삽입정렬 InsertionSort 입니다. 

 

삽입정렬의 원리를 먼저 생각해보겠습니다. 

 

삽입 정렬은 포커카드에서 우리가 습관적으로 하나씩 카드를 뽑아 원하는 위치로 옮기는 것과 유사한 방식으로 작동합니다. 

 

 

이를 슈도 코드로 작성해보면 다음과 같을 수 있을 것 같습니다. 

 

 

하지만 알고리즘의 정확성 (correctness of a algorithm)을 분명히 하기 위해선 

각 코드 라인 별로 알고리즘을 분석해야 합니다. 

 

 

 

이렇게 각 라인별로 몇 번 반복되는지 엄밀히 확인을 하고 나면 

전체 알고리즘의 계산횟수를 구할 수 있습니다. 

 

이 계산횟수는 알고리즘의 시간복잡도라고 할 수도 있습니다.

저희는 가장 최악의 상황, worst case의 time complexity를 계산해봤습니다.