How to write a method that sorts an ArrayList in java using a generic Comparable type

Question

I am trying to write a method to sort an array of integers.

The method must utilize the Comparable interface. I've designed a test case and attempted to write a solution.

Expected:

Enter 10 integers: 3 4 12 7 3 4 5 6 4 7
The sorted numbers are 3 3 4 4 4 5 6 7 7 12

Actual:

Enter 10 integers: 1
Enter 10 integers: 2
Enter 10 integers: 34
Enter 10 integers: 4
Enter 10 integers: 3
Enter 10 integers: 2
Enter 10 integers: 1
Enter 10 integers: 4
Enter 10 integers: 5
Enter 10 integers: 6
The sorted numbers are: 3 5 4 1 2 2 1 4 5 6

My attempt

public class Test2 {
    
    public static void main(String args[]){
        ArrayList<Integer> array = new ArrayList<>();
        Scanner input = new Scanner(System.in);
        for(int i = 0; i < 10; i++){
            System.out.print("Enter 10 integers: ");
            int integer    = input.nextInt();
            array.add(integer);
        }
        sort(array);
        System.out.print("The sorted numbers are ");
        for(int i = 0; i <= array.size()-1; i++){
            System.out.print(array.get(i)+" ");
        }
    }

    public static <E extends Comparable <E>> void sort(ArrayList<E> list) {
        int n = list.size();
    
        for(int  i = 1; i < n-1; i++) {
            for(int j = 0; j < n-i-1; j++) {
                if(list.get(i).compareTo(list.get(i+1)) < 0) {
                    E temp = list.get(i);
                    list.set(j, list.get(j+1));
                    list.set(j + 1, temp);
                }
            }
         }
     }
}

What can I try next?

Alexander Ivanchenko · Accepted Answer · 2022-04-02 12:21:19Z

3

It doesn't work in the same way, as you can assign the value to the element of an array.

With a list you have to use method set():

list.set(j + 1, temp);

Also, avoid using concrete types like ArrayList for method parameters and variables, write your code against interfaces like List. Now, your method sort() is limited to accept only instances ArrayList and not able to deal with a LinkedList.

edited Apr 2, 2022 at 12:21

answered Apr 1, 2022 at 20:52

Alexander Ivanchenko

29.3k6 gold badges29 silver badges54 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Joop Eggen · Accepted Answer · 2022-04-03 21:29:26Z

Actually the logic is wrong, that repeated swapping will not necessarily sort all.

The code does not give any assurrance to cover all pairs needing swapping:

public static <E extends Comparable <E>> void sort(List<E> list) {
    int n = list.size();
    for (int  i = 1; i < n-1; i++) { // n-2 i's
        for (int j = 0; j < n-1-i; j++) { // for all i: n-1-i
            if (list.get(i).compareTo(list.get(i+1)) < 0) {
                Collections.swap(i, j+1);
            }
        }
     }
 }

It assumes that the elements after n-1-i will be sorted later. Especially the last element i == n-1 seems not be treated.

More trustworthy:

public static <E extends Comparable <E>> void sort(List<E> list) {
    int n = list.size();
    // INVARIANT list[0, i> is sorted
    for (int  i = 0; i < n; i++) {
        // INVARIANT list[0, i> is sorted

        // INVARIANT list[0, j> is sorted
        // INVARIANT list[j, i> is sorted
        for (int j = 0; j < i; j++) {
            // INVARIANT list[0, j> is sorted
            // INVARIANT list[j, i> is sorted
            if (list.get(i).compareTo(list.get(j)) < 0) {
                Collections.swap(i, j);
                // And greater j's are unsorted w.r.t. j
            }
            // INVARIANT list[j+1, i> is sorted
            // INVARIANT list[0, j+1> is sorted
        }
        // INVARIANT list[0, i+1> is sorted
     }
     // INVARIANT list[0, n> is sorted
 }

You could check out pre-conditions, post-conditions, loop-variants, invariants and proofs.

The complexity (of both) is O(n²) which could be bettered, as 100² is already 10_000 (5_000 loop steps).

PM 77-1 · Accepted Answer · 2022-04-01 21:13:43Z

-3

import java.util.ArrayList;
import java.util.Scanner;


public class Exercise19_09 {
    
    public static void main(String args[]){
        ArrayList<Integer> array = new ArrayList<>();
        Scanner input = new Scanner(System.in);
        System.out.print("Enter 10 integers: ");
        for(int i = 0; i < 10; i++){
            int integer    = input.nextInt();
            array.add(integer);
        }
        sort(array);
        System.out.print("The sorted numbers are ");
        for(int i = 0; i <= array.size()-1; i++){
            System.out.print(array.get(i)+" ");
        }
    }

    public static <E extends Comparable <E>> void sort(ArrayList<E> list){
        int n = list.size();
    
        for(int  i = 0; i < n-1; i++){
            for(int j = 0; j < n-i-1; j++)
                if(list.get(j).compareTo(list.get(j+1)) > 0){
                    E temp = list.get(j);
                    list.set(j, list.get(j+1));
                    list.set(j + 1, temp);

                }
        }
    }
}

edited Apr 1, 2022 at 21:13

PM 77-1

13.4k21 gold badges73 silver badges118 bronze badges

answered Apr 1, 2022 at 21:03

Evan Gertis

2,0767 gold badges37 silver badges81 bronze badges

1 Comment

halfer Over a year ago

The general advice given on Stack Overflow about answers is about how the author can make them useful for future readers. I've not downvoted, but a couple of people have. Perhaps their advice would be that some explanatory text would be excellent. Could you add some in?

Collectives™ on Stack Overflow

How to write a method that sorts an ArrayList in java using a generic Comparable type

3 Answers 3

Comments

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related