오봉이와 함께하는 개발 블로그

Algorithmday_4 정리 (2021.12.01 수요일) 쉘 정렬(Shell Sort) 원소의 비교 연산과 먼 거리의 이동을 줄이기 위해 몇 개의 서브 리스트로 나누어 삽입 정렬 반복 수행 삽입 정렬의 개념을 확대하여 일반화 시킨 정렬 방법 삽입 정렬의 최대 문제점은 요소들이 이동할 때 이웃한 위치로만 이동한 것 쉘 정렬에서는 요소들이 멀리 떨어진 위치로도 이동할 수 있기 때문에 쉘 정렬이 삽입 정렬보다 속도가 빠름. 정렬 방법 정렬에서 사용할 간격 결정 전체 원소 수 n의 1/3, 다시 이것의 1/3.... 간격이 작아질수록 짧은 거리를 이동하고 원소 이동이 적음 첫 번째 간격에 따라 서브 리스트로 분할 각 서브 리스트에 대하여 삽입 정렬 수행 두 번째 간격에 따라 서브 리스트로 분할 각 서브 리..

Algorithmday_4 정리 (2021.12.01 수요일) 삽입 정렬(Insertion Sort) 정렬되어 있지 않은 부분의 왼쪽 끝에서 삽입할 원소를 찾아서 정렬되어 있는 부분의 적절한 위치에 삽입 정렬 안 된 부분의 숫자 하나가 정렬된 부분에 삽입됨으로써, 정렬된 부분의 원소 수가 1개 늘어나고, 동시에 정렬이 안 된 부분의 원소 수는 1개 줄어든다. 이를 반복하면 결국 정렬 안 된 부분에는 아무 원소도 남지 않고 정렬된 부분에 모든 원소가 존재 정렬 방법 정렬되어 있지 않은 부분의 왼쪽에서 삽입할 원소 k 선택 빈자리 확보를 위해 k를 꺼내서 임시 장소에 보관 정렬되어 있는 부분에서 k보다 큰 원소들을 오른쪽으로 이동하여 k가 들어갈 빈자리 확보 확보된 빈자리에 k삽입 모든 원소들이 정렬될 때 ..

Algorithmday_4 정리 (2021.12.01 수요일) 선택 정렬(Selection Sort) 잘못된 위치에 들어가 있는 원소를 찾아서 그것을 올바른 위치에 넣는 원소 교환 방식으로 정렬 가장 작은 원소를 찾아 첫 번째 위치의 원소와 교환 두 번째로 작은 원소를 찾아 두 번째 위치의 원소와 교환 첫 번째 원소를 키로 지정하고 뒤 원소와 비교해서 작은 값을 앞으로 보내는 방식 두 번째 원소를 키로 지정하고 뒤 원소와 비교해서 작은 값을 앞으로 보내는 방식 정렬될 때 까지 과정 반복 초기 : 5, 2, 8, 3, 1 1라운드 키는 첫 번째 원소 2, 5, 8, 3, 1 (5와 2교환) 1, 5, 8, 3, 2 (2와8, 3을 비교 했지만 2가 작기 때문에 교환하지 않고, 2와 1교환) 2라운드 1, ..

Algorithmday_4 정리 (2021.12.01 수요일) 버블 정렬(Bubble Sort) 인접한 항목이 순서대로 되어 있지 않으면 서로 교환한다. a = [7,6,5,2,1,4,8,9,3] 원본 a = [6,7,5,2,1,4,8,9,3] 7, 6 교환 a = [6,5,7,2,1,4,8,9,3] 7, 5 교환 a = [6,5,2,7,1,4,8,9,3] 7, 2 교환 a = [6,5,2,1,7,4,8,9,3] 7, 1 교환 a = [6,5,2,1,4,7,8,9,3] 7, 4 교환 a = [6,5,2,1,4,7,8,3,9] 7, 8 / 7, 9는 맞기 때문에 건너 뛰고(하지만 비교는 하기 때문에 성능에 영향을 끼친다.) 9, 3 교환 까지 1라운드 종료 -> 다시 a[0], a[1]비교부터 시작 a =..

Algorithmday_4 정리 (2021.12.01 수요일) 정렬(Sort) 일련의 자료들을 자료 중에 포함된 몇 가지 항목을 우선대로 지정하여 그 순서에 따라 모든 자료를 나열하는 방법 정렬 알고리즘 종류 버블 정렬(Bubble Sort) 선택 정렬(Selection Sort) 삽입 정렬(Insertion Sort) 쉘 정렬(Shell Sort) 퀵 정렬(Quick Sort) 이원 합병 정렬(2-Way merge Sort) 기수 정렬(Radix Sort) 힙 정렬(Heap Sort) 정렬 알고리즘 단순하지만 비효율적인 방법 : 삽입 정렬, 선택 정렬, 버블 정렬 복잡하지만 효율적인 방법 : 퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬 정렬 알고리즘의 평가 비교 횟수 이동 횟수 모든 경우 최적인 알고리..