면접을 준비하자 - 자료구조/알고리즘편

선택 정렬에 대해서 말해보세요.

선택정렬은 N번의 순환과정에서, 가장 작은 또는 큰값을 찾아

처음부터 차례대로 교체함으로써 정렬하는 방식입니다.

N번의 순환에대해서 N번의 비교를 하기 때문에 bigO(N^2)의 시간 복잡도를 가집니다.

비교적 데이터 이동이 적은 것이 장점입니다.

<br/>

<br/>

버블 정렬에 대해서 말해보세요.

버블정렬은 가장 간단한 정렬 방식입니다.

다음 데이터와 비교하여, 정렬에 맞게 위치를 교체해줍니다.

버블정렬은 N번의 순환과정에서 최대 N번의 비교/교체 하며 따라서 bigO(N^2)의 시간복잡도를 가집니다.

장점은 가장 간단하지만, 비교적 자료 교환연산이 많아 잘 사용하지 않습니다.

<br/>

<br/>

삽입 정렬에 대해서 말해보세요.

자신의 앞의 데이터와 비교하여, 자신의 위치를 찾아 "삽입"함으로써 정렬하는 방식입니다.

최악의 경우 N번의 루트에서 최대 N번의 비교를 가져 bigO(N^2)의 시간 복잡도를 가집니다.

최선으 경우 이미 정렬되어있는 경우에 bigO(N)의 시간복잡도를 가집니다.

삽입 정렬의 장점은 안정된 정렬이며, 이미 어느 정도 정렬되어있는 경우에 효과적입니다.

<br/>

<br/>

병합 정렬에 대해서 말해보세요.

병합 정렬은 분할정복 방식을 이용한 정렬 방법입니다.

데이터를 분할하고, 이를 반복합니다. 최대 분할하여 병합과정에서 정렬하는 방식입니다.

최대 log2N개로 분할되며, 각 병합과정마다 최대 N개의 비교가 이루어지기 때문에 bigO(Nlog2N)의 시간 복잡도를 가집니다.

병합정렬의 장점은 안전한 정렬이며, 최악 평균 최대 모두 동일한 시간복잡도를 가집니다.

단점으로는 추가공간을 필요로하며, 비교적 이동연산이 많아 링크드 리스트를 사용하는 것으로 보안 할 수 있습니다.

<br/>

<br/>