How can I bubble sort this?

Question

In this program I just wanted to bubble sort the ArrayList words. So far I used the Collections.sort and it has placed all the lines in the text file alphabetically. However, I want to implement a binary search algorithm to this program but, I don't think it would be possible to do so without sorting the data (e.g merge sort, bubble sort). I might be wrong but that is why I came here for guidance & knowledge.

Secondly, when I create a method for sorting, this is a words is a String not an String[]. How do I then do a bubble sort using such a datatype?

public static void main(String[]args) throws IOException{
    Scanner scan = new Scanner(System.in);
    String stringSearch = scan.nextLine();

    ArrayList<String> words = new ArrayList<String>();
    BufferedReader reader = new BufferedReader(new FileReader("File1.txt"));

    String line;

    while ((line = reader.readLine()) != null) {                
        words.add(line);
    }reader.close();

    Collections.sort(words);
    for(String str:words)
        System.out.println(str); 

    for(String sLine : words) 
    {
        if (sLine.contains(stringSearch)) 
        {
            int index = words.indexOf(sLine);
            System.out.println("Got a match at line " + index);

        }
     }

    System.out.println(words.size());
}

_"So far I used the `Collections.sort` and it has placed all the lines in the text file alphabetically."_ How is this result different from what you call a "bubble sort"? After you use `Collections.sort` you should be able to do a binary search on the result without any further sorting. — Jim Garrison, Jan 09 '13 at 04:48
Binary search requires ordered data (it's a prerequisite or it will fail miserably :-/), yes, but it .. doesn't matter *how* it is sorted. Also, with very few exceptions (it does have nice properties wrt almost entirely sorted data and stability), a [Bubble Sort](http://en.wikipedia.org/wiki/Bubble_sort) should be left to a junior-level college course .. and never used in "real" code due to abysmal asymptotic complexity. — , Jan 09 '13 at 04:51
I'm not sure exactly what algorithm `Collections.sort` (I heard a variation of Quick Sort?) uses, but I can guarantee that it is faster than bubble sort! — Chris Dargis, Jan 09 '13 at 04:53
Thank you guys !! I don't mean to be a pain but I'm new to algorithms and I've been used to doing binary search algorithms using int[] arrays. But then this time, I have to create a binary search method with a String parameter. If it was a String[] array I would have understood but I don't even have a clue where to start when using a String as a parameter.....any help?? — user1883386, Jan 09 '13 at 05:01
@DougRamsey http://stackoverflow.com/questions/753237/what-sort-does-java-collections-sortnodes-use , http://stackoverflow.com/questions/3566843/why-does-java-util-arrays-sortobject-use-2-kinds-of-sorting-algorithms — , Jan 09 '13 at 05:01
@pst: Thanks. I misspoke. The algorithm used is dependent on the size of the problem (which includes Quick Sort, Merge Sort, Insertion Sort). Asymptotic notation does not measure speed, rather growth rate. I was really referring to relatively large numbers of `N`. Thanks for pointing it out :) — Chris Dargis, Jan 09 '13 at 05:08

score 2 · Accepted Answer · edited Jan 09 '13 at 04:56

2

First, you can sort the list using Collections.sort(Collection).

Second, you can use List.get(int) of the ArrayList implementation to achieve an O(1) indexed access.

Third, Object.compareTo(Object) will do the job of guiding your binary search loop.

Sorry if I misunderstood something!

edited Jan 09 '13 at 04:56

Bhavik Shah

5,125
3
23
40

answered Jan 09 '13 at 04:49

PEdroArthur

824
8
18

score 0 · Answer 2 · answered May 06 '19 at 07:50

Bubble sort is a simple sorting algorithm that repeatedly steps through the list should be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. Do you know why its called as Bubble sort because The smaller value bubbles up to the top of the list, while the larger value sinks to the bottom.

Please find the complete source code from my tech blog - http://www.algonuts.info/java---how-to-create-a-bubble-sort.html

package info.algonuts;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;

class BubbleSortCompute {
    static List <Integer> intList = new ArrayList <Integer>();

    public static void add(List <Integer> temp) {
        intList.clear();
        Iterator<Integer> ptr  = temp.iterator();
        while(ptr.hasNext()) {
            intList.add(ptr.next());
        }
    }

    public static void sort() {
        System.out.println("Before Bubble Sort:");
        Iterator<Integer> ptr  = intList.iterator();
        while(ptr.hasNext()) {
            System.out.print(ptr.next()+" ");
        }
        System.out.println("\n\nAfter Bubble Sort:");
        compute();
        ptr  = intList.iterator();
        while(ptr.hasNext()) {
            System.out.print(ptr.next()+" ");
        }
    }

    private static void compute() {
        int temp;
        int intListSize = intList.size();
        for(int outerCounter = 0;outerCounter < intListSize; outerCounter++) {
            for(int interCounter = 0;interCounter < intListSize - outerCounter - 1; interCounter++) {
                if(intList.get(interCounter) >= intList.get(interCounter+1)) {
                    temp  = intList.get(interCounter+1);
                    intList.set(interCounter+1, intList.get(interCounter));
                    intList.set(interCounter, temp);
                }
            }
        }   
    }
}

public class BubbleSort {
    //Entry Point
    public static void main(String[] args) {
        List <Integer> intList = new ArrayList <Integer>(Arrays.asList(50,2,5,78,90,20,4,6,98,1));
        BubbleSortCompute.add(intList);
        BubbleSortCompute.sort();
    }
}

How can I bubble sort this?

2 Answers2