What is wrong with this Haskell quicksort -

-

taking functional programming plunge , trying teach myself haskell online materials. pretty basic, cannot figure why implementation of quicksort not terminate input list length longer 1.

here's code:

quicksort :: (ord ord) => [ord] -> [ord quicksort [] = [] quicksort [element] = [element] quicksort array = quicksort right_half ++ [pivot] ++ quicksort left_half   pivot = head array         right_half = [element | element <- array, element <= pivot]         left_half = [element | element <- array, element > pivot]

i reading online textbook decided try quicksort myself before reading given solution. after failing, went , understood given answer, still cannot see why mine wrong. haskell newbie appreciated!

notice sort of algorithm not going yield quick sort. time complexity of (++) destroy you, if nothing else.

as problem, taking elements <= pivot.. (absolutely) include pivot. if have list [2,1] sort right half call quicksort [2,1], creating loop.

a better solution pattern match, using like:

quicksort (pivot:array) = quicksort righthalf ++ [pivot] ++ quicksort lefthalf

edit: see related why minimalist, example haskell quicksort not "true" quicksort?


Comments

Post a Comment

Popular posts from this blog

php - Admin SDK -- get information about the group -

-
please, help. https://www.googleapis.com/admin/directory/v1/groups/106274944935548788283 sending request obtain information group id 1062 ... here link method in google https://developers.google.com/admin-sdk/directory/v1/guides/manage-groups#get_group in response error - 401 unauthorized. oauth authenticate via user has received rights necessary request, included in console admin sdk. authorization successful, there token. not can not understand. if not hard - response. requested information: file_get_contents("https://www.googleapis.com/admin/directory/v1/groups/1062749‌​44935548788283?key=aizasybruhiomdf9nlx9lx3imxwesqmcrnhh4l4"); id group - "106274944935548788283" key applications in case - "aizasybruhiomdf9nlx9lx3imxwesqmcrnhh4l4" error: failed open stream: http request failed! http/1.0 401 unauthorized
Read more

Python Error - TypeError: input expected at most 1 arguments, got 3 -

-
can explain why can not use your_name in goal variable? my_name = "bryson" my_age = 29 your_name = input ("what name? ") your_age = input ("what age? ") print ("my name is", my_name,", , am", my_age, "years old.") print ("your name is", your_name,", , are", your_age,".") print("thank buying book,", your_name,"!") goal = input ("what favorite part of book,", your_name, "?") print("awesome!") the error is: goal = input ("what favorite part of book,", your_name, "?") typeerror: input expected @ 1 arguments, got 3 you got error because in fact gave 3 arguments input function when expecting 1 (namely, string prompt). in input ("what favorite part of book,", your_name, "?") ---------------------------------------- , ---------, --- the underlined parts comma-separated arguments: st...
Read more

python - Pygame screen.blit not working -

-
in program creating in python/pygame, screen.blit not working. in other programs have made, screen.blit works. error: traceback (most recent call last): file "c:...\main.py", line 46, in <module> screen.blit(sight.image, sight.rect) attributeerror: 'int' object has no attribute 'blit' the error in question caused screen variable being allocated integer instead of pygame.surface() object.perhaps accidentally rewrote variable somewhere? from can make of doing, seems stating position of blit full rect instead of coordinate. when do: screen.blit(sight.image,sight.rect) what program seeing is: screen.blit(sight.image,(sight.rect.x,sight.rect.y,sight.rect.width,sight.rect.height)) i assuming don't intend this. remember rect object consists of position, width , height. to correct code, put (sight.rect.x,sight.rect.y) location goes instead this: screen.blit(sight.image,(sight.rect.x,sight.rect.y)) the .x , .y corres...
Read more