quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) =
let smallerOrEqual = [a | a <- xs, a <= x]
larger = [a | a <- xs, a > x]
in quicksort smallerOrEqual ++ [x] ++ larger
main = do
let a = [ 5, 1, 9, 4, 6, 7, 3]
print $ quicksort a
in Haskell quick sort, why the first let uses <= instead of <? I think <= will duplicate that x many times. Why not?
I think <= will duplicate that x many times
No, it will not. Let us understand what exactly is happening here. You are basically partitioning your list into three parts.
List of numbers smaller than or equal to the pivot element (excluding the first element, since that is the pivot element)
The pivot element itself (the first element in the list)
List of numbers greater than the pivot element
So, in your case, the partitioned list becomes like this
[1, 4, 3] ++ [5] ++ [9, 6, 7]
Consider a case like this, quicksort [5, 1, 5, 9, 8, 5, 3, 6, 4]. Then, your program will partition it into something like this
smallerOrEqual ++ [x] ++ larger
Since smallerOrEqual and larger work with xs, which doesn't have the x, there is no duplication as such. Now, the partitioned list, after the filtering, becomes
[1, 5, 5, 3, 4] ++ [5] ++ [9, 8, 6]
See? There is no duplication, just partitioning.
Note: Your program has a serious bug. Check this line
quicksort smallerOrEqual ++ [x] ++ larger
It basically works like this
(quicksort smallerOrEqual) ++ [x] ++ larger
So, the larger list is never sorted. You recursively have to sort both the smaller list and the greater list and finally merge them in to one. So, it should have been
(quicksort smallerOrEqual) ++ [x] ++ (quicksort larger)
which can be written without the brackets like this
quicksort smallerOrEqual ++ [x] ++ quicksort larger
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加