I am writing here 3 Sorting algorithms for an Array/Collection elements:
1. Selection Sort
2. Exchange Sort (Also called Bubble Sort)
3. Insertion Sort.
Other two important sorting algorithms are Quick Sort and Merge Sort. Quick Sort I have discussed
at this link: http://www.deepakmodi2006.blogspot.in/2012/03/quicksort-in-java.html
However I have not written Merge Sort till now. Will write later.
If you already know the logics of Selection, Bubble and Insertion Sort, please go at the end
of the blog, a full program I have written in a very lucid manner else go line by line.
---------------------------------------------------
Selection Sort: In selection sort algorithm we find the minimum value in the array. First assign
minimum index in key (index_of_min=x). Then find the minimum value and assign the index of minimum
value in key (index_of_min=y). Then swap the minimum value with the value of minimum index.
At next iteration leave the value of minimum index position and sort the remaining values by following
same steps.
It is simplest algorithm.
Time efficiency:
The complexity of selection sort algorithm is in worst-case, average-case, and best-case run-time of O(n2),
assuming that comparisons can be done in constant time.
//sArray[]={4,5,3,2,6,1,7,8,9,4,7};
int temp;
for(int i=0; i<sArray.length-1; i++){
for(int j=i+1; j<sArray.length; j++){
if(sArray[i] > sArray[j]){
temp = sArray[i];
sArray[i] = sArray[j];
sArray[j] = temp;
}
}
}
---------------------------------------------------
Exchange Sort (Bubble sort) is a simplest sorting algorithm. The traversal logic is quite simple, please see
the code below. The algorithm follow the same steps repeatedly until the values of array is sorted.
In this algorithm we are comparing first two values and put the larger one at higher index. Then we take next
two values compare these values and place larger value at higher index. This process do iteratively until the
largest value is not reached at last index. Then start again from zero index up to n-1 index. The algorithm
follows the same steps iteratively unlit elements are not sorted.
Time efficiency:
In worst-case the complexity of bubble sort is O(n2).
//eArray[]={4,5,3,2,6,1,7,8,9,4,7};
temp=0;
for(int i=0; i<eArray.length-1; i++){
for(int j=0; j<(eArray.length-1)-i; j++){
if(eArray[j] > eArray[j+1]){
temp = eArray[j];
eArray[j] = eArray[j+1];
eArray[j+1] = temp;
}
}
}
---------------------------------------------------
Insertion sorting algorithm is similar to bubble sort. But insertion sort is more efficient than bubble
sort because in insertion sort the elements comparisons are less as compare to bubble sort.
In insertion sorting algorithm we compare one value until all the prior elements in Array are lesser.
This mean that the all previous values are lesser than compared value.
Insertion sort is a good choice for small values and for nearly-sorted values. There are more efficient
algorithms such as quick sort, heap sort, or merge sort for large values .
Positive feature of insertion sorting:
1.It is simple to implement.
2.It is efficient on (quite) small data values.
3.It is efficient on data sets which are already nearly sorted.
Time efficiency:
The complexity of insertion sorting is O(n) at best case of an already sorted array and O(n2) at worst case.
//iArray[]={4,5,3,2,6,1,7,8,9,4,7};
temp=0;
for(int i=1;i<iArray.length;i++){
int j = i;
temp=iArray[i]; //mark this element
while((j > 0) && (iArray[j-1] >= temp)){ //until element is smaller.
iArray[j] = iArray[j-1]; //shift them to right
j--; //Move one position left
}
iArray[j] = temp;
}
---------------------------------------------------
Complete program having all these Sorting Strategies:
//SortingProgram.java
public class SortingProgram {
public static void main(String[] args) {
//Array Used in Selection sort: sArray
//Array Used in Exchange (also called Bubble sort) sort: eArray
//Array Used in Insertion sort: iArray
int sArray[]={4,5,3,2,6,1,7,8,9,4,7};
int eArray[]={4,5,3,2,6,1,7,8,9,4,7};
int iArray[]={4,5,3,2,6,1,7,8,9,4,7};
//***********Selection sort logic starts here:
int temp;
System.out.println("Array elements before Selection sorting:");
for(int num:sArray)
System.out.print(num+", ");
for(int i=0; i<sArray.length-1; i++){
for(int j=i+1; j<sArray.length; j++){
if(sArray[i] > sArray[j]){
temp = sArray[i];
sArray[i] = sArray[j];
sArray[j] = temp;
}
}
}
System.out.println("\nArray elements After Selection sorting:");
for(int num:sArray)
System.out.print(num+", ");
//***********Exchange sort logic starts here:
//Showing ArrayElements again below for better visibility.
//eArray[]={4,5,3,2,6,1,7,8,9,4,7};
System.out.println("\nArray elements before Exchange sorting:");
for(int num:eArray)
System.out.print(num+", ");
temp=0;
for(int i=0; i<eArray.length-1; i++){
for(int j=0; j<(eArray.length-1)-i; j++){
if(eArray[j] > eArray[j+1]){
temp = eArray[j];
eArray[j] = eArray[j+1];
eArray[j+1] = temp;
}
}
}
System.out.println("\nArray elements After Exchange sorting:");
for(int num:eArray)
System.out.print(num+", ");
//***********Insertion sort logic starts here:
//Showing ArrayElements again below for better visibility.
//iArray[]={4,5,3,2,6,1,7,8,9,4,7};
System.out.println("\nArray elements before Insertion sorting:");
for(int num:iArray)
System.out.print(num+", ");
temp=0;
for(int i=1;i<iArray.length;i++){
int j = i;
temp=iArray[i]; //mark this element
while((j > 0) && (iArray[j-1] >= temp)){ //until element is smaller.
iArray[j] = iArray[j-1]; //shift them to right
j--; //Move one position left
}
iArray[j] = temp;
}
System.out.println("\nArray elements After Insertion sorting:");
for(int num:iArray)
System.out.print(num+", ");
}
}
//
//Output:
Array elements before Selection sorting:
4, 5, 3, 2, 6, 1, 7, 8, 9, 4, 7,
Array elements After Selection sorting:
1, 2, 3, 4, 4, 5, 6, 7, 7, 8, 9,
Array elements before Exchange sorting:
4, 5, 3, 2, 6, 1, 7, 8, 9, 4, 7,
Array elements After Exchange sorting:
1, 2, 3, 4, 4, 5, 6, 7, 7, 8, 9,
Array elements before Insertion sorting:
4, 5, 3, 2, 6, 1, 7, 8, 9, 4, 7,
Array elements After Insertion sorting:
1, 2, 3, 4, 4, 5, 6, 7, 7, 8, 9,
=============================END==========================
No comments:
Post a Comment