Recursion Hacks

Save this code from infinite recursion. The code should print something like this:

**********
*********
********
*******
******
*****
****
***
**
*
public void drawLine(int n) {
     if (n != 0) {
          for (int i = 1; i <= n; i++) {
               System.out.print("*");
               
          }
          System.out.println();
          drawLine(n - 1);
     }
}
drawLine(10);

**********
*********
********
*******
******
*****
****
***
**
*

Sorting Hack:

Write a insertion or selection sort program that sorts an ArrayList in decreasing order so that the largest country is at the beginning of the array (Create your own Country class with size). Use a Comparator.</p>

Bonus Hack:

Use heap sort to do the above

</div> </div> </div> 
public class Country implements Comparable<Country> {
    private int size;
    private int population;

    public Country(int size, int population) {
        this.size = size;
        this.population = population;
    }

    public int getSize() {
        return size;
    }

    public int getPopulation() {
        return population;
    }

    @Override
    public int compareTo(Country o) {
        return this.size - o.size;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj instanceof Country) {
            Country other = (Country) obj;
            return this.size == other.size && this.population == other.population;
        }
        return false;
    }

    @Override
    public String toString() {
        return "Country{" +
                "size=" + size +
                ", population=" + population +
                '}';
    }
}

public class SelectionSortBackwards {
    public void sort(ArrayList<Country> arr) {
        for (int i = 0; i < arr.size()-1; i++) {
            int max_idx = i;
            for (int j = i+1; j < arr.size(); j++) {
                if (arr.get(j).compareTo(arr.get(max_idx)) > 0)
                    max_idx = j;
            }
            Country temp = arr.get(max_idx);
            arr.set(max_idx, arr.get(i));
            arr.set(i, temp);
        }

        // for (int i = arr.length-1; i > 0; i--) {
        //     int max_idx = i;
        //     for (int j = i-1; j >= 0; j--) {
        //         if (arr[j].compareTo(arr[max_idx]) > 0)
        //             max_idx = j;
        //     }
        //     Country temp = arr[max_idx];
        //     arr[max_idx] = arr[i];
        //     arr[i] = temp;
        // }
    }
    public static void main() {
        SelectionSortBackwards ob = new SelectionSortBackwards();
        ArrayList<Country> arr = new ArrayList<Country>();
        arr.add(new Country(1, 1));
        arr.add(new Country(7, 7));
        arr.add(new Country(23, 23));
        arr.add(new Country(6, 6));
        arr.add(new Country(4, 4));
        arr.add(new Country(6, 6));
        arr.add(new Country(1, 1));

        ob.sort(arr);
        for (int i = 0; i < arr.size(); i++) {
            System.out.println(arr.get(i) + " ");
        }
    }
}

SelectionSortBackwards.main();

Country{size=23, population=23} 
Country{size=7, population=7} 
Country{size=6, population=6} 
Country{size=6, population=6} 
Country{size=4, population=4} 
Country{size=1, population=1} 
Country{size=1, population=1} 

// create a class with a heapSort() and heapify() method
public class HeapSort
{
    public void sort(ArrayList<Country> arr) {
        int n = arr.size();
  
        // Build heap (rearrange array)
        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(arr, n, i);
  
        // One by one extract an element from heap
        for (int i=n-1; i>=0; i--)
        {
            // Move current root to end
            Country temp = arr.get(0);
            arr.set(0, arr.get(i));
            arr.set(i, temp);
  
            // call max heapify on the reduced heap
            heapify(arr, i, 0);
        }
    }

    void heapify(ArrayList<Country> arr, int n, int i)
    {
        int largest = i;  // Initialize largest as root
        int l = 2*i + 1;  // left = 2*i + 1
        int r = 2*i + 2;  // right = 2*i + 2
  
        // If left child is larger than root
        if (l < n && arr.get(l).compareTo(arr.get(largest)) > 0)
            largest = l;
  
        // If right child is larger than largest so far
        if (r < n && arr.get(r).compareTo(arr.get(largest)) > 0)
            largest = r;
  
        // If largest is not root
        if (largest != i)
        {
            Country swap = arr.get(i);
            arr.set(i, arr.get(largest));
            arr.set(largest, swap);
  
            // Recursively heapify the affected sub-tree
            heapify(arr, n, largest);
        }
    }

    public static void main() {
        HeapSort ob = new HeapSort();
        ArrayList<Country> arr = new ArrayList<Country>();
        arr.add(new Country(1, 1));
        arr.add(new Country(7, 7));
        arr.add(new Country(23, 23));
        arr.add(new Country(6, 6));
        arr.add(new Country(4, 4));
        arr.add(new Country(6, 6));
        arr.add(new Country(1, 1));

        ob.sort(arr);
        for (int i = 0; i < arr.size(); i++) {
            System.out.println(arr.get(i) + " ");
        }
    }

}

HeapSort.main()

Country{size=1, population=1} 
Country{size=1, population=1} 
Country{size=4, population=4} 
Country{size=6, population=6} 
Country{size=6, population=6} 
Country{size=7, population=7} 
Country{size=23, population=23}

Arraylist Hacks:

Choose two of these options to do.

  • Test if two arraylists contain the same elements in reverse order
  • Overwrite all the elements in an arraylist with the alphabet (✅)
  • Remove every other element from an arraylist (✅)
// overwrite elements in arraylist with alphabet
ArrayList<String> alphabet = new ArrayList<String>();
for (int i = 0; i < 26; i++) {
    char letter = (char)(97 + Math.random() * 26);
    alphabet.add(String.valueOf(letter));
}
System.out.println("original elemens: " + alphabet);

for (int i = 0; i < 26; i++) {
    char letter = (char)(97 + i);
    alphabet.set(i, String.valueOf(letter));
}

System.out.println(alphabet);

// remove every other element
for (int i = 0; i < alphabet.size(); i++) {
    if (i % 2 == 0) {
        alphabet.remove(i);
    }
}
System.out.println("remove every other: " + alphabet);

original elemens: [m, w, a, c, o, v, t, e, z, o, z, t, e, u, k, i, u, z, k, u, q, p, w, w, g, s]
[a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z]
remove every other: [b, c, e, f, h, i, k, l, n, o, q, r, t, u, w, x, z]
</div>