[CS50] 알고리즘 기초 : 탐색, 정렬, 시간 복잡도

edwith CS50강의를 보며 정리했습니다.

---

선형탐색

 

우리가 원하는 자료를 탐색할 때 사용되는 알고리즘 중 선형 탐색(linear search)은 자료를 찾을 때까지 모든 자료를 탐색해야 하는 방법이다. 선형(linear)이라는 단어의 뜻 그대로, 선의 모양처럼 일직선을 그대로 따라 탐색하는 방법이다.

만약 리스트의 길이가 n이라면, 가장 최악의 경우에는 가장 마지막에 찾고자 하는 숫자가 있을 때, n-1번만큼 자료를 탐색해야한다. 보통 어떠한 정보도 없거나 자료가 정렬되어 있지 않을 때 사용하는 방법이다.

보통 가장 왼쪽부터 오른쪽으로 하나씩 이동하며 탐색을 한다. 이런식의 무작위 탐색은 굉장히 비효율적이기 때문에, 탐색을 하기 전에 정렬이 필수적인 이유를 알 수 있다.

 

버블정렬

어릴 때 했던 게임 중 버블버블이 생각나는 이름을 가진 버블 정렬! 인접한 두 개의 자료가 차례차례 비교되며 위치를 찾아가는 모습이 마치 거품이 보글보글 일어나는 것처럼 보인다 하여 붙여진 이름이라고 한다. 

버블 정렬은 단 두 개의 요소만 비교하기 때문에, 간단하지만 한 번의 정렬에 너무 많은 리소스가 낭비되는 경우가 발생할 수 있다. 만약 두 개의 인접한 수를 비교해서 순서에 맞으면 두고, 순서에 안 맞으면 교환하는 방식으로 작동한다.

n 개의 원소에 대해서 버블 정렬을 한 번 수행할 때 마다, n번째의 원소가 제 자리를 찾게 된다.

 

 

선택정렬

가장 작은 것을 찾아서 제자리에 배치한 후, 나머지 중 가장 작은 것을 찾아서 배치하는 방법을 반복적으로 사용하여 정렬하는 것을 뜻한다.

선택정렬은 교환횟수를 최소화할 수 있지만, 각 자료를 비교하는 횟수는 증가한다는 단점이 있다.

 

삽입정렬

삽입 정렬은 정리되지 않은 자료가 정렬된 부분의 자리로 삽입되는 형태의 방법이다.

정리가 안 되어있는 데이터들을 다른 상자에 차례대로 담아낼 때, 기존 상자에 있는 정리된 데이터는 새로 들어온 데이터가 삽입될 때마다 위치가 달라질 수 있다.

 

새로운 데이터가 삽입될 때마다 정렬된 자료들이 자리를 이동해야하는 가능성이 있으므로 안정성이 낮다.