Bubble Sort Algorithm
Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order. This algorithm is not suitable for large data sets as its average and worst-case time complexity are quite high.
We sort the array using multiple passes. After the first pass, the maximum element goes to end (its correct position). Same way, after second pass, the second largest element goes to second last position and so on.
In every pass, we process only those elements that have already not moved to correct position. After k passes, the largest k elements must have been moved to the last k positions.
In a pass, we consider remaining elements and compare all adjacent and swap if larger element is before a smaller element. If we keep doing this, we get the largest (among the remaining elements) at its correct position.
public class bubblesort {
public static void main(String[] args) {
int[] score = { 90, 80, 70, 60, 50 };
for (int j = 1; j < score.length; j++)// running 7 time
{
for (int i = 0; i < score.length - 1; i++) // j or 1 score.length-j change to index because index star from
// [0]
// why j order index--decrese when number order ex{80,70,60,50,80,90,90} then
// index decreaseex{80,70,60,50,80},
{
if (score[i] > score[i + 1])// 0>1,1>2,2>3,3>4
{
int temp = score[i];
score[i] = score[i + 1];
score[i + 1] = temp;
}
}
}
for (int i = 0; i < score.length; i++) {
System.out.print(score[i] + " ");
}
}
}
output:
50 60 70 80 90
Complexity Analysis of Bubble Sort:
Time Complexity: O(n2)
Auxiliary Space: O(1)
Advantages of Bubble Sort:
Bubble sort is easy to understand and implement.
It does not require any additional memory space.
It is a stable sorting algorithm, meaning that elements with the same key value maintain their relative order in the sorted output.
Disadvantages of Bubble Sort:
Bubble sort has a time complexity of O(n2) which makes it very slow for large data sets.
Bubble sort has almost no or limited real world applications. It is mostly used in academics to teach different ways of sorting.
Reference:https://www.geeksforgeeks.org/bubble-sort-algorithm/
Selection Sort
Selection Sort is a comparison-based sorting algorithm. It sorts an array by repeatedly selecting the smallest (or largest) element from the unsorted portion and swapping it with the first unsorted element. This process continues until the entire array is sorted.
First we find the smallest element and swap it with the first element. This way we get the smallest element at its correct position.
Then we find the smallest among remaining elements (or second smallest) and swap it with the second element.
We keep doing this until we get all elements moved to correct position.
Algorithm for Selection Sort
Implementation of Selection Sort in Java is mentioned below:
Step 1: Array arr with N size
Step 2: Initialise i=0
Step 3: If(i<N-1) Check for any element arr[j] where j>i and arr[j]<arr[i] then Swap arr[i] and arr[j]
Step 4: i=i+1 and Goto Step 3
Step 5: Exit
Complexity Analysis of Selection Sort
Time Complexity: O(n2) ,as there are two nested loops:
One loop to select an element of Array one by one = O(n)
Another loop to compare that element with every other Array element = O(n)
Therefore overall complexity = O(n) * O(n) = O(n*n) = O(n2)
**
Auxiliary Space:** O(1) as the only extra memory used is for temporary variables.
Advantages of Selection Sort
Easy to understand and implement, making it ideal for teaching basic sorting concepts.
Requires only a constant O(1) extra memory space.
It requires less number of swaps (or memory writes) compared to many other standard algorithms. Only cycle sort beats it in terms of memory writes. Therefore it can be simple algorithm choice when memory writes are costly.
Disadvantages of the Selection Sort
Selection sort has a time complexity of O(n^2) makes it slower compared to algorithms like Quick Sort or Merge Sort.
Does not maintain the relative order of equal elements which means it is not stable.
Applications of Selection Sort
Perfect for teaching fundamental sorting mechanisms and algorithm design.
Suitable for small lists where the overhead of more complex algorithms isn’t justified and memory writing is costly as it requires less memory writes compared to other standard sorting algorithms.
Complexity of the Above Method
Time Complexity: O(n2)
Auxiliary Space: O(1)
Reference:https://www.geeksforgeeks.org/java-program-for-selection-sort/
**Reference:https://www.geeksforgeeks.org/selection-sort-algorithm-2/
package afterfeb13;
public class selectionsort {
public static void main(String[] args) {
int[] score = { 90, 80, 70, 60, 50 };// {50,80,70,60,,,90}{50,60,70,80,90}
for (int j = 0; j < score.length - 1; j++)// index 4 value compare is enogh so -1
{
int big = 0, big_index = 0;
for (int i = 0; i < score.length - j; i++)// -j or 1 indicate index decrease for
// ex{80,70,60,50,90}--{70,60,50,80}
{
if (score[i] > big)// 90>0
{
big_index = i; // index[0]=90//index[1]=80//index[2]=70
big = score[i];// 90
}
}
System.out.println(big_index); // 0121 last indicate index[1]=60 no comapare 0 1 2 3 becase of
// j<score.length(4)
int len = score.length - (j + 1); // totalindex=4,length=5-(j+1)=4 90 go 4th index;length=5-(1+1)=80to
// 3index
// 2nd index 70
int temp = score[len]; // temp=4
score[len] = big; // big=0 len 4 to big o
score[big_index] = temp; // 4
}
for (int i = 0; i < score.length; i++)
System.out.print(score[i] + " ");
}
}
Output:
0
1
2
1
50 60 70 80 90
Order the number:
0,1,0,1,0,1,0,1
or(1,0,1,0,1,0,1,0)
package afterfeb13;
public class bubblesort {
public static void main(String[] args) {
int[] score = { 0,1,0,1,0,1,0,1 };
for (int j = 1; j < score.length; j++)// running 7 time
{
for (int i = 0; i < score.length - 1; i++) // j or 1 score.length-j change to index because index star from
// [0]
// why j order index--decrese when number order ex{80,70,60,50,80,90,90} then
// index decreaseex{80,70,60,50,80},
{
if (score[i] > score[i + 1])// 0>1,1>2,2>3,3>4
{
int temp = score[i];
score[i] = score[i + 1];
score[i + 1] = temp;
}
}
}
for (int i = 0; i < score.length; i++) {
System.out.print(score[i] + " ");
}
}
}
output:
0 0 0 0 1 1 1 1
Top comments (0)