Bubble, selection, and insertion sorting

Question

The following programs are bubble sorting, selection sorting and insertion sorting. As most of the programs online or in books are with Arrays and not ArrayList, I am unsure if they are correct.

---

BubbleSort:

 public class BubbleSort {
 List<Integer> unsortedList;
 private BubbleSort() {
 unsortedList = new ArrayList<Integer>();
 unsortedList.add(0, 6);
 unsortedList.add(1, 3);
 unsortedList.add(2, 7);
 unsortedList.add(3, 4);
 unsortedList.add(4, 2);
 unsortedList.add(5, 3);
 unsortedList.add(6, 8);
 }
 private void sortData() {
 ArrayList<Integer> tempList = (ArrayList<Integer>) this.unsortedList;
 int size = unsortedList.size();
 int counter = size;
 do {
 for (int i = 0; i < size-1; i++) {
 if (unsortedList.get(i) > unsortedList.get(i + 1)) {
 Integer temp1= unsortedList.get(i + 1);
 Integer temp2= unsortedList.get(i);
 unsortedList.set(i,temp1);
 unsortedList.set(i+1,temp2);
 }
 }
 size = size - 1;
 } while (size != 1);
 }
 public static void main(String arg[]) {
 BubbleSort obj = new BubbleSort();
 obj.sortData();
 for(Integer i:obj.unsortedList){
 System.out.println(i);
 }
 }}

---

SelectionSort:

 public class SelectionSort {
 List<Integer> unsortedList;
 private SelectionSort() {
 unsortedList = new ArrayList<Integer>();
 unsortedList.add(0, 16);
 unsortedList.add(1, 3);
 unsortedList.add(2, 7);
 unsortedList.add(3, 4);
 unsortedList.add(4, 12);
 unsortedList.add(5, 3);
 unsortedList.add(6, 8);
 unsortedList.add(7, 18);
 unsortedList.add(8, 81);
 unsortedList.add(9, 2);
 }
 public void sortData() {
 int totalPass = unsortedList.size();
 int listLength = totalPass;
 for (int i = 0; i <= totalPass - 1; i++) {
 int pointerSmallPosition=i;
 for (int j = i; j < listLength-1; j++) {
 if (unsortedList.get(pointerSmallPosition) > unsortedList.get(j + 1)) {
 pointerSmallPosition=j + 1;
 }
 }
 int temp1= unsortedList.get(i);
 int temp2= unsortedList.get(pointerSmallPosition);
 unsortedList.set(i,temp2);
 unsortedList.set(pointerSmallPosition,temp1); 
 }
}
public static void main(String arg[]) {
 SelectionSort obj = new SelectionSort();
 obj.sortData();
 for (Integer i : obj.unsortedList) {
 System.out.println(i);
 }
}}

---

InsertionSort:

 public class InsertionSort {
 List<Integer> unsortedList;
 public InsertionSort(){
 unsortedList = new ArrayList<Integer>();
 unsortedList.add(0, 6);
 unsortedList.add(1, 3);
 unsortedList.add(2, 7);
 unsortedList.add(3, 4);
 unsortedList.add(4, 2);
 unsortedList.add(5, 3);
 unsortedList.add(6, 8);
 }
 public static void main(String arg[]){
 InsertionSort obj=new InsertionSort();
 obj.sortData();
 for(Integer i:obj.unsortedList){
 System.out.println(i);
 }
 }
 private void sortData() {
 int size = unsortedList.size();
 int sortedSize=0;
 for(int i=1;i<size-1;i++){
 int j=i;
 do{
 if(unsortedList.get(j)<unsortedList.get(j-1)){
 int small=unsortedList.get(j);
 int large=unsortedList.get(j-1);
 unsortedList.set(j-1, small);
 unsortedList.set(j, large);
 }
 j--;
 }while(j>sortedSize);
 }}}

Answer 1

The comments below apply to all of your classes, even though I will use BubbleSort in all the examples.

Usability

The sort classes have hard-coded data in the constructor. This is unusable for any practical purpose. You can easily do better by making the list a parameter. For example:

class BubbleSort { 
 public static void sort(List<Integer> list) {
 // ...
 }
 public static void main(String[] args) {
 List<Integer> list = new ArrayList<>(Arrays.asList(6, 3, 7, 4, 2, 3, 8));
 BubbleSort.sort(list);
 System.out.println(list);
 }
}

Member fields

There's really no need to make unsorted list a member field of the class. The sorting method can receive the list as a parameter, sort it, and that's it. No need to keep a reference. (See the example in the previous point.)

Prefer interface types instead of implementation

List is the interface, ArrayList is the implementation. Your algorithm can work everywhere with a List, a more general, abstract concept, so it's good to refer to the list everywhere as List.

This was a particularly nonsensical move:

 ArrayList<Integer> tempList = (ArrayList<Integer>) this.unsortedList;

You could delete this line and it will make no difference.

Unnecessary code

There are several unnecessary statements, for example the tempList and counter variables in the sortData method. Avoid all unnecessary code.

Initializing a list

An easier way to initialize a list of numbers:

List<Integer> list = new ArrayList<>(Arrays.asList(6, 3, 7, 4, 2, 3, 8));

Use for loop for simple counting

The while loop in sortData is a simple counter from size until 1. It's more natural to use a counting for loop for this purpose, like this:

for (int size = list.size(); size != 1; --size) {
 // ...
}

Suggested implementation

Applying the above suggestions, the bubble sort becomes:

public static void sort(List<Integer> list) {
 for (int size = list.size(); size != 1; --size) {
 for (int i = 0; i < size - 1; i++) {
 int temp1 = list.get(i + 1);
 int temp2 = list.get(i);
 if (temp2 > temp1) {
 list.set(i, temp1);
 list.set(i + 1, temp2);
 }
 }
 }
}

• Navdeep Singh: Thanks to everyone for their responses. I really appreciate what you have provided here. Thanks again.

Answer 2

They seem right to me. A few minor comments:

1. You don't need to construct your lists by adding .add(pos, value). You can build them from an array as:

   int[] array = {6,12,9,-14};
   List<Integer> list = new ArrayList<>(Arrays.asList(array);
   

   which is more concise and readable.

2. In your bubblesort, you do:

   Integer temp1= unsortedList.get(i + 1);
   Integer temp2= unsortedList.get(i);
   

   accessing unsortedList twice. If you assign outside the if, you can recycle it and make it more readable. Also, consider using better names than temp1 and temp2: not much difference here, but it's a good habit to get into, same for insertion.

Answer 3

• It's best practices to let statements like if, for, do, while be followed by a space to distinguish them from method invocations. Sometimes you do it, sometimes you don't.
• Sometimes you enclose operators with spaces, sometimes you don't. It's best practices to do it always.
• Ending classes with }} or }}} is unusual.
• Variable names like obj aren't to descriptive. Any decent java programmer knows that a reference variable refers to an object. I'd call them sort.
• SelectionSort: int listLength = totalPass; isn't necessary since you don't change its value, you just use it.

• Declaring variables inside a loop (Integer temp<n>, int pointerSmallPosition, int temp<n>, int j, int small, int large) is advised in general (削除) isn't a good idea in general (削除ここまで).

  In cases where performance really matters (Diego Martinoia mentioned it in his answer) it's slightly different since the stack element (and heap space in case of an object) for every variable is thrown away and re-allocated with every iteration rather than being reused. (Unless the compiler or the JVM optimizes such. But that's not guaranteed.) Declaring them before the loop also gives the readers of your code (including you in, let's say, 5 years) an idea what's going on inside it.

  See also Declare Variables Inside or Outside a Loop.

  You can combine both, limited scope and reuse, if you declare variables in for's initialization in InsertionSort:

  private void sortData() {
   int size = unsortedList.size();
   for (int sortedSize = 0, i = 1, j = i, small, large;
   i < size - 1; i++) {
   do {
   if (unsortedList.get(j) < unsortedList.get(j - 1)) {
   small = unsortedList.get(j);
   large = unsortedList.get(j - 1);
   unsortedList.set(j - 1, small);
   unsortedList.set(j, large);
   }
   } while (--j > sortedSize);
   }
  }
  

  Note also the decrement of j that has been moved.

• Simon Forsberg: +1, but I don't agree with avoiding declaring variables inside a loop. My recommendation is to declare variables in the tightest scope possible.
• Gerold Broser: @SimonAndréForsberg You're right. I adapted my answer accordingly.