Search code examples
sortingschemer5rs

Sorting list of lists by their first element in scheme


I'm working on sorting a list of lists by their first element for example
(sort (list '(2 1 6 7) '(4 3 1 2 4 5) '(1 1))))

expected output => ('(1 1) '(2 1 6 7) '(4 3 1 2 4 5))

The algorithm I used is bubble sort. And I modified it to deal with lists. However, the code doesn't compile. The error is

mcar: contract violation
  expected: mpair?
  given: 4

Can someone correct my code and explain it. Thank you

 (define (bubble L)
        (if (null? (cdr L))   
            L    
            (if (< (car (car L)) (car (cadr L)))   
                (list (car L)
                      (bubble (car (cdr L))))   
                (list (cadr L)
                      (bubble (cons (car (car L)) (car (cddr L))))))))

    (define (bubble-sort N L)    
        (cond ((= N 1) (bubble L))   
              (else
               (bubble-sort (- N 1) (bubble L)))))

    (define (bubble-set-up L) 
        (bubble-sort (length L) L))


    (define t3 (list '(2 1 6 7) '(4 3 1 2 4 5) '(1 2 3) '(1 1)))
    (bubble-set-up t3)

Solution

  • I have fixed a few mistakes. There is at least one mistake left. Consider the case where L only contains one element.

    #lang r5rs
    
    (define (bubble L)
      (if (null? (cdr L))
          L    
          (if (< (car (car L)) (car (cadr L)))   
              (cons (car L)
                    (bubble (cdr L)))
              (cons (cadr L)
                    (bubble (cons (car L) (cddr L)))))))
    
    (define (bubble-sort N L)    
      (cond ((= N 1) (bubble L))   
            (else
             (bubble-sort (- N 1) (bubble L)))))
    
    (define (bubble-set-up L) 
      (bubble-sort (length L) L))
    
    
    (define t3 (list '(2 1 6 7) '(4 3 1 2 4 5) '(1 2 3) '(1 1)))
    (display (bubble-set-up t3))
    (newline)