Sort 검색 결과

해당 글 7건
sort 함수의 custom compare 함수를 구현할 때 어떤 점도 조심해야 할까요?

요새 졸리네요. 코딩 테스트를 개최하면서 여러 코드를 보았는데요. 2회 코테가 의외로 1번부터 막히는 경우가 많았는데요. 아마도 정렬과 비교 함수의 메커니즘에 대해서 익숙하지 않아서 그러셨을 겁니다. strict weak ordering은 이펙티브 자바에서도 언급하는 주제이니 다른 조심해야 할 점을 언급해 볼게요. 이 질문과 이 질문은 제가 오늘 쓰려는 글과 관련이 깊습니다. 결론부터 말하자면, 정렬 문제에서 전처리 할 부분을 미리 전처리 하고 오면 로직이 단순해 집니다. 그러면 실수할 여지도 적습니다. 그리고 크기가 n인 배열을 정렬할 때 키 2개를 비교하는 compare 함수는 O(nlogn)번 호출됩니다. 이 글에서는 compare 함수가 어떻게 동작하나요? 에 대해서는 다루지 않습니다. 어떻게 정..
자료알고/알고리즘 2021. 11. 10. 00:42
linux sort 명령어를 알아봅시다.

안녕하세요. 이번 시간에는 리눅스 sort 명령어를 배워보면서 정렬에 대해서 간단하게 이해해 보겠습니다. man 페이지에서 언급하고 있는 로케일에 관한 warning은 이 글에서 다루지 않겠습니다. 몇 번 삽질을 해 봐야 아 로케일이 이런 거라는 것이 와 닿지 않을까 싶어요. 혹시나, 보완할 부분이나 잘못된 부분이 있다면 댓글로 남겨주시면 감사히 받겠습니다. 1.in의 1번째 줄 부터 10번째 줄 까지는 이런 내용들이 있어요. 요구 사항이 하나 들어왔는데요. 공백을 기준으로 필드를 나눌 때, 1번째 필드 오름차순으로 정렬하려고 해요. 단, 필드에는 수가 있으니까, 수가 증가하는 순서대로 정렬이 되어야 합니다. 옵션을 찾아 보니, KEYDEF라는 것이 보여요. F[.C][OPTS][,F[.C][OPTS]]..
OS/리눅스 2021. 9. 28. 02:49
파이썬 문자열 다중정렬 : sort가 stable 하다는 것을 이용합시다.

저번 시간에 tuple을 이용해서 다중 정렬을 손쉽게 하는 법을 배웠습니다. 특히 정수는 오름차순 반대인 내림차순으로 비교하기 위해서, 앞에 -만 붙이면 매우 간단하게 비교할 수 있어요. 그런데 문자열은 그게 되지 않습니다. 문제 상황을 보면서 어떻게 구현하면 좋을지 천천히 생각해 보도록 합시다. 개인적으로 아래 두 개의 글을 먼저 보고 오시는 게 좋아 보입니다. [관련글] tuple로 정렬 기준을 떨어트리는 방법을 알아봅시다. 안정 정렬에 대해서 알아봅시다. solution 함수를 구현해야 하는데요. list에는 튜플이 들어 있어요. 튜플의 1번째, 2번째 요소는 소문자로만 이루어진 문자열이 들어 있어요. 1차 정렬 기준은, 1번째 요소를 사전순 내림차순으로 돌립니다. 만약에, 1번째 요소가 같은 문자..
코딩/파이선 2021. 9. 24. 23:39
java의 arrays.sort 메서드는 어떤 정렬을 사용할까요?

java의 Array.sort는 어떤 정렬 알고리즘을 쓸까요? primitive type을 정렬하는 경우와, 그렇지 않은 경우에 쓰는 알고리즘이 다릅니다. 어떻게 다른지 간단하게 보도록 하겠습니다. java8 기준으로 작성되었음을 참고하시면 됩니다. 먼저 primitive type을 정렬할 때 어떻게 동작할까요? Array.class 안으로 들어가 보겠습니다. int형을 저장해 놓은 배열을 정렬하려는 경우보시면, rangeCheck를 하고, DualPivotQuickSort로 들어간다는 것을 알 수 있습니다. short형은 어떨까요? 마찬가지입니다. DualPivotQuickSort 안으로 들어가 보겠습니다. 먼저, int형 배열을 정렬하는 경우입니다. QuickSort_ThreasHold보다 작으면 s..
레퍼런스/분석 2020. 6. 28. 23:58
인트로 정렬 : c++의 sort는 왜 최악의 경우에도 빠르게 동작하는가?

C++의 sort는 어떻게 O(nlogn)의 복잡도가 보장될 수 있을까요? 저번에 compare 함수가 항상 True를 리턴할 때에 어떤 일이 일어나는가? 편에서 이 함수를 뜯은 적이 있었습니다. 그 기억을 되살려서 보도록 하겠습니다. Quick sort는 pivot을 어떻게 선택하느냐가 중요하다고 했어요. 저번에 median 값을 가지고 pivot값을 생성한다는 것을 알 수 있는데요. 이 방법을 저격하는 데이터가 있다는 것이 알려져 있어요. 그러면 이 방법을 어떻게 해결할까요? nth_element에도 적용되는 기법 중 하나인데요. 호출 깊이의 제한을 둡니다. first와 last가 다른 경우, __introsort_loop를 호출합니다. 그런데, 이것은, 3번째 인자에 이상한 __lg(__last -..
레퍼런스/분석 2019. 12. 7. 21:25