반응형 정렬 알고리즘6 힙 정렬, 도수 정렬 Preface 오늘 배운 힙 정렬과 도수 정렬을 끝으로 드디어 정렬 알고리즘을 모두 마쳤다. 두 방법 모두 글로 쓰여진 설명은 복잡했지만, 실제 코드는 생각보다 간단하여 쉽게 작성할 수 있었다. 다만 힙 정렬은 정렬 과정마다 배열을 힙으로 만들어야 하므로 불필요한 계산이 많음에도 불구하고 사용되는 이유가 무엇인지 이해할 수 없었는데, 여러 블로그를 찾아본 결과 힙 정렬은 전체 배열을 정리하는 것이 아니라 가장 큰 값 몇 개만을 필요로 할 때 사용한다고 한다. 요즘 들어 공부를 할 때마다 머리를 복잡하게 하는 한 가지 걱정이 있다. 책에 쓰여진 코드를 천천히 분석하며 계산해보면 분명 이해는 할 수 있지만, 막상 나에게 동일한 문제가 주여졌을 때 내가 해당 코드를 작성할 수 있을 거란 확신이 들지 않는다는 .. 2022. 1. 10. 병합 정렬 Preface 오늘은 병합 정렬을 공부했는데, 어제 배운 퀵 정렬과 크게 다른 점이 없는 것 같다. 퀵 정렬은 배열을 1개의 원소만이 남을 때 까지 두 그룹으로 나누는 작업을 반복하는데, 병합 정렬 역시 배열을 마지막 원소까지 나눈 후 오름차순으로 병합하는 작업을 반복한다. 한 가지 차이점이 있다면 퀵 정렬은 피벗을 중심으로 배열을 나누지만, 병합 정렬은 무작위로 그룹을 반으로 나눈다는 것이다. 나는 나누어진 원소들을 병합할 때마다 비교하여 정렬하는 병합 정렬보단 한 번 피벗을 설정한 후 나누면서 정렬을 수행하는 퀵 정렬이 훨씬 효율적이라고 생각한다. 마지막으로 본문의 첫 번 째 코드에서 a, b 배열의 남은 원소들을 c에 복사할 때 남은 원소들 중 다른 배열의 마지막 원소보다 작은 배열이 있을 경우 정.. 2022. 1. 9. 퀵 정렬 Preface 오늘은 퀵 정렬을 공부했다. 일반적인 퀵 정렬에서부터 스택을 사용한 비재귀적 정렬, 특정한 규칙을 적용한 퀵 정렬까지 다양한 방식으로 퀵 정렬을 구현해봤다. 한 번 공부할 때 모든 것을 완벽히 이해할 정도는 아니어도 다시 봤을 때 배웠던 것들을 금방 떠올릴 수 있을 정도로 공부했던 탓인지 3개월 전 업로드했던 스택 관련 코드들은 큰 어려움 없이 사용할 수 있었다. 그러나 배열의 맨 앞, 중간, 맨 끝 원소의 중앙값을 정렬한 후 원소의 수가 9개 미만일 땐 단순 선택 정렬, 10개 이상일 땐 퀵 정렬을 사용하여 결과를 출력하는 코드는 생각할 것도 너무 많고 이것 저것 계산해볼 값들도 다양해서 머리가 너무 복잡했다. 앞으로는 직접 계산하지 않고 종단점을 설정한 후 디버깅을 실행하여 계산 과정을.. 2022. 1. 8. 셸 정렬 Preface 오늘은 다음날 공부할 시간이 없을 것 같아 한 파트를 추가로 업로드한다. 이번 파트에선 셸 정렬에 대해 공부했다. 불과 몇 시간 전 단순 삽입 정렬을 직접 계산할 땐 계산할 부분이 너무 많아서 복잡하게 느껴진다는 생각을 했었는데, 셸 정렬을 사용하여 계산을 하자 확실히 원소들을 정렬하기 쉬워졌다는 것을 느낄 수 있었다. 또한, 셸 정렬의 앞 부분을 읽어보며 아무리 원소들을 그룹으로 나누어 정렬한다고 한들 이들이 순서 없이 다시 합쳐지면 결국 단순 삽입 정렬과 동일해질 것 같다는 생각이 들어 직접 두 가지 방법으로 계산을 해보기도 했는데, 뒷 부분에 이러한 문제점을 완화시킬 수 있는 수열을 사용한 셸 정렬이 소개되어 있어 셸 정렬의 효율성을 인정할 수 있었다. 처음 정렬 알고리즘을 공부할 땐.. 2022. 1. 6. 단순 선택 정렬, 단순 삽입 정렬 Preface 오늘은 지난 포스팅에 이어 정렬 알고리즘의 종류 중 하나인 단순 선택 정렬과 단순 삽입 정렬, 이진 삽입 정렬을 공부했다. 단순 선택 정렬은 내가 예상했던 방식으로 코드를 작성하여 큰 어려움 없이 이해할 수 있었지만, 단순 삽입 정렬은 그렇지 않았다. 어떠한 방식으로 정렬이 진행되는 것인지는 금방 이해할 수 있었지만, 이 내용을 코드화하자 생각보다 복잡하여 코드를 한 줄 한 줄 분석한 후 직접 노트에 적어 계산해 본 후에야 코드의 작동 방식을 알 수 있었다. 이진 삽입 정렬도 마찬가지이다. 이진 검색을 하는 부분에서 검색 범위의 맨 끝 원소 인덱스를 i가 아닌 i - 1로 설정한 이유부터 시작하여 j의 값을 굳이 범위로 설정하는 이유 등 곧바로 이해되지 않는 부분들이 있어 한 시간 이상을 .. 2022. 1. 5. 정렬 알고리즘, 버블 정렬 Preface 이번 장에선 정렬 알고리즘이란 무엇인지에 관한 내용과 그 종류 중 하나인 버블 정렬 및 버블 정렬에 약간의 변화를 준 셰이커 정렬을 공부했다. 코드를 작성할 땐 아무 생각 없이 책에 나온 방식대로 진행하게 되지만, 해당 코드를 완성하면 기존의 코드에 능률성을 더한 새로운 코드 작성을 요구한다. 이전부터 코드를 작성할 때 어떻게 해야 더욱 효율적인 코드를 작성할 수 있을지를 고민하자고 생각은 하지만, 막상 공부를 하다 보면 그게 마음대로 되지 않는다. 내일부턴 책에 있는 코드를 그대로 따라 작성하기 전에 해당 문제를 해결할 방법을 미리 고민해 본 후 책과 비교하며 코드를 짤 생각이다. 또, 알고리즘 공부를 시작한 뒤로 진도를 나가는 데 시간이 너무 오래 걸리는데, 내 공부 방식이 맞는 것인지.. 2022. 1. 2. 이전 1 다음
