Skip to content

Bug Report for quickSort #4394

@JichiGe

Description

@JichiGe

Bug Report for https://neetcode.io/problems/quickSort

Issue Summary:
The test case appears to expect a stable sort result (i.e., elements with equal keys retain their original relative order), but Quick Sort is inherently unstable. My implementation is logically correct and correctly sorts the list based on the key values. However, it fails the test cases solely because the output order of elements with the same key differs from the expected (due to Quick Sort’s instability).

Steps to Reproduce:

Implement Quick Sort as instructed (code sample below).

Sort a list of Pair objects where two or more pairs share the same key.

Observe that the test fails even though the keys are sorted correctly—only the relative order of same-key pairs differs.

Example Implementation:

python
复制
编辑

Definition for a pair.

class Pair:

def init(self, key: int, value: str):

self.key = key

self.value = value

class Solution:
def quickSort(self, pairs: List[Pair]) -> List[Pair]:
def quick_sort_helper(s, e, pair_list):
if e <= s:
return
l = s
pivot = pairs[e]
for r in range(s, e):
if pairs[r].key <= pivot.key:
pairs[l], pairs[r] = pairs[r], pairs[l]
l += 1
pairs[l], pairs[e] = pairs[e], pairs[l]
quick_sort_helper(s, l - 1, pair_list)
quick_sort_helper(l + 1, e, pair_list)

    quick_sort_helper(0, len(pairs) - 1, pairs)
    return pairs

Suggestion:
If the platform intends to test value stability, it should either:

Specify that a stable sort is required (and disallow Quick Sort), or

Allow logically correct results even if the relative order of same-key elements differs.

Thanks for providing this great platform! Please let me know if clarification is needed.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions