Swapping is the main feature of both the sorting techniques. You must understand the swapping of elements from one index position to another in order to make easier for you to understand the Sorting Techniques. Example:-
Before you learn about swapping the values within the Array List, you should learn the simple swapping within two or more variables.
int a=10, b=20;
Now, to do swapping we need an extra variable.
int temp;
temp=a; a=b; b=temp;
Now, the identifier ‘a’ has the integer value ‘20’ and the identifier ‘b’ has the integer value ‘10’.
Step 1: temp=a;
By the above step, we have stored the integer value ‘10’ in the identifier ‘temp’. To make it easier just think like this: temp=10;
Step 2: a=b;
By the above step, we have stored the integer value ‘20’ in the identifier ‘a’. To make it easier just think like this: a=20;
Step 3: b=temp;
Now, the identifier ‘temp’ has the integer value ‘10’. So, by the above step we have changed the value of ‘b’ i.e., from ‘20’ to ‘10’.
Now take another example of swapping:
int a, b, c, temp;
a=1; b=2; c=3;
temp=a; a=b; b=c; c=temp;
System.out.println(a+”\n”+b+”\n”+c);
Output:-
2
3
1
By the same way technique the swapping of elements within an Array List can also be done but with the help of any iteration statement (for, while, do-while).
Index values are also the important one. You must understand the use of index number while working with any Array List. Example:-
List: [10, 1, 9, 2, 8, 3, 7, 4, 6, 5]
Index: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Now, if you want to access the specific element from the above list, you have to use its Index value.
int list[] = new int[]{10, 1, 9, 2, 8, 3, 7, 4, 6, 5};
Now, I want to change add ‘5’ in ‘9’, which is present in the list, I will do so as:-
list[2]+=5;
As the Index value of ’9’ is ‘2’, I have accessed ‘9’ by using ‘2’ within ‘[ ]’. We can access any of the list elements by the same way.
Bubble Sort:-
In Bubble sort the numbers are compared to the adjoining number and if the adjoining number is smaller than the first number, the numbers will be swapped. Example of the algorithm and sorting of a 10 number list with it (Sorting to Ascending Order):-
List:-
[10, 1, 9, 2, 8, 3, 7, 4, 6, 5]
STEP 1
The first element in the list is ‘10’. Now, ‘10’ is compared with ‘1’, the adjoining number, and 1 is smaller than ‘10’ so the swapping takes place. After the first swapping the list becomes like:
[1, 10, 9, 2, 8, 3, 7, 4, 6, 5]
Now, the number second element is again ‘10’. So, again the same procedure, like above, takes place and this happens until the list, above list, becomes:
[1, 9, 2, 8, 3, 7, 4, 6, 5, 10]
STEP 2
1-9 No swapping done, 9-2 swapping done….. And after the few more swapping the list will become:
[1, 2, 8, 3, 7, 4, 6, 5, 9, 10]
Other Results, per step, are below:-
STEP 3
[1, 2, 3, 7, 4, 6, 5, 8, 9, 10]
STEP 4
[1, 2, 3, 4, 6, 5, 7, 8, 9, 10]
STEP 5
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
The List becomes sorted but as the test condition of the loop is ‘true’, the other steps will also execute but no swapping will be done. So, in general you can say that the list became sorted after five steps but programmatically the list will be said sorted only after all the steps have been executed successfully.
STEP 6
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] (No Swapping Done)
STEP 7
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] (No Swapping Done)
STEP 8
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] (No Swapping Done)
STEP 9
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] (No Swapping Done)
STEP 10
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] (No Swapping Done)
Selection Sort:-
In this technique, the first element is assumed as the small element and compared with all other elements of the list and if any other element is smaller than that, the new smaller number is compared with the remaining list and if no element is much smaller than that, the number is separated from the list (According to the sorting i.e., Ascending or Descending). Here are the steps executed on the same list, the list used in bubble sort:-
STEP 1
[1, 10, 9, 2, 8, 3, 7, 4, 6, 5]
STEP 2
[1, 2, 9, 10, 8, 3, 7, 4, 6, 5]
STEP 3
[1, 2, 3, 10, 8, 9, 7, 4, 6, 5]
STEP 4
[1, 2, 3, 4, 8, 9, 7, 10, 6, 5]
STEP 5
[1, 2, 3, 4, 5, 9, 7, 10, 6, 8]
STEP 6
[1, 2, 3, 4, 5, 6, 7, 10, 9, 8]
STEP 7
[1, 2, 3, 4, 5, 6, 7, 10, 9, 8]
STEP 8
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
STEP 9
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
STEP 10
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
The difference can be seen easily. In Selection Sort, generally the list became sorted in seven steps which are more than that of the Bubble Sort technique.
Source Codes (With Steps’ Printouts):-
About Possible Errors/Exceptions: The most common errors/exceptions which might occur during the execution of program are:-InputMismatchException: Thrown by a
Scanner to indicate that the token retrieved does not match the pattern for the expected type, or that the token is out of range for the expected type.NumberFormatException: Thrown to indicate that the application has attempted to convert a string to one of the numeric types, but that the string does not have the appropriate format.
ArrayIndexOutOfBoundsException: Thrown to indicate that an array has been accessed with an illegal index. The index is either negative or greater than or equal to the size of the array.
NullPointerException: Thrown when an application attempts to use null in a case where an object is required. These include:
- Calling the instance method of a null object.
- Accessing or modifying the field of a null object.
- Taking the length of null as if it were an array.
- Accessing or modifying the slots of null as if it were an array.
- Throwing null as if it were a Throwable value.
Applications should throw instances of this class to indicate other illegal uses of the null object. NullPointerException objects may be constructed by the virtual machine as if suppression were disabled and/or the stack trace was not writable.
(Note: If you want to catch multiple exceptions within a single catch block, you will have to get JDK (Java Development Kit) 1.6 or more. You can get it from the official Oracle’s web site, Go Now!)
Selection Sort Code:-
import java.util.*;
public class SelectionSort {
Scanner scan = new Scanner(System.in);
int list[] = new int[10];
int i, j, temp = 0, pos = 0, small = 0;
List<Integer> lst = new ArrayList<>();
public void input() {
try {
System.out.println("Enter 10 number list:- ");
for (i = 0; i < 10; i++) {
list[i] = scan.nextInt();
}
} catch (InputMismatchException | NumberFormatException | ArrayIndexOutOfBoundsException | NullPointerException e) {
System.err.println("Error Occur\n" + e.getMessage());
System.exit(0);
}
}
public void compute() {
for (i = 0; i < 10; i++) {
lst.clear();
small = list[i];
pos = i;
for (j = i + 1; j < 10; j++) {
if (small > list[j]) {
small = list[j];
pos = j;
}
}
temp = list[i];
list[i] = list[pos];
list[pos] = temp;
System.out.println("STEP " + (i + 1));
for (int k = 0; k < 10; k++) {
lst.add(list[k]);
}
System.out.println(lst);
System.out.println('\n');
}
}
public void display() {
System.out.println("Sorted List:-");
for (i = 0; i < 10; i++) {
System.out.println(list[i]);
}
}
public static void main(String[] args) {
SelectionSort ss = new SelectionSort();
ss.input();
ss.compute();
ss.display();
}
}
Bubble Sort Code:-
import java.util.*;
public class BubbleSort {
int list[] = new int[10];
int i = 0, j = 0, temp = 0;
List<Integer> lst = new ArrayList<>();
Scanner scan = new Scanner(System.in);
public void input() {
try {
System.out.println("Enter 10 number list: ");
for (i = 0; i < 10; i++) {
list[i] = scan.nextInt();
}
} catch (InputMismatchException | NumberFormatException | ArrayIndexOutOfBoundsException | NullPointerException e) {
System.err.println("Error Occur\n" + e.getMessage());
System.exit(0);
}
}
public void compute() {
for (i = 0; i < 10; i++) {
lst.clear();
for (j = 0; j < 10 - i - 1; j++) {
if (list[j + 1] < list[j]) {
temp = list[j + 1];
list[j + 1] = list[j];
list[j] = temp;
}
}
System.out.println("STEP " + (i + 1));
for (int k = 0; k < 10; k++) {
lst.add(list[k]);
}
System.out.println(lst);
System.out.println('\n');
}
}
public void display() {
System.out.println("Sorted List:-");
for (i = 0; i < 10; i++) {
System.out.println(list[i]);
}
}
public static void main(String[] args) {
BubbleSort bs = new BubbleSort();
bs.input();
bs.compute();
bs.display();
}
}
Comments