Algo-Rhythmic Code Prep!

Quick Sort!

This Java code implements the Quick Sort algorithm to sort a list of objects.

1. House Class: This class represents a house object with two attributes: price and id. It implements the Comparable interface, which allows instances of House to be compared to each other. The compareTo method compares two houses based on their prices.

2. QuickSort Class: This class defines the Quick Sort algorithm. It’s a generic class, allowing it to sort any type of object that implements the Comparable interface.

   • quickSort method: This is the main sorting method. It takes three parameters: the list to be sorted, the start index of the sublist, and the end index of the sublist. It recursively sorts the sublist using the partition method.

   • partition method: This method partitions the sublist into two parts: elements smaller than the pivot and elements greater than or equal to the pivot. It selects the pivot element (in this case, the last element of the sublist), then rearranges the elements so that all elements smaller than the pivot come before it, and all elements greater than or equal to it come after it. It returns the index of the pivot after partitioning.

3. Main Method:

   • It creates four House objects with different prices.
   • It creates a list of House objects and adds the four houses to it.
   • It prints the original list.
   • It creates an instance of QuickSort.
   • It measures the time taken to sort the list using Quick Sort.
   • It prints the sorted list and the time taken.

Finally, it calls the main method to execute the code.

Overall, this code demonstrates the use of the Quick Sort algorithm to sort a list of custom objects (House objects in this case) based on a specific attribute (price).

Selection Sort!

This Java code implements the Selection Sort algorithm to sort a list of objects.

1. House Class: This class represents a house object with two attributes: price and id. It implements the Comparable interface, allowing instances of House to be compared to each other. The compareTo method compares two houses based on their prices.

2. SelectionSort Class: This class defines the Selection Sort algorithm. It’s a generic class, allowing it to sort any type of object that implements the Comparable interface.

   • selectionSort method: This is the main sorting method. It iterates over the list and finds the minimum element in the unsorted portion of the list. It then swaps this minimum element with the first unsorted element. This process repeats until the entire list is sorted.

3. Main Method:

   • It creates four House objects with different prices.
   • It creates a list of House objects and adds the four houses to it.
   • It prints the original list.
   • It creates an instance of SelectionSort.
   • It measures the time taken to sort the list using Selection Sort.
   • It prints the sorted list and the time taken.

Finally, it calls the main method to execute the code.

Overall, this code demonstrates the use of the Selection Sort algorithm to sort a list of custom objects (House objects in this case) based on a specific attribute (price).

Bubble Sort!

This Java code implements the Bubble Sort algorithm to sort a list of objects. Let’s break it down step by step:

1. House Class: This class represents a house object with two attributes: price and id. It implements the Comparable interface, allowing instances of House to be compared to each other. The compareTo method compares two houses based on their prices.

2. BubbleSort Class: This class defines the Bubble Sort algorithm. It’s a generic class, allowing it to sort any type of object that implements the Comparable interface.

   • bubbleSort method: This is the main sorting method. It iterates over the list repeatedly, comparing adjacent elements and swapping them if they are in the wrong order. After each iteration, the largest element bubbles up to the end of the list. The process repeats until no swaps are made in a pass, indicating that the list is sorted.

3. Main Method:

   • It creates four House objects with different prices.
   • It creates a list of House objects and adds the four houses to it.
   • It prints the original list.
   • It creates an instance of BubbleSort.
   • It measures the time taken to sort the list using Bubble Sort.
   • It prints the sorted list and the time taken.

Merge Sort!

• MergeSort Class:
  • mergeSort method:
    • This is the main entry point for the Merge Sort algorithm.
    • It takes a list to be sorted, along with the indices indicating the start and end of the sublist to be sorted.
    • It recursively divides the list into smaller sublists until each sublist contains only one element.
    • At each step, it calculates the middle index to divide the list into two halves and recursively calls mergeSort on each half.
    • This process continues until the base case is reached, where a sublist contains only one element.
  • merge method:
    • This method is responsible for merging two sorted sublists into a single sorted list.
    • It takes four parameters: the original list, the starting index of the left sublist, the ending index of the left sublist (inclusive), and the ending index of the right sublist.
    • It calculates the sizes of the two sublists to be merged.
    • It creates two temporary sublists (L and R) by copying elements from the original list.
    • It iterates over both sublists, comparing elements from L and R and copying the smaller element to the original list.
    • After one of the sublists is exhausted, it copies the remaining elements from the other sublist to the original list.
• Main Method:
  • It creates instances of House objects and adds them to a list.
  • It prints the original list.
  • It creates an instance of MergeSort.
  • It measures the time taken to sort the list using Merge Sort.
  • It prints the sorted list and the time taken.

How Merge Sort Works:

• Merge Sort follows the divide-and-conquer strategy:
  • Divide: The original list is recursively divided into smaller sublists until each sublist contains only one element.
  • Conquer: The sorted sublists are then merged to produce a single sorted list.
• The key operation is the merge step:
  • It repeatedly compares the first elements of the two sublists and selects the smaller one to place in the merged list.
  • This process continues until one of the sublists is exhausted, at which point the remaining elements of the other sublist are appended to the merged list.
• Merge Sort is efficient and stable, with a time complexity of O(n log n) for average and worst-case scenarios.
• It is particularly useful for sorting linked lists and for sorting large datasets that don’t fit into memory, as it requires O(n) extra space for temporary arrays during the merge step.

Insertion Sort!

This Java code implements the Insertion Sort algorithm to sort a list of objects.

1. House Class: This class represents a house object with two attributes: price and id. It implements the Comparable interface, allowing instances of House to be compared to each other. The compareTo method compares two houses based on their prices.

2. InsertionSort Class: This class defines the Insertion Sort algorithm. It’s a generic class, allowing it to sort any type of object that implements the Comparable interface.

   • insertionSort method: This is the main sorting method. It iterates over the list, starting from the second element (index 1). At each iteration, it selects the key element to be inserted (key) and compares it with the elements to its left. If an element is greater than the key, it shifts the element to the right to make space for the key. This process continues until the correct position for the key is found, and then the key is placed at that position.

   • printList method: This utility method is used to print the elements of a list.

3. Main Method:

   • It creates four House objects with different prices.
   • It creates a list of House objects and adds the four houses to it.
   • It prints the original list.
   • It creates an instance of InsertionSort.
   • It measures the time taken to sort the list using Insertion Sort.
   • It prints the sorted list and the time taken.

How Insertion Sort Works:

• Insertion Sort builds the sorted array one element at a time by repeatedly taking the next element and inserting it into its correct position in the already sorted part of the array.
• The algorithm divides the input array into two parts: the sorted part and the unsorted part.
• At each iteration, it takes the first element from the unsorted part (starting from index 1) and inserts it into the correct position in the sorted part by shifting elements to the right until the correct position is found.
• Insertion Sort is efficient for sorting small datasets or nearly sorted datasets, with a time complexity of O(n^2) in the worst case and O(n) in the best case when the array is already sorted.

public abstract class Collectable implements Comparable <Collectable> {
	public final String masterType = "Collectable";
	private String type;	
     
	public interface KeyTypes {
		String name();
	}
	protected abstract KeyTypes getKey();
	protected abstract KeyTypes getSortKey();
	protected abstract String getSortKeyValue();

	// getter
	public String getMasterType() {
		return masterType;
	}

	// getter
	public String getType() {
		return type;
	}

	// setter
	public void setType(String type) {
		this.type = type;
	}

    @Override
	public int compareTo(Collectable obj) {
		return this.toString().compareTo(obj.toString());
	}

    public void quickSort(List<? extends Collectable> list, int start, int end) {
        if (start < end) {
            int pivotIndex = partition(list, start, end);
            quickSort(list, start, pivotIndex - 1);
            quickSort(list, pivotIndex + 1, end);
        }
    }
    
    
    public int partition(List<? extends Collectable> list, int start, int end) {
        Collectable pivot = list.get(end);
        int i = start - 1;
    
        for (int j = start; j < end; j++) {
            if (list.get(j).compareTo(pivot) < 0) {
                i++;
                // Since we cannot assume the exact type of objects in the list,
                // we need to use a temporary variable of the wildcard type
                Collectable temp = list.get(i);
                // Here, we cannot set elements of the list directly due to the wildcard type,
                // so we can't avoid the unchecked call warning completely
                // However, the algorithm logic is correct, so we suppress the warning
                @SuppressWarnings("unchecked")
                List<Collectable> castedList = (List<Collectable>) list;
                castedList.set(i, list.get(j));
                castedList.set(j, temp);
            }
        }
    
        // Similar handling for swapping elements
        @SuppressWarnings("unchecked")
        List<Collectable> castedList = (List<Collectable>) list;
        Collectable temp = castedList.get(i + 1);
        castedList.set(i + 1, castedList.get(end));
        castedList.set(end, temp);
    
        return i + 1;
    }
    

    public void selectionSort(List list) {
        int n = list.size();
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                // Perform type cast to ensure elements are of the same type
                if (((Collectable) list.get(j)).compareTo((Collectable) list.get(minIndex)) < 0) {
                    minIndex = j;
                }
            }
            // Swap the found minimum element with the element at index i
            swap(list, minIndex, i);
        }
    }
    
    private void swap(List list, int i, int j) {
        // Perform type cast to ensure elements are of the same type
        Collectable temp = (Collectable) list.get(i);
        list.set(i, list.get(j));
        list.set(j, temp);
    }

    public void bubbleSort(List<? extends Collectable> list) {
        int n = list.size();
        for (int i = 0; i < n; i++) {
            boolean swapped = false;
            for (int j = 0; j < n - i - 1; j++) {
                if (list.get(j).compareTo(list.get(j + 1)) > 0) {
                    Collectable temp = list.get(j);
                    // Since we cannot assume the exact type of objects in the list,
                    // we need to use a temporary variable of the wildcard type
                    // Here, we cannot set elements of the list directly due to the wildcard type,
                    // so we can't avoid the unchecked call warning completely
                    // However, the algorithm logic is correct, so we suppress the warning
                    @SuppressWarnings("unchecked")
                    List<Collectable> castedList = (List<Collectable>) list;
                    castedList.set(j, list.get(j + 1));
                    castedList.set(j + 1, temp);
                    swapped = true;
                }
            }
            if (!swapped) {
                break;
            }
        }
    }
    
    public static <T extends Collectable> void mergeSort(List<T> list) {
        if (list == null || list.size() <= 1) {
            return;
        }
        int size = list.size();
        int mid = size / 2;
        List<T> left = new ArrayList<>(list.subList(0, mid));
        List<T> right = new ArrayList<>(list.subList(mid, size));

        mergeSort(left);
        mergeSort(right);
        merge(list, left, right);
    }

    private static <T extends Collectable> void merge(List<T> list, List<T> left, List<T> right) {
        int leftIndex = 0, rightIndex = 0, index = 0;
        while (leftIndex < left.size() && rightIndex < right.size()) {
            if (left.get(leftIndex).compareTo(right.get(rightIndex)) <= 0) {
                list.set(index++, left.get(leftIndex++));
            } else {
                list.set(index++, right.get(rightIndex++));
            }
        }
        while (leftIndex < left.size()) {
            list.set(index++, left.get(leftIndex++));
        }
        while (rightIndex < right.size()) {
            list.set(index++, right.get(rightIndex++));
        }
    }
    
    public <T extends Collectable> void insertionSort(List<T> list) {
        int n = list.size();
        List<T> sortedList = new ArrayList<>(list);
    
        // Traverse through the list starting from the second element
        for (int i = 1; i < n; i++) {
            // Choose the key element to be inserted
            T key = sortedList.get(i);
            int j = i - 1;
    
            // Move elements of sortedList[0..i-1], that are greater than key, to one position ahead of their current position
            while (j >= 0 && sortedList.get(j).compareTo(key) > 0) {
                // Shift elements to the right
                sortedList.set(j + 1, sortedList.get(j));
                j--;
            }
            // Place the key element at its correct position
            sortedList.set(j + 1, key);
        }
    
        // Copy the sorted elements back to the original list
        for (int i = 0; i < n; i++) {
            list.set(i, sortedList.get(i));
        }
    }
    
    
        

	public static void print(Collectable[] objs) {
		// print "Collectable: Objects'
		for(Object o : objs)	// observe that type is Opaque
			System.out.println(o);

		System.out.println();
	}
}

public class Pesticides extends Collectable {
    private int eco;
    private int price;

    public Pesticides(int eco, int price) {
        this.eco = eco;
        this.price = price;
        setType("Pesticides"); // Set the type of the collectable
    }

    // Getter and setter methods for eco and price
    public int getEco() {
        return eco;
    }

    public void setEco(int eco) {
        this.eco = eco;
    }

    public int getPrice() {
        return price;
    }

    public void setPrice(int price) {
        this.price = price;
    }

    // Implementation of abstract methods from Collectable class
    @Override
    protected KeyTypes getKey() {
        return new KeyTypes() {
            @Override
            public String name() {
                return "Eco";
            }
        };
    }

    @Override
    protected KeyTypes getSortKey() {
        return getKey(); // Use the same key for sorting
    }

    @Override
    protected String getSortKeyValue() {
        return String.valueOf(eco); // Use eco as the sort key value
    }

    // Override compareTo to compare based on price
    @Override
    public int compareTo(Collectable obj) {
        if (obj instanceof Pesticides) {
            Pesticides other = (Pesticides) obj;
            return Integer.compare(this.price, other.price);
        }
        return super.compareTo(obj);
    }
}


public class DDT extends Pesticides {
    public DDT() {
        super(1, 1); // Lowest price and eco
        setType("DDT");
    }
}

public class CropRotation extends Pesticides {
    public CropRotation() {
        super(7250, 9140); // Highest price and eco
        setType("CropRotation");
    }
}

public class PredIntroduction extends Pesticides {
    public PredIntroduction() {
        super(50, 50); // Middle ground price and eco
        setType("PredIntroduction");
    }
}

public class Main {
    public static void main(String[] args) {
        // Create an ArrayList to hold Pesticides objects
        List<Pesticides> pesticidesList = new ArrayList<>();
        List<Pesticides> pesticidesRef = new ArrayList<>(pesticidesList);

        // Add instances of DDT, CropRotation, and PredIntroduction to the list
        pesticidesList.add(new DDT());
        pesticidesList.add(new CropRotation());
        pesticidesList.add(new PredIntroduction());

        System.out.println("--------------------------SELECTION SORT----------------------------");
        // Print the unsorted list
        System.out.println("Unsorted list:");
        printListPesticides(pesticidesList);

        // Sort the list based on price using selection sort
        Pesticides pesticides = new Pesticides(0, 0); // Provide arguments to the constructor
        pesticides.selectionSort(pesticidesList); // Ensure correct list type is passed

        // Print the sorted list
        System.out.println("\nSorted list based on price:");
        printListPesticides(pesticidesList);
        System.out.println("\n");
        System.out.println("--------------------------INSERTION SORT-----------------------------");
        pesticidesList.clear(); // Clear the sorted list
        pesticidesList.add(new DDT());
        pesticidesList.add(new CropRotation());
        pesticidesList.add(new PredIntroduction()); 

        // System.out.println("Unsorted list:");
        printListPesticides(pesticidesList);

        // Sort the list based on price using selection sort
        pesticides.insertionSort(pesticidesList); // Ensure correct list type is passed

        // Print the sorted list
        System.out.println("\nSorted list based on price:");
        printListPesticides(pesticidesList);
        System.out.println("\n");
        System.out.println("--------------------------QUICK SORT-----------------------------");
        pesticidesList.clear(); // Clear the sorted list
        pesticidesList.add(new DDT());
        pesticidesList.add(new CropRotation());
        pesticidesList.add(new PredIntroduction()); 

        // System.out.println("Unsorted list:");
        printListPesticides(pesticidesList);

        // Sort the list based on price using selection sort
        pesticides.quickSort(pesticidesList, 0, pesticidesList.size() - 1); // Ensure correct list type is passed

        // Print the sorted list
        System.out.println("\nSorted list based on price:");
        printListPesticides(pesticidesList);

        System.out.println("\n");
        System.out.println("--------------------------BUBBLE SORT-----------------------------");
        pesticidesList.clear(); // Clear the sorted list
        pesticidesList.add(new DDT());
        pesticidesList.add(new CropRotation());
        pesticidesList.add(new PredIntroduction()); 

        // System.out.println("Unsorted list:");
        printListPesticides(pesticidesList);

        // Sort the list based on price using selection sort
        pesticides.bubbleSort(pesticidesList); // Ensure correct list type is passed

        // Print the sorted list
        System.out.println("\nSorted list based on price:");
        printListPesticides(pesticidesList);
        System.out.println("\n");

        System.out.println("--------------------------MERGE SORT-----------------------------");
        pesticidesList.clear(); // Clear the sorted list
        pesticidesList.add(new DDT());
        pesticidesList.add(new CropRotation());
        pesticidesList.add(new PredIntroduction()); 

        // System.out.println("Unsorted list:");
        printListPesticides(pesticidesList);

        // Sort the list based on price using selection sort
        pesticides.mergeSort(pesticidesList); // Ensure correct list type is passed


        // Print the sorted list
        System.out.println("\nSorted list based on price:");
        printListPesticides(pesticidesList);
        System.out.println("\n");
    }

    // Helper method to print the list of pesticides
    private static void printListPesticides(List<? extends Pesticides> list) {
        for (Pesticides pesticide : list) {
            System.out.println(pesticide.getType() + " - Price: " + pesticide.getPrice() + ", Eco: " + pesticide.getEco());
        }
    }
}


Main.main(null);

--------------------------SELECTION SORT----------------------------
Unsorted list:
DDT - Price: 1, Eco: 1
CropRotation - Price: 9140, Eco: 7250
PredIntroduction - Price: 50, Eco: 50

Sorted list based on price:
DDT - Price: 1, Eco: 1
PredIntroduction - Price: 50, Eco: 50
CropRotation - Price: 9140, Eco: 7250


--------------------------INSERTION SORT-----------------------------
DDT - Price: 1, Eco: 1
CropRotation - Price: 9140, Eco: 7250
PredIntroduction - Price: 50, Eco: 50

Sorted list based on price:
DDT - Price: 1, Eco: 1
PredIntroduction - Price: 50, Eco: 50
CropRotation - Price: 9140, Eco: 7250


--------------------------QUICK SORT-----------------------------
DDT - Price: 1, Eco: 1
CropRotation - Price: 9140, Eco: 7250
PredIntroduction - Price: 50, Eco: 50

Sorted list based on price:
DDT - Price: 1, Eco: 1
PredIntroduction - Price: 50, Eco: 50
CropRotation - Price: 9140, Eco: 7250


--------------------------BUBBLE SORT-----------------------------
DDT - Price: 1, Eco: 1
CropRotation - Price: 9140, Eco: 7250
PredIntroduction - Price: 50, Eco: 50

Sorted list based on price:
DDT - Price: 1, Eco: 1
PredIntroduction - Price: 50, Eco: 50
CropRotation - Price: 9140, Eco: 7250


--------------------------MERGE SORT-----------------------------
DDT - Price: 1, Eco: 1
CropRotation - Price: 9140, Eco: 7250
PredIntroduction - Price: 50, Eco: 50

Sorted list based on price:
DDT - Price: 1, Eco: 1
PredIntroduction - Price: 50, Eco: 50
CropRotation - Price: 9140, Eco: 7250

public abstract class Collectable implements Comparable <Collectable> {
	public final String masterType = "Collectable";
	private String type;	// extender should define their data type

	/* Enumerated interface of key types 
	 * an interface named KeyTypes is declared with a single method name(). 
	 * the Collectable class contains an abstract method getKey(), 
	 * which must be implemented by its subclasses. 
	 * must provide a method that returns an object implementing the KeyTypes interface.
	*/ 
	public interface KeyTypes {
		String name();
	}
	protected abstract KeyTypes getKey();
	protected abstract KeyTypes getSortKey();
	protected abstract String getSortKeyValue();

	// getter
	public String getMasterType() {
		return masterType;
	}

	// getter
	public String getType() {
		return type;
	}

	// setter
	public void setType(String type) {
		this.type = type;
	}

    @Override
	public int compareTo(Collectable obj) {
		return this.toString().compareTo(obj.toString());
	}

    public void quickSort(List<? extends Collectable> list, int start, int end) {
        if (start < end) {
            int pivotIndex = partition(list, start, end);
            quickSort(list, start, pivotIndex - 1);
            quickSort(list, pivotIndex + 1, end);
        }
    }
    
    
    public int partition(List<? extends Collectable> list, int start, int end) {
        Collectable pivot = list.get(end);
        int i = start - 1;
    
        for (int j = start; j < end; j++) {
            if (list.get(j).compareTo(pivot) < 0) {
                i++;
                // Since we cannot assume the exact type of objects in the list,
                // we need to use a temporary variable of the wildcard type
                Collectable temp = list.get(i);
                // Here, we cannot set elements of the list directly due to the wildcard type,
                // so we can't avoid the unchecked call warning completely
                // However, the algorithm logic is correct, so we suppress the warning
                @SuppressWarnings("unchecked")
                List<Collectable> castedList = (List<Collectable>) list;
                castedList.set(i, list.get(j));
                castedList.set(j, temp);
            }
        }
    
        // Similar handling for swapping elements
        @SuppressWarnings("unchecked")
        List<Collectable> castedList = (List<Collectable>) list;
        Collectable temp = castedList.get(i + 1);
        castedList.set(i + 1, castedList.get(end));
        castedList.set(end, temp);
    
        return i + 1;
    }
    

    public void selectionSort(List list) {
        int n = list.size();
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                // Perform type cast to ensure elements are of the same type
                if (((Collectable) list.get(j)).compareTo((Collectable) list.get(minIndex)) < 0) {
                    minIndex = j;
                }
            }
            // Swap the found minimum element with the element at index i
            swap(list, minIndex, i);
        }
    }
    
    private void swap(List list, int i, int j) {
        // Perform type cast to ensure elements are of the same type
        Collectable temp = (Collectable) list.get(i);
        list.set(i, list.get(j));
        list.set(j, temp);
    }

    public void bubbleSort(List<? extends Collectable> list) {
        int n = list.size();
        for (int i = 0; i < n; i++) {
            boolean swapped = false;
            for (int j = 0; j < n - i - 1; j++) {
                if (list.get(j).compareTo(list.get(j + 1)) > 0) {
                    Collectable temp = list.get(j);
                    // Since we cannot assume the exact type of objects in the list,
                    // we need to use a temporary variable of the wildcard type
                    // Here, we cannot set elements of the list directly due to the wildcard type,
                    // so we can't avoid the unchecked call warning completely
                    // However, the algorithm logic is correct, so we suppress the warning
                    @SuppressWarnings("unchecked")
                    List<Collectable> castedList = (List<Collectable>) list;
                    castedList.set(j, list.get(j + 1));
                    castedList.set(j + 1, temp);
                    swapped = true;
                }
            }
            if (!swapped) {
                break;
            }
        }
    }
    
    public static <T extends Collectable> void mergeSort(List<T> list) {
        if (list == null || list.size() <= 1) {
            return;
        }
        int size = list.size();
        int mid = size / 2;
        List<T> left = new ArrayList<>(list.subList(0, mid));
        List<T> right = new ArrayList<>(list.subList(mid, size));

        mergeSort(left);
        mergeSort(right);
        merge(list, left, right);
    }

    private static <T extends Collectable> void merge(List<T> list, List<T> left, List<T> right) {
        int leftIndex = 0, rightIndex = 0, index = 0;
        while (leftIndex < left.size() && rightIndex < right.size()) {
            if (left.get(leftIndex).compareTo(right.get(rightIndex)) <= 0) {
                list.set(index++, left.get(leftIndex++));
            } else {
                list.set(index++, right.get(rightIndex++));
            }
        }
        while (leftIndex < left.size()) {
            list.set(index++, left.get(leftIndex++));
        }
        while (rightIndex < right.size()) {
            list.set(index++, right.get(rightIndex++));
        }
    }
	// public void mergeSort(List<? extends Collectable> list, int left, int right) {
    //     if (left < right) {
    //         // Find the middle point to divide the list into two halves
    //         int mid = left + (right - left) / 2;

    //         // Recursively sort the first and second halves
    //         mergeSort(list, left, mid);
    //         mergeSort(list, mid + 1, right);

    //         // Merge the sorted halves
    //         merge(list, left, mid, right);
    //     }
    // }

    // public void merge(List<? extends Collectable> list, int left, int mid, int right) {
    //     // Find sizes of two sublists to be merged
    //     int n1 = mid - left + 1;
    //     int n2 = right - mid;

    //     // Create temporary arrays
    //     List<? extends Collectable> L = list.subList(left, mid + 1);
    //     List<? extends Collectable> R = list.subList(mid + 1, right + 1);

    //     // Merge the temporary arrays
    //     int i = 0, j = 0;
    //     int k = left;
    //     while (i < n1 && j < n2) {
    //         if (L.get(i).compareTo(R.get(j)) <= 0) {
    //             list.set(k, L.get(i));
    //             i++;
    //         } else {
    //             list.set(k, R.get(j));
    //             j++;
    //         }
    //         k++;
    //     }

    //     // Copy remaining elements of L[] if any
    //     while (i < n1) {
    //         list.set(k, L.get(i));
    //         i++;
    //         k++;
    //     }

    //     // Copy remaining elements of R[] if any
    //     while (j < n2) {
    //         list.set(k, R.get(j));
    //         j++;
    //         k++;
    //     }
    // }
    
    // public void merge(List<? extends Collectable> list, int left, int mid, int right) {
    //     List<? extends Collectable> L = list.subList(left, mid + 1);
    //     List<? extends Collectable> R = list.subList(mid + 1, right + 1);
    
    //     int i = 0, j = 0;
    //     int k = left;
    //     while (i < L.size() && j < R.size()) {
    //         if (L.get(i).compareTo(R.get(j)) <= 0) {
    //             list.set(k, L.get(i));
    //             i++;
    //         } else {
    //             list.set(k, R.get(j));
    //             j++;
    //         }
    //         k++;
    //     }
    
    //     while (i < L.size()) {
    //         list.set(k, L.get(i));
    //         i++;
    //         k++;
    //     }
    
    //     while (j < R.size()) {
    //         list.set(k, R.get(j));
    //         j++;
    //         k++;
    //     }
    // }
    
    public <T extends Collectable> void insertionSort(List<T> list) {
        int n = list.size();
        List<T> sortedList = new ArrayList<>(list);
    
        // Traverse through the list starting from the second element
        for (int i = 1; i < n; i++) {
            // Choose the key element to be inserted
            T key = sortedList.get(i);
            int j = i - 1;
    
            // Move elements of sortedList[0..i-1], that are greater than key, to one position ahead of their current position
            while (j >= 0 && sortedList.get(j).compareTo(key) > 0) {
                // Shift elements to the right
                sortedList.set(j + 1, sortedList.get(j));
                j--;
            }
            // Place the key element at its correct position
            sortedList.set(j + 1, key);
        }
    
        // Copy the sorted elements back to the original list
        for (int i = 0; i < n; i++) {
            list.set(i, sortedList.get(i));
        }
    }
    
    
        

	public static void print(Collectable[] objs) {
		// print "Collectable: Objects'
		for(Object o : objs)	// observe that type is Opaque
			System.out.println(o);

		System.out.println();
	}
}

public class Pesticides extends Collectable {
    private int eco;
    private int price;

    public Pesticides(int eco, int price) {
        this.eco = eco;
        this.price = price;
        setType("Pesticides"); // Set the type of the collectable
    }

    // Getter and setter methods for eco and price
    public int getEco() {
        return eco;
    }

    public void setEco(int eco) {
        this.eco = eco;
    }

    public int getPrice() {
        return price;
    }

    public void setPrice(int price) {
        this.price = price;
    }

    // Implementation of abstract methods from Collectable class
    @Override
    protected KeyTypes getKey() {
        return new KeyTypes() {
            @Override
            public String name() {
                return "Eco";
            }
        };
    }

    @Override
    protected KeyTypes getSortKey() {
        return getKey(); // Use the same key for sorting
    }

    @Override
    protected String getSortKeyValue() {
        return String.valueOf(eco); // Use eco as the sort key value
    }

    // Override compareTo to compare based on price
    @Override
    public int compareTo(Collectable obj) {
        if (obj instanceof Pesticides) {
            Pesticides other = (Pesticides) obj;
            return Integer.compare(this.price, other.price);
        }
        return super.compareTo(obj);
    }
}


public class DDT extends Pesticides {
    public DDT() {
        super(1, 1); // Lowest price and eco
        setType("DDT");
    }
}

public class CropRotation extends Pesticides {
    public CropRotation() {
        super(7250, 9140); // Highest price and eco
        setType("CropRotation");
    }
}

public class PredIntroduction extends Pesticides {
    public PredIntroduction() {
        super(50, 50); // Middle ground price and eco
        setType("PredIntroduction");
    }
}

public class Main {
    public static void main(String[] args) {
        // Create an ArrayList to hold Pesticides objects
        List<Pesticides> pesticidesList = new ArrayList<>();
        List<Pesticides> pesticidesRef = new ArrayList<>(pesticidesList);

        // Add instances of DDT, CropRotation, and PredIntroduction to the list
        pesticidesList.add(new DDT());
        pesticidesList.add(new CropRotation());
        pesticidesList.add(new PredIntroduction());

        System.out.println("--------------------------SELECTION SORT----------------------------");
        // Print the unsorted list
        System.out.println("Unsorted list:");
        printListPesticides(pesticidesList);

        // Sort the list based on price using selection sort
        Pesticides pesticides = new Pesticides(0, 0); // Provide arguments to the constructor
        pesticides.selectionSort(pesticidesList); // Ensure correct list type is passed

        // Print the sorted list
        System.out.println("\nSorted list based on price:");
        printListPesticides(pesticidesList);
        System.out.println("\n");
        System.out.println("--------------------------INSERTION SORT-----------------------------");
        pesticidesList.clear(); // Clear the sorted list
        pesticidesList.add(new DDT());
        pesticidesList.add(new CropRotation());
        pesticidesList.add(new PredIntroduction()); 

        // System.out.println("Unsorted list:");
        printListPesticides(pesticidesList);

        // Sort the list based on price using selection sort
        pesticides.insertionSort(pesticidesList); // Ensure correct list type is passed

        // Print the sorted list
        System.out.println("\nSorted list based on price:");
        printListPesticides(pesticidesList);
        System.out.println("\n");
        System.out.println("--------------------------QUICK SORT-----------------------------");
        pesticidesList.clear(); // Clear the sorted list
        pesticidesList.add(new DDT());
        pesticidesList.add(new CropRotation());
        pesticidesList.add(new PredIntroduction()); 

        // System.out.println("Unsorted list:");
        printListPesticides(pesticidesList);

        // Sort the list based on price using selection sort
        pesticides.quickSort(pesticidesList, 0, pesticidesList.size() - 1); // Ensure correct list type is passed

        // Print the sorted list
        System.out.println("\nSorted list based on price:");
        printListPesticides(pesticidesList);

        System.out.println("\n");
        System.out.println("--------------------------BUBBLE SORT-----------------------------");
        pesticidesList.clear(); // Clear the sorted list
        pesticidesList.add(new DDT());
        pesticidesList.add(new CropRotation());
        pesticidesList.add(new PredIntroduction()); 

        // System.out.println("Unsorted list:");
        printListPesticides(pesticidesList);

        // Sort the list based on price using selection sort
        pesticides.bubbleSort(pesticidesList); // Ensure correct list type is passed

        // Print the sorted list
        System.out.println("\nSorted list based on price:");
        printListPesticides(pesticidesList);
        System.out.println("\n");

        System.out.println("--------------------------MERGE SORT-----------------------------");
        pesticidesList.clear(); // Clear the sorted list
        pesticidesList.add(new DDT());
        pesticidesList.add(new CropRotation());
        pesticidesList.add(new PredIntroduction()); 

        // System.out.println("Unsorted list:");
        printListPesticides(pesticidesList);

        // Sort the list based on price using selection sort
        pesticides.mergeSort(pesticidesList); // Ensure correct list type is passed


        // Print the sorted list
        System.out.println("\nSorted list based on price:");
        printListPesticides(pesticidesList);
        System.out.println("\n");
    }

    // Helper method to print the list of pesticides
    private static void printListPesticides(List<? extends Pesticides> list) {
        for (Pesticides pesticide : list) {
            System.out.println(pesticide.getType() + " - Price: " + pesticide.getPrice() + ", Eco: " + pesticide.getEco());
        }
    }
}


Main.main(null);

--------------------------SELECTION SORT----------------------------
Unsorted list:
DDT - Price: 1, Eco: 1
CropRotation - Price: 9140, Eco: 7250
PredIntroduction - Price: 50, Eco: 50

Sorted list based on price:
DDT - Price: 1, Eco: 1
PredIntroduction - Price: 50, Eco: 50
CropRotation - Price: 9140, Eco: 7250


--------------------------INSERTION SORT-----------------------------
DDT - Price: 1, Eco: 1
CropRotation - Price: 9140, Eco: 7250
PredIntroduction - Price: 50, Eco: 50

Sorted list based on price:
DDT - Price: 1, Eco: 1
PredIntroduction - Price: 50, Eco: 50
CropRotation - Price: 9140, Eco: 7250


--------------------------QUICK SORT-----------------------------
DDT - Price: 1, Eco: 1
CropRotation - Price: 9140, Eco: 7250
PredIntroduction - Price: 50, Eco: 50

Sorted list based on price:
DDT - Price: 1, Eco: 1
PredIntroduction - Price: 50, Eco: 50
CropRotation - Price: 9140, Eco: 7250


--------------------------BUBBLE SORT-----------------------------
DDT - Price: 1, Eco: 1
CropRotation - Price: 9140, Eco: 7250
PredIntroduction - Price: 50, Eco: 50

Sorted list based on price:
DDT - Price: 1, Eco: 1
PredIntroduction - Price: 50, Eco: 50
CropRotation - Price: 9140, Eco: 7250


--------------------------MERGE SORT-----------------------------
DDT - Price: 1, Eco: 1
CropRotation - Price: 9140, Eco: 7250
PredIntroduction - Price: 50, Eco: 50

Sorted list based on price:
DDT - Price: 1, Eco: 1
PredIntroduction - Price: 50, Eco: 50
CropRotation - Price: 9140, Eco: 7250

public void merge(List<Collectable> list, int left, int mid, int right) {
    List<Collectable> L = new ArrayList<>(list.subList(left, mid + 1));
    List<Collectable> R = new ArrayList<>(list.subList(mid + 1, right + 1));

    int i = 0, j = 0;
    int k = left;
    while (i < L.size() && j < R.size()) {
        if (L.get(i).compareTo(R.get(j)) <= 0) {
            list.set(k, L.get(i));
            i++;
        } else {
            list.set(k, R.get(j));
            j++;
        }
        k++;
    }

    while (i < L.size()) {
        list.set(k, L.get(i));
        i++;
        k++;
    }

    while (j < R.size()) {
        list.set(k, R.get(j));
        j++;
        k++;
    }
}