전체 글 (12) 썸네일형 리스트형 계수 정렬 (counting sort) 알아보기 이제 정렬 알고리즘 시리즈의 마지막에 다다른 것 같습니다. 제가 코딩테스트를 준비하거나 현업에서 활용하던 정렬 알고리즘의 종류는 포스팅에 올린 정렬 방법 정도면 충분했던 것 같습니다. 그 중에서 제일 낯설기도 했고 제일 활용도가 좋은 방법이었던 계수 정렬에 관해 알아보겠습니다. 계수 정렬이 활용도가 좋다고 표현한 이유는 우선 빠른 정렬 알고리즘이기 때문입니다. 계수 정렬은 O(n)의 시간복잡도를 갖습니다. 선형 시간이 걸리기 때문에 O(n^2) 방법이었던 버블, 삽입, 선택 정렬이나 O(nlogn) 방법이었던 퀵, 병합 정렬보다 훨씬 빠른 방법입니다. 데이터의 크기가 굉장히 큰 경우 강력한 힘을 발휘하는 방법입니다. 두번째로 계수 정렬은 꼭 자릿수를 기준으로 카운트를 할 필요가 없습니다. 다시 말해서 흔.. 버킷 정렬 (bucket sort) 알아보기 이번 포스팅도 정렬에 관한 내용입니다. 기왕 정렬에 관해 적는 것을 시작했으니 다 훑어보는게 좋겠다는 생각이 들었습니다. 사실 정렬은 방법이 워낙 다양합니다. 저 역시도 모르는 정렬 방법이 많죠. 그러나 기본적인 정렬 방법 몇 가지와 nlogn 방법 몇 가지, 그리고 버킷 정렬과 계수 정렬 정도 알고 있다면 현업이나 코딩 테스트에서는 전혀 문제되지 않는다고 생각합니다. 저 역시도 현재까지 알고 있는 정렬 방법으로 현업에서 잘 사용하고 있습니다. 제가 생각하는 중요 정렬 방법 중 한 가지인 버킷 정렬은 개념적으로는 이해하기 쉽습니다. 프로그래밍 문제 풀이에 익숙하지 않던 시절에는 버킷 정렬에 관한 설명을 보고 '읭?' 스러웠던 기억이 있습니다. 분명 설명대로 따라하면 정렬이 되는 것 같긴 한데 이것 자체로.. [c++] 퀵 정렬 (quick sort) 구현하기 이번 포스팅에서는 지난 포스팅에 이어 퀵 정렬에 관해 이야기해보려고 합니다. 지난번에는 퀵 정렬에 대한 개념과 정렬 과정을 글로 정리해봤다면 이번 포스팅에서는 실제 c++ 구현을 해보면서 설명하려고 합니다. 설명이 궁금한 분들께서는 지난 포스팅을 참고하시고 오면 더욱 도움이 될 것 같습니다. 먼저 c++ 전체 코드를 살펴보겠습니다. 줄 번호를 따라 각각의 동작을 설명하도록 하겠습니다. 기본적으로 한번 따라서 작성해보면서 코드를 분석하면 더욱 도움이 될 것으로 생각됩니다. 3: quickSort 함수부에서 2곳에 swap 코드가 필요합니다. 비슷한 동작을 수행하는 반복된 부분을 처리하기 위해 전처리문을 활용했습니다. auto를 쓰면 다양한 타입에서의 swap을 한번에 쓸 수 있기 때문에 유용합니다. 6: .. 이전 1 2 3 4 다음
