정렬 알고리즘2 [알고리즘] - 쉘 정렬 (Shell-sort) 1. 쉘 정렬(Shell-Sort)이란? 리스트를 일정한 간격에 따라 나누고, 각 부분 리스트를 삽입 정렬을 통해 정렬하는 방법이다. 앞선 글에서 삽입 정렬 에 대해 설명하였다. 삽입 정렬의 경우, 기존 배열이 어느정도 정렬되어있냐에 따라 수행 시간이 크게 차이난다. 현재 선택한 원소의 적절한 삽입 위치가 멀다면, 비교 & 이동해야하는 횟수가 많아지면서 수행 시간이 늘어나는 것이다. 정렬된 상태와 가까운 배열일수록 수행 시간은 단축된다. 즉, 삽입 정렬은 초기 리스트가 정렬이 된 상태일 경우 더 효율적이다. → 조금이라도 정렬이 된 상태에 가까운 배열로 만든 후에 삽입정렬을 수행하는 방법이 쉘 정렬이라고 할 수 있겠다. → 쉘 정렬은 삽입 정렬을 보완한 방법! 쉘 정렬의 시간 복잡도는 아직까지도 정확하게.. 2024. 4. 14. [알고리즘] - 삽입 정렬 (Insertion-sort) 1. 삽입 정렬(Insertion Sort)이란? 선택한 원소를 현재 정렬된 배열 범위 내의 적절한 위치에 삽입하는 방법이다. 구현하기 쉬운 알고리즘이지만, 시간 복잡도는 O(n²) 으로 다른 정렬 알고리즘들에 비해서 느린 편에 속한다. 2. 삽입 정렬의 수행 방식 삽입 정렬 과정 ① 현재 index의 원소를 선택한다. ② 정렬된 부분 내에서, 현재 선택한 원소가 들어갈 적절한 삽입 위치를 찾는다. ③ 삽입 위치부터 끝까지 데이터를 한 칸씩 뒤로 민다. ④ 삽입 위치에 현재 선택한 원소를 삽입한다. ⑤ index를 1 증가시키고, 다시 ①부터 반복한다. (index가 배열의 크기만큼 커질때까지 반복) 다시 말해, 인덱스를 증가시켜 가면서 배열의 원소를 선택하고, 선택한 원소를 정렬된 범위 내의 적절한 위.. 2024. 4. 9. 이전 1 다음
