الگوریتمهای مرتبسازی
Sorting Algorithms
مباحث الگوریتمهای مرتبسازی.
طراحی الگوریتم کنکور ارشد علوم کامپیوتر
کارتها · 10
Insertion sort is adaptive: it runs in Θ(n) on nearly-sorted input where merge/quicksort still pay Θ(nlog n) .
Merging k sorted lists with n total elements costs Θ(nlog k) , which is O(n) only when k is constant.
Picking the exact median as pivot gives a perfectly balanced split, yielding T(n)=2T(n/2)+f(n)+Θ(n)=O((n+f(n))log n) .
On an array of size n, Quicksort's comparison count is a random quantity ranging from nlog n (best) to n(n-1)/2 (worst), determined entirely by how each pivot splits its subarray.
Bubble sort (and any sort that only swaps adjacent out-of-order elements) performs exactly as many swaps as there are inversions in the input — so you can count swaps without simulating the passes.
Bubble, selection, and insertion sort all run in Theta(n^2) on a random array; what distinguishes them is whether their cost depends on the input — selection sort is always Theta(n^2), bubble and insertion can drop to Theta(n) on sorted data.
Sort an array of three distinct key values into low-mid-high order in a single linear, in-place pass using three pointers.
Model one run of merge sort as a recursion tree with n leaves: there are n-1 internal (splitting) nodes, so merge is called n-1 times, total mergesort invocations are 2n-1, and the worst-case element comparisons are at most nceil(log2 n) - 2^ceil(log2 n) + 1. Don't confuse 'total calls' with 'recursive calls'.
Stopping merge-sort recursion at blocks of a constant size k and finishing each block with insertion sort keeps the running time at Θ(nlog n) ; the cutoff only shaves a constant factor. The bound changes only when k is allowed to grow with n .
LSD radix sort is correct only if the per-digit auxiliary sort is stable, so heapsort and quicksort cannot be plugged in while stable counting sort can.