Sorting is nothing
but storage of data in sorted order, it can be in ascending or descending
order. The term Sorting comes into picture with the term Searching.
Sorting arranges data in a sequence which
makes searching easier. Every record which is going to be sorted will contain
one key. Based on the key the record will be sorted.
Sorting Efficiency
There are many
techniques for sorting. Implementation of particular sorting technique depends
upon situation. Sorting techniques mainly depends on two parameters. First
parameter is the execution time of program, which means time taken for
execution of program. Second is the space, which means space taken by the program?
Types of Sorting Techniques
1. Bubble
Sort
2. Insertion
Sort
3. Selection
Sort
4. Quick
Sort
5. Merge
Sort
6. Heap
Sort
Bubble Sort
In bubble sort we
compare the each element with all the element of the array. In one parse we get
the largest or shortest element of the array, it takes n iteration to sort one
element to sort all element n*n iteration takes place. So the worst case
complexity of bubble sort is O (N^2).
Code snippet
-
/**
* Bubble sorting implementation
* @author Manoj
*/
public class BubbleSortTest {
public static void bubbleSort(int arr[]) {
for (int outerCount = 0; outerCount < arr.length; outerCount++) {
for (int innerCount = outerCount + 1; innerCount < arr.length; innerCount++) {
if (arr[outerCount] > arr[innerCount]) {
arr[outerCount] = arr[outerCount] + arr[innerCount];
arr[innerCount] = arr[outerCount] - arr[innerCount];
arr[outerCount] = arr[outerCount] - arr[innerCount];
}
}
}
for (int count = 0; count < arr.length; count++) {
System.out.println(arr[count]);
}
}
public static void main(String args[]) {
int arr[] = {
1, 2, 9, 6, 3, 5 };
bubbleSort(arr);
}
}
Selection Sort
In this sorting technique, in each iteration we try to find the smallest element and swap this with starting elements (for ascending order), so again n elements are iterated over n loops so the complexity is O (n^2) but the advantage over bubble sort is it have maximum O (n) swaps while bubble sort have maximum O (n^2) .
Code Snippet-
/**
* Selection sort
* @author Manoj
*/
public class SelectionSortTest {
public static void sort(int arr[]) {
for (int outerCount = 0; outerCount < arr.length; outerCount++) {
int pos = outerCount;
for (int innerCount = outerCount + 1; innerCount < arr.length; innerCount++) {
if(arr[pos] > arr[innerCount]) {
pos = innerCount;
}
}
int smallerNumber = arr[pos];
arr[pos] = arr[outerCount];
arr[outerCount] = smallerNumber;
}
for (int count = 0; count < arr.length; count++) {
System.out.println(arr[count]);
}
}
public static void main(String args[]) {
int arr[] = {
1, 2, 9, 6, 3, 5 };
sort(arr);
}
}
Insertion Sort
In each iteration of insertion sort removes an element from the
array and insert this element into the correct position in already-sorted list,
until no input elements remain. The choice of which element to select from the
input is arbitrary, and can be made according to implementation.
Code snippet-
/**
*
Insertion sort implementation.
* @author Manoj
*/
public class InsertionSort {
public static void insertionSort(int array[]) {
int n = array.length;
for (int j = 1; j < n; j++) {
int key = array[j];
int i = j - 1;
while ((i > -1) && (array[i] > key)) {
array[i + 1] = array[i];
i--;
}
array[i + 1] = key;
}
}
public static void main(String a[]) {
int[] arr1 = { 9,
14, 3, 2, 43, 11, 58, 22 };
System.out.println("Before Insertion Sort");
for (int i : arr1) {
System.out.print(i + "
");
}
System.out.println();
insertionSort(arr1);//
sorting array using insertion sort
System.out.println("After Insertion Sort");
for (int i : arr1) {
System.out.print(i + "
");
}
}
}
Analysis – for first element suppose there is 1 comparison
and 1 movement similarly for N element there will be n comparison 2*(1+2+3…N-1)
= N*(N-1) – O (N^2)
Quick Sort
Quick Sort is a Divide and Conquer algorithm. It picks an element as
pivot put this pivot element to its correct location. This will divide the
array into two sub array one will contain all element smaller than pivot and
other will contain element than pivot, repeat this process recursively.
Code snippet-
/**
* Quick sort implementation
* @author Manoj
*/
public class QuickSort {
private int array[];
private int length;
public void sort(int[] inputArr) {
if (inputArr == null || inputArr.length == 0) {
return;
}
this.array = inputArr;
length = inputArr.length;
quickSort(0, length - 1);
}
private void quickSort(int lowerIndex, int higherIndex) {
int i = lowerIndex;
int j = higherIndex;
int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
while (i <= j) {
while (array[i] < pivot) {
i++;
}
while (array[j] > pivot) {
j--;
}
if (i <= j) {
exchangeNumbers(i, j);
i++;
j--;
}
}
if (lowerIndex < j)
quickSort(lowerIndex, j);
if (i < higherIndex)
quickSort(i, higherIndex);
}
private void exchangeNumbers(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public static void main(String a[]){
QuickSort sorter = new QuickSort();
int[] input = {1,5,2,9,4,2,10,25,12,12};
sorter.sort(input);
for(int i:input){
System.out.print(i);
System.out.print(" ");
}
}
}
Merge Sort
Merge sort first divides the array into
equal halves and then combines them in a sorted manner.
This technique is based on divide and
conquer approach. With worst-case time complexity Ο (n log n.
Code Snippet-
import java.util.*;
/**
* Merge sort
* @author Manoj
*
*/
public class MergeSort
{
public static void main(String[] args)
{
Integer[] a = { 2, 6, 3, 5, 1 };
mergeSort(a);
System.out.println(Arrays.toString(a));
}
@SuppressWarnings("rawtypes")
public static Comparable[] mergeSort(Comparable[] list)
{
if (list.length <= 1) {
return list;
}
Comparable[] first = new Comparable[list.length / 2];
Comparable[] second = new Comparable[list.length - first.length];
System.arraycopy(list, 0, first, 0, first.length);
System.arraycopy(list, first.length, second, 0, second.length);
mergeSort(first);
mergeSort(second);
merge(first, second, list);
return list;
}
@SuppressWarnings({ "rawtypes", "unchecked" })
private static void merge(Comparable[] first, Comparable[] second, Comparable[] result)
{
int iFirst = 0;
int iSecond = 0;
int iMerged = 0;
while (iFirst < first.length && iSecond < second.length)
{
if (first[iFirst].compareTo(second[iSecond]) < 0)
{
result[iMerged] = first[iFirst];
iFirst++;
}
else
{
result[iMerged] = second[iSecond];
iSecond++;
}
iMerged++;
}
System.arraycopy(first, iFirst, result, iMerged, first.length - iFirst);
System.arraycopy(second, iSecond, result, iMerged, second.length - iSecond);
}
}
Heap sort
Heap
sort is a comparison based sorting technique based on Binary Heap data
structure. It is similar to selection sort where we first find the maximum
element and place the maximum element at the end. We repeat the same process
for remaining element.
Time complexity of heap sort is O(Logn)
Code Snippet-
/**
* Heap sort
* @author Manoj
*/
public class HeapSort {
private static int N;
public static void sort(int arr[]) {
heapify(arr);
for (int i = N; i > 0; i--) {
swap(arr, 0, i);
N = N - 1;
maxheap(arr, 0);
}
}
public static void heapify(int arr[]) {
N = arr.length - 1;
for (int i = N / 2; i >= 0; i--)
maxheap(arr, i);
}
public static void maxheap(int arr[], int i) {
int left = 2 * i;
int right = 2 * i + 1;
int max = i;
if (left <= N && arr[left] > arr[i])
max = left;
if (right <= N && arr[right] > arr[max])
max = right;
if (max != i) {
swap(arr, i, max);
maxheap(arr, max);
}
}
public static void swap(int arr[], int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
@SuppressWarnings("resource")
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
System.out.println("Heap Sort Test\n");
int n, i;
System.out.println("Enter number of integer elements");
n = scan.nextInt();
int arr[] = new int[n];
System.out.println("\nEnter " + n + "
integer elements");
for (i = 0; i < n; i++) {
arr[i] = scan.nextInt();
}
sort(arr);
System.out.println("\nElements after sorting ");
for (i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
No comments:
Post a Comment