Member Avatar for tubby123

can u give me an example array of the best case of quick sort?
I do understand that the best case of quick sort is when the elements are already in the pivot place., and that the complexity is O(n logn), but i m just not able to come up with a large array, that fits this condition perfectly.

  • 3 Contributors
  • 2 Replies
  • 238 Views
  • 12 Hours Discussion Span
  • Latest Post Latest Post by mrnutty

Dani AI

Generated

Short clarification: “Best case” for quicksort depends on how the pivot is chosen and which partition routine is used — exactly as pointed out. If the implementation explicitly detects already-sorted subarrays it can short-circuit to linear work; otherwise the usual “best” notion is that every partition splits the current subarray as evenly as possible (giving Θ(n log n)). ’s hint about working from the medians is exactly the right construction idea.

Three concrete, small examples (values 1..7) that produce perfectly balanced splits for common deterministic pivot rules:

  • Pivot = middle index (pick mid element): sorted order is already best-case:
    [1, 2, 3, 4, 5, 6, 7]

  • Pivot = first element (common with Hoare-style partition): use the preorder of the balanced median tree:
    [4, 2, 1, 3, 6, 5, 7]

  • Pivot = last element (common with Lomuto-style partition): use the postorder of the balanced median tree:
    [1, 3, 2, 5, 7, 6, 4]

To generate these for any size without handcrafting, build the balanced-median ordering of the sorted keys. Preorder places each subtree’s median at the front (good when pivot = first). Postorder places medians at the end (good when pivot = last). In-order is the sorted list (good when pivot = mid). Example pseudocode:

function balanced_preorder(sorted):
    if sorted empty: return []
    mid = len(sorted) // 2
    return [sorted[mid]] + balanced_preorder(sorted[:mid]) + balanced_preorder(sorted[mid+1:])

function balanced_postorder(sorted):
    if sorted empty: return []
    mid = len(sorted) // 2
    return balanced_postorder(sorted[:mid]) + balanced_postorder(sorted[mid+1:]) + [sorted[mid]]

Notes and cautions: confirm the exact pivot-selection and partition implementation before using a test array (Hoare vs Lomuto behave differently). Duplicates and equality-handling can break the neat halves. If the implementation uses randomized pivots, a guaranteed best-case input cannot be produced unless the RNG is controlled.

Recommended Answers

All 2 Replies

Member Avatar for Narue

The best cast for quicksort is an already sorted array when the implementation checks for an already sorted subset. In such a case, no partitioning takes place and no recursive calls are made, which results in linear complexity:

function quicksort(a, first, last)
    if is_sorted(a, first, last) then
        return
    end if

    pivot := partition(a, first, last)

    quicksort(a, first, pivot - 1)
    quicksort(a, pivot + 1, last)
end function

Assuming the original quicksort algorithm with no improvements, the best case is an even partitioning in all steps, which is O(N log N).

i m just not able to come up with a large array, that fits this condition perfectly

The dependency is your partitioning scheme, so to create an array that fits the best case, you need both a deterministic partitioning scheme (ie. random pivots will need to be mocked) and an array that gets partitioned perfectly each time. Without knowing your partitioning algorithm, I can't really offer much more advice than that.

commented: And that about covers it... +11
Member Avatar for mrnutty

Hint: Use your pivot algorithm to work from the bottom up instead of top down

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.