In this section let's look into the implementation of basic sorting algorithms in java.
In today's world of computer science, sorting is a basic operation which is unavoidable. Whatever may be the application you work on, sorting of data will be the preliminary operation that one would be required to do. Here we will stick only to integer sorting.
The following java program is self explanatory with necessary comments. It contains a set of methods implementing various sorting algorithms to sort integer values in ascending order.
The algorithms implemented here are bubble sort, selection sort, insertion sort, quick sort and heap sort. OK! Which is the best sorting algorithm?
The answer depends on the data set used. If the data set is less (say 10 values) then bubble sort (or selection sort) will work fine. In other case if there is a huge data set to be sorted (say 1000 values) then quick or heap sort will do best as the complexity is 0(nlogn).
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS''
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
* TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE IS DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS
* BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
* POSSIBILITY OF SUCH DAMAGE.
*/
package in.techdive.java.examples;
/**
* This class contains implementation methods for basic sorting algorithms
*/
public class SortingAlgorithms
{
public SortingAlgorithms()
{
}
public static void main(String[] args)
{
SortingAlgorithms p = new SortingAlgorithms();
int a[] = new int[] { 0, 15, 61, 1, 42, 100, 5, 6, 13, 2, 8, 9, 7, 3,
11, 74, 19, 12 };
/* Bubble Sort */
System.out.println("Bubble Sort ");
System.out.println("Input Array: ");
p.printArr(a);
p.bubbleSort(a);
System.out.println();
System.out.println("Output Array: ");
p.printArr(a);
/* Selection Sort */
System.out.println("\n\nSelection Sort ");
a = new int[] { 0, 2, 8, 9, 7, 3, 11, 74, 19, 12 };
System.out.println("Input Array: ");
p.printArr(a);
p.selectionSort(a);
System.out.println();
System.out.println("Output Array: ");
p.printArr(a);
/* Insertion Sort */
System.out.println("\n\nInsertion Sort ");
a = new int[] { 8, 9, 7, 3, 11, 74, 19, 12 };
System.out.println("Input Array: ");
p.printArr(a);
p.insertionSort(a);
System.out.println();
System.out.println("Output Array: ");
p.printArr(a);
/* Quick Sort */
System.out.println("\n\nQuick Sort ");
a = new int[] { 0, 15, 61, 1, 42, 100, 5, 6, 13, 2, 8, 11, 74, 19, 12 };
System.out.println("Input Array: ");
p.printArr(a);
p.quickSort(a, 0, a.length);
System.out.println();
System.out.println("Output Array: ");
p.printArr(a);
/* Heap Sort */
System.out.println("\n\nHeap Sort ");
System.out.println("Input Array: ");
a = new int[] { 81, 0, 15, 61, 1, 42, 100, 5, 6, 13, 2, 8, 11, 74, 19,
12 };
p.printArr(a);
p.heapSort(a);
System.out.println();
System.out.println("Output Array: ");
p.printArr(a);
/* Merge Sort */
System.out.println("\n\nMerge Sort ");
System.out.println("Input Arrays: ");
System.out.println("First Array : ");
p.printArr(a);
System.out.println();
System.out.println("Second Array : ");
int[] b = new int[] { 8, 9, 7, 3, 11, 74, 19, 12 };
p.printArr(b);
System.out.println();
System.out.println("Output Array: ");
p.printArr(p.mergeSort(a, b));
}
/**
* This method sorts the array passed as parameter using Selection Sort algorithm.
* The complexity is 0(n*n), where n is the number of elements to be sorted
*/
public void selectionSort(int[] a)
{
for (int i = 0; i < a.length; i++)
{
for (int j = i + 1; j < a.length; j++)
{
if (a[i] > a[j])
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
}
/**
* This method sorts the array passed as parameter using bubble sort algorithm.
* The complexity is 0(n*n), where n is the number of elements to be sorted
*/
public void bubbleSort(int[] a)
{
int pass = 0;
for (int i = 0; i < a.length; i++)
{
pass = 0;
for (int m = 0; m < a.length - 1; m++)
{
if (a[m] > a[m + 1])
{
int temp = a[m];
a[m] = a[m + 1];
a[m + 1] = temp;
pass++;
}
}
if (pass == 0)
break;
}
}
/**
* This method sorts the array passed as parameter using insertion sort algorithm.
* The complexity is 0(n*n), where n is the number of elements to be sorted
*/
public void insertionSort(int[] a)
{
int min = a[0];
int z = 0;
for (int i = 1; i < a.length; i++)
{
if (min > a[i])
{
min = a[i];
z = i;
}
}
int temp = a[0];
a[0] = a[z];
a[z] = temp;
for (int i = 2; i < a.length; i++)
{
int x = a[i];
int k = i - 1;
while (k > 0 && x < a[k])
{
k--;
}
if (k + 1 == i)
{
continue;
}
else
{
for (int m = k + 1; m <= i; m++)
{
int tmp = a[m];
a[m] = x;
x = tmp;
}
}
}
}
/**
* This method sorts the array passed as parameter using Quick sort algorithm in a recursive manner.
* The complexity is nlog(n), where n is the number of elements to be sorted
*/
public void quickSort(int[] a, int lowLim, int upperLim)
{
if (lowLim != upperLim)
{
int s = partitionArr(a, lowLim, upperLim);
if (s <= 0)
{
return;
}
if (s > ((upperLim) - s))
{
quickSort(a, lowLim + s, upperLim);
quickSort(a, lowLim, lowLim + (s));
return;
}
else
{
quickSort(a, lowLim, lowLim + (s));
quickSort(a, lowLim + s, upperLim);
return;
}
}
return;
}
/**
* This method partitions a given array in to two based on (middle=(lowlim+upperlim)/2) value, in such a way that
* first part of the array contains elements < middle value and second part of the array contains values < middle
* value. It is used by quick sort algorithm.
*/
public int partitionArr(int[] a, int lowLim, int upperLim)
{
int x = lowLim;
int y = upperLim - 1;
if (x == y)
{
return 0;
}
if (y <= 0)
{
return 0;
}
int c = 0;
if (x == y)
{
return 0;
}
int k = a[(x + y) / 2];
for (int i = lowLim; i < upperLim; i++)
{
if (a[i] <= k)
c++;
}
int m = lowLim + c;
while (x <= m && x < a.length)
{
if (a[x] >= k)
{
y = upperLim - 1;
while (y > x)
{
if (a[y] <= k)
{
int t = a[y];
a[y] = a[x];
a[x] = t;
break;
}
y--;
}
}
x++;
}
return c;
}
/**
* This method sorts the array passed as parameter using Heap sort algorithm.
* The complexity is nlog(n), where n is the number of elements to be sorted
*/
public void heapSort(int[] a)
{
int n = a.length;
boolean swap = true;
int k = n;
for (int i = 0; i < n; i++)
{
while (swap == true)
{
swap = false;
for (int j = 0; j < k; j++)
{
if (((2 * j) + 1) < k && a[j] < a[(2 * j) + 1])
{
swapElem(a, j, (2 * j) + 1);
swap = true;
}
if (((2 * j) + 2) < k && a[j] < a[(2 * j) + 2])
{
swapElem(a, j, (2 * j) + 2);
swap = true;
}
}
}
swapElem(a, 0, k - 1);
k = k - 1;
swap = true;
}
}
public void swapElem(int[] a, int g, int h)
{
int temp = a[g];
a[g] = a[h];
a[h] = temp;
}
/**
* This method merges two sorted arrays passed as parameter using Merge sort algorithm
*/
public int[] mergeSort(int[] firstArr, int[] secondArr)
{
int[] finalArr = new int[firstArr.length + secondArr.length];
for (int i = 0; i < firstArr.length; i++)
{
finalArr[i] = firstArr[i];
}
for (int i = 0; i < secondArr.length; i++)
{
addElement(finalArr, secondArr[i], firstArr.length + i);
}
return finalArr;
}
public void addElement(int[] finalArr, int insElement, int len)
{
int lowerLimit = 0;
int upperLimit = len - 1;
while ((lowerLimit + 1) != upperLimit)
{
int middle = (lowerLimit + upperLimit) / 2;
if (insElement > finalArr[middle])
{
lowerLimit = middle;
}
else
{
upperLimit = middle;
}
}
if (finalArr[lowerLimit] > insElement)
{
if (lowerLimit == 0)
insertElement(finalArr, insElement, lowerLimit, len + 1);
else
insertElement(finalArr, insElement, lowerLimit - 1, len + 1);
}
else
{
insertElement(finalArr, insElement, lowerLimit + 1, len + 1);
}
}
public void insertElement(int[] finalArr, int insElement, int pos, int len)
{
int addElem = insElement;
for (int i = pos; i < len; i++)
{
int temp = finalArr[i];
finalArr[i] = addElem;
addElem = temp;
}
}
public void printArr(int[] a)
{
for (int i = 0; i < a.length; i++)
{
System.out.print(a[i] + " ");
}
}
}
Ok here is the sample output
Input Array:
0 15 61 1 42 100 5 6 13 2 8 9 7 3 11 74 19 12
Output Array:
0 1 2 3 5 6 7 8 9 11 12 13 15 19 42 61 74 100
Selection Sort
Input Array:
0 2 8 9 7 3 11 74 19 12
Output Array:
0 2 3 7 8 9 11 12 19 74
Insertion Sort
Input Array:
8 9 7 3 11 74 19 12
Output Array:
3 7 8 9 11 12 19 74
Quick Sort
Input Array:
0 15 61 1 42 100 5 6 13 2 8 11 74 19 12
Output Array:
0 1 2 5 6 8 11 12 13 15 19 42 61 74 100
Heap Sort
Input Array:
81 0 15 61 1 42 100 5 6 13 2 8 11 74 19 12
Output Array:
0 1 2 5 6 8 11 12 13 15 19 42 61 74 81 100
Merge Sort
Input Arrays:
First Array :
0 1 2 5 6 8 11 12 13 15 19 42 61 74 81 100
Second Array :
8 9 7 3 11 74 19 12
Output Array:
0 1 2 3 5 6 7 8 8 9 11 11 12 12 13 15 19 19 42 61 74 74 81 100
Choose the best sorting algorithm as per you requirement.
Fine... what about sorting in reverse order(or descending order). Hope it would be really simple enough to tweak the below algorithms to change to descending order, try your hand at it! Happy Sorting :)
For Further Study