How can I sort an arraylist without using collections.sort()? [duplicate]

Question

This question already has answers here:

sorting integers in order lowest to highest java (7 answers)

Closed 9 years ago.

I have been looking for a while for a way to sort an arraylist without using collections.sort as my own logic is flawed and I have been having a lot of trouble.

I need to sort it in a way that I can use a method I created that basically does what collections.swap does in order to completely sort an arraylist.

Here is my code:

public static void mySort(ArrayList<Double> sort){

    int min = 0;
    int i;
    int j = 0;
        for(i = 0; i < sort.size() - 1; i++) {
            min = i;
            mySwap(sort, j ,min);

            for(j = 0; j < sort.size() -1;j++){
                if(j < min ){
                    min = j;
                }
            }
    }
}

public static void mySwap(ArrayList<Double> a, int x, int y){

    double temp = a.get(x);
    a.set(x,a.get(y));
    a.set(y,temp);
}

I have been having a lot of trouble of with this. Sorry if it is a question is that harming the community.

Answer 1

I assume you want the following algorithm: find min in the rest of the array, swap it with current element starting with first, reconsider rest to be array starting of increased +1 index.

You should update your code like this:

public static void swap(List<Integer> sort, int i, int j) {
    int tmp = sort.get(i);
    sort.set(i, sort.get(j));
    sort.set(j, tmp);
}

public static void doSort(List<Integer> sort) {
    int min;
    for (int i = 0; i < sort.size(); ++i) {
        //find minimum in the rest of array
        min = i;
        for (int j = i + 1; j < sort.size(); ++j) {
            if (sort.get(j) < sort.get(min)) {
                min = j;
            }
        }

        //do swap
        swap(sort, i, min);
    }
}

You have a bug with finding minimum and then swapping items. Please note that the code can be improved in many ways (I tried to maintain your let's say way of coding as possible), such as swapping integer references in swap(), doing BubbleSort like another answer suggests (same algorithm but simpler implementation), using O(n * log(n)) complexity algorithm, and so on.