waca's field

# 셸 정렬 개념 및 원리 셸 정렬(shell sort)은 Donald L. Shell 이 제안한 방법으로 삽입 정렬이 어느 정도 정렬 되어 있는 배열에 대해서는 대단히 빠르다는 점을 이용해 만든 방법이다. 셸 정렬은 삽입 정렬의 시간 복잡도 $O(n^2)$보다 빠르다. 삽입 정렬의 문제점은 요소들일 삽입될 때, 이웃한 위치로 한 칸씩만 이동한다는 점이다. // 제 블로그에 삽입 정렬로 검색하시면 관련 설명과 알고리즘을 확인해보실 수 있습니다. 삽입 정렬은 for 루프를 이용해 인접한 위치부터 한 칸씩 이동하며 삽입할 위치를 탐색하므로 만약 삽입할 원소가 들어갈 자리가 멀리 떨어져 있다면 한 칸씩 이동하는 설계 때문에 불필요하게 많은 반복과 비교를 해야 한다는 단점이 있습니다. 셸 정렬에서는 요소들이 멀..

# 삽입 정렬 삽입 정렬(Insertion Sort)은 데이터 집합을 순회하면서 정렬이 필요한 요소를 뽑아 이를 다시 적당한 곳에 삽입해 나가는 알고리즘이다. 마치 뒤섞여 있는 트럼프 카드를 순서대로 정리하는 모습과 같다. 카드를 한 장씩 뽑아 카드의 값에 따라 적절한 곳에 끼워 넣는 것을 반복하다 보면 결국 모든 카드가 순서대로 정리된다. 마찬가지로 데이터 집합에서 요소를 하나씩 뽑아 적절한 곳에 끼워 넣는 것을 반복하다 보면 정렬된 데이터 집합을 얻을 수 있다. 삽입 정렬은 구현이 간단해서 버블 정렬과 함께 프로그래머들에게 애용되는 알고리즘 중 하나다. 성능 또한 버블 정렬과 비슷하다. 이 알고리즘은 아래의 과정을 통해 정렬을 수행한다. 오름차순으로 정렬할 때를 가정한다. 데이터 집합에서 정렬 대상이..