CODEWITHSUNDEEP
listsortinghaskell
baron aron
baron aron

Reputation: 169

Implementing a sorting method similar to bubble sort

I am trying to figure out how to implement a sorting method that is like bubble sort but differs in some ways.

The pseudo code would be like this:

  1. Get list and take first element in the list
  2. if the element next to it is smaller then swap the elements
  3. else mark the element as moved and repeat until all elements are marked

Here is how I thought about implementing this problem:

sortElement [] elm= []
sortElement [x] elm= [x]
sortElement lis@(x:y:xs) elm = 
--first if is to find the element in the list that i want to move
if elm /=x  
then x:sortElement(y:xs) elm 
else if x > y then y:sortElement(x:xs) elm 
else lis

stackBubble lis = stackBubble' lis lis

stackBubble' [] [] = [] 
stackBubble' [x] [] = [x]
stackBubble' [] [x] = []
stackBubble' lis@(x:xs) lis1@(x1:xs1) = do 

sortElement(stackBubble' lis xs1) x1

The error I am getting is

Non-exhaustive patterns in function stackBubble'

If I do like suggested elsewhere: 

sortElement(x:stackBubble' xs xs1) x1

I get a fully sorted list after one iteration when I would like to get something like this:

[4,2,7,1] => iterating 4 [2,4,7,1], after iterating all the elements [2,4,1,7].

Upvotes: 1

Views: 322

Answers (3)

tazjin
tazjin

Reputation: 673

The easiest way to solve this would probably be using guards and simple recursion, for example:

bubble :: Ord a => [a] -> [a]
bubble (x:y:xs) | x > y = y : bubble (x : xs)
                | otherwise = x : bubble (y : xs)
bubble x = x

Have you covered guards yet? Just in case you haven't, I'll explain in short. The syntax for a guard is

| (expression that evaluates to Bool) = code

Just like in pattern matching Haskell will check the guards from top to bottom and execute the first one that returns true. otherwise is the "fall-through case" which is just defined as True.

So going through the code line by line:

bubble (x:y:xs) | x > y = y : bubble (x : xs)

We separate the list into x:y:xs and run the first guard which checks if y is smaller than x, if it is y is appended to the result list we're building and bubble is called again with (x : xs).

                | otherwise = x : bubble (y : xs)

Second guard always returns True, keeps x at it's position and calls bubble again with the list still in the same order.
The last line just returns the last element, or in case you call the function with an empty list, an empty list.

Assuming the example list [4,2,5,1] the execution would work like this:

1: 2 is smaller than 4 -> 2 : bubble [4,5,1]
2: 5 is not smaller than 4 -> 2 : 4 : bubble [5,1]
3: 1 is smaller than 5 -> 2 : 4 : 1 : bubble [5]
4: end of list -> 2 : 4 : 1 : 5 -> [2,4,1,5]

This implementation has no explicit "marking" an element as moved but that's not required.

Upvotes: 2

Greg E.
Greg E.

Reputation: 2742

I began to code a corrected version, but while I was doing that the question was answered. I'll include it here anyway for the sake of demonstration:

bubbleSort l =
  bSort l []
  where bSort []        acc = acc
        bSort [x]       acc = acc ++ [x]
        bSort (x:y:xys) acc
          | x > y     = bSort (acc ++ (y:x:xys)) []
          | otherwise = bSort (y:xys) (acc ++ [x])

Note that this is probably grossly inefficient even by the standards of bubble sort because of all the list concatenation (it would most likely be preferable to append to the head of the accumulator list and then reverse when necessary). This implementation is extremely naive, but reasonably concise and perhaps instructive, though more because of the blatancy of its crudeness than any positive virtue.

Upvotes: 2

Louis Wasserman
Louis Wasserman

Reputation: 198391

You're getting the error because stackBubble' doesn't specify the result when one argument is empty and the other has more than one element.

Upvotes: 2

Related Questions