Problem: Design a function that receives a sequence of numbers and returns a boolean
indicating if the sequence is sorted (in ascending order) or not. Write your answers
in the language of your choice. 

C211 Design Recipe

; 1. data representation
; A ManyNumber is one of:
;   -- empty

;   -- (cons Number ManyNumber)

; 2. give some examples
(define e0 empty)
(define e1 (cons 5 e0))
(define e2 (cons 3 e1))
(define e3 (cons 4 e2))
(define e4 (cons 1 e3))

; 3. name, signature, purpose statement
; sorted? : ManyNumber -> Boolean
; determines if the input is sorted ascending order or not

; 4. given e0 expected true
;    given e1 expected true
;    given e2 expected true
;    given e3 expected false 
;    given (list 1 4 2 3 6 5) expected false 
;    given (list 3 6 7 9) expected true 

; 5. choose a template
; (define (sorted? lon)
;   (cond ((empty? lon) ...)
;         (else ( ... (first lon) ... (sorted? (rest lon)) ... ))))

; 6. flesh out the template
(define (sorted? lon)
  (cond ((empty? lon) true)
        ((empty? (rest lon)) true)
        ((<= (first lon) (first (rest lon))) (sorted? (rest lon)))
        (else false)))

(check-expect (sorted? e0) true)
(check-expect (sorted? e1) true)
(check-expect (sorted? e2) true)
(check-expect (sorted? e3) false)
(check-expect (sorted? (list 3 6 7 9)) true)
(check-expect (sorted? (list 1 4 2 3 6 5)) false)

Can we solve this in any other way? 

Yes. Accumulator passing style. That's similar to using loops. 

How do we write sorted? in Java:

import java.util.Arrays; 

public class Thursday {
  public static void main(String[] args) {
    int[] a = { 5, 2, 3, 1, 4 };  // Troy's idea. 
    System.out.println( Arrays.toString ( a ) ); 
    System.out.println( Arrays.toString ( args ) ); // Joseph's idea 
  }
}

This runs as follows: 

Welcome to DrJava.  Working directory is C:\Users\dgerman\Desktop
> run Thursday
[5, 2, 3, 1, 4]
[]
> run Thursday 5 2 3 1 4
[5, 2, 3, 1, 4]
[5, 2, 3, 1, 4]
> run Thursday 1 2 3 5 6
[5, 2, 3, 1, 4]
[1, 2, 3, 5, 6]
> 

Let's design sorted? 

import java.util.Arrays; 

public class Thursday {
  public static void main(String[] args) {
    int[] a = { 5, 2, 3, 1, 4 };  // Troy's idea. 
    System.out.println( Arrays.toString ( a ) ); 
    System.out.println( Thursday.sorted( a ) ); 
    System.out.println( Thursday.sorted( new int[] { 1, 2, 5, 7} ) ); 
    
  }
  public static boolean sorted(int[] a) {
    if (a.length <= 1) 
      return true; 
    for (int i = 0; i < a.length-1; i = i + 1) {
      if (a[i] > a[i+1]) 
        return false;
    }
    return true; 
  }
}

That looks good. 

Take a look at our discussion from yesterday

http://silo.cs.indiana.edu:8346/c212/fall2015/0923a.phps

The main goal for today is to set you up for Homework 04. 

Let's design sort. 


              [0 0 0 0 0 0 0 ]            [4 3 2 1 6 5 1]

              [1 0 0 0 0 0 0 ]            [4 3 2 1 6 5]

              [1 1 0 0 0 0 0 ]            [4 3 2 6 5]

              [1 1 2 0 0 0 0 ]            [4 3 6 5]

I believe this works. 

We need to write the procedure that finds the minimum and eliminates it from an array. 

Here's two tools we need to design before we can use Troy's method

import java.util.Arrays; 

public class Thursday {
  public static void main(String[] args) {
    int[] a = { 5, 2, 3, 1, 4 };  // Troy's idea. 
    System.out.println( Arrays.toString ( a ) ); 
    System.out.println( Thursday.sorted( a ) ); 
    System.out.println( Thursday.sorted( new int[] { 1, 2, 5, 7} ) ); 
    
  }
  public static int[] troy(int[] a) {
    int min = Thursday.min(a); 
    int[] result = new int[a.length - 1]; 
    // go through a skipping min once and putting elements in result 
    return result; 
  }
  public static int min(int[] a) {
    // assume that a.length > 0 
    int min = a[0]; 
    for (int e : a)
      if (e < min)
        min = e;
    return min; 
  }
  public static boolean sorted(int[] a) {
    if (a.length <= 1) 
      return true; 
    for (int i = 0; i < a.length-1; i = i + 1) {
      if (a[i] > a[i+1]) 
        return false;
    }
    return true; 
  }
}

Need to finish in lab. 

--