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

Algorithmday_4 정리 (2021.12.01 수요일) 기수 정렬(Radix Sort) 정렬할 원소의 키 값을 나타내는 숫자의 자리수(radix)를 기초로 정렬하는 기법(사전식 정렬 방법) 정렬하고자 하는 값을 버킷에 넣어 정렬 버킷으로 큐 사용 데이터가 입력되는 곳, 출력되는 곳 : 먼저 들어온 것이 먼저 출력 버킷의 개수는 키의 표현 방법과 밀접한 관계 이진법을 사용한다면 버킷은 2개 알파벳 문자를 사용한다면 버킷은 26개 십진법을 사용한다면 버킷은 10개 기수 정렬 방법 첫 번째 패스 (1라운드) 정렬할 키의 가장 작은 자리수를 기준으로 분배 정렬 두 번째 패스 두 번째 작은 자리수를 기준으로 분배 정렬 키 값이 같은 경우 이전 정렬에서의 순서를 그대로 유지 키의 가장 큰 자리수까지 반복 수..

Algorithmday_4 정리 (2021.12.01 수요일) 이원 합병 정렬(Two-way Merge Sort) 정렬된 2개의 리스트를 혼합하여 완전히 정렬된 하나의 리스트로 합하는 정렬 방식 6, 9, 2, 12, 8, 34, 23, 33, 56, 17, 56, 32 (6, 9), (2, 12), (8, 34), (23, 33), (17, 56), (32, 56) (2, 6, 9, 12), (8, 23, 33, 34), (17, 36, 56, 56) (2, 6, 9, 9, 12, 23, 33, 34), (17, 36, 56, 56) {2, 6, 8, 9, 12, 17, 23, 32, 33, 34, 56, 56}

Algorithmday_4 정리 (2021.12.01 수요일) 퀵 정렬(Quick Sort) 분할 정복 정렬 방법 중 하나 전체 리스트를 2개의 부분 리스트로 분할하고 각각의 서브 리스트를 다시 퀵 정렬로 정렬 기준 값보다 큰 값들은 오른쪽으로, 작은 값들은 왼쪽으로 재 배열 정렬 방법 전체 리스트에서 한 원소를 기준 값(pivot)으로 선정 피벗을 기준으로 두 개의 서브 리스트로 분할 왼쪽 : 피벗보다 작은 값의 원소들로 구성 오른쪽 : 피벗보다 크거나 같은 값의 원소들로 구성 각각의 파티션(서브 리스트)에 대해 다시 퀵 정렬을 순환 적용 피벗 선정 및 파티션 분할 퀵 정렬 수행 순서 피벗(pivot) : 가장 왼쪽 숫자를 피벗으로 선정 두 개의 변수 : low와 high(이동) low는 왼쪽에 위치 ..

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삽입 모든 원소들이 정렬될 때 ..