jtj8412   2년 전

어떤 원리로 정렬하나요?

선택(Selection) 정렬처럼

for (int i = 0; i < N - 1; ++i)

  for (int j = i + 1; j < N; ++j)

이런 느낌으로 'i' 번째 데이터와 'j' 번째 데이터를 비교해서 정렬하는건가요?

wondy1128   2년 전



Complexity and implementations[edit]

The C++ standard requires that a call to sort performs O(N log N) comparisons when applied to a range of N elements.[4] In previous versions of C++, such as C++03, only average complexity was required to be O(N log N).[5] This was to allow the use of algorithms like (median-of-3) quicksort, which are fast in the average case, indeed significantly faster than other algorithms like heap sort with optimal worst-case complexity, and where the worst-case quadratic complexity rarely occurs.[6] The introduction of hybrid algorithms such as introsort allowed both fast average performance and optimal worst-case performance, and thus the complexity requirements were tightened in later standards.

Different implementations use different algorithms. The GNU Standard C++ library, for example, uses a 3-part hybrid sorting algorithm: introsort is performed first (introsort itself being a hybrid of quicksort and heap sort), to a maximum depth given by 2×log2 n, where n is the number of elements, followed by an insertion sort on the result.[7]

댓글을 작성하려면 로그인해야 합니다.