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());
}

Answer 1

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!

Answer 2

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();
    }
}