Sorting and Its types with Examples (Data Structure and Algorithm)

Sorting and Its types with Examples

Sorting is a method of arranging data in either increasing order or decreasing order. Several sorting algorithms are purposed. Sorting algorithm specifies the way to arrange data in a particular order. Most common orders are numerical or lexicographical order. Some of the well-known are as follows:

Insertion Sort:

In this method an element is selected from the list of elements, that element is inserted into its correct position by shifting other elements if necessary. The selection of elements is done one by one and are placed in their correct position. The time complexity of this algorithm is O(n²)

We can create a java program to sort array elements using insertion sort. Insertion is good for small elements only because it requires more time for sorting large number of elements.

Let's see a simple java program to sort an array using insertion sort algorithm.

public class InsertionSortExample {

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+" ");

}

Output:

Before Insertion Sort

9 14 3 2 43 11 58 22

After Insertion Sort

2 3 9 11 14 22 43 58

Selection Sort:

An maximum element is selected from the list of size n, that maximum element is swapped with the last element of the list of size n. Then second maximum element is selected from the list of size n-1, that second maximum element is swapped with last element of the list of size n-1. This selection of maximum element and swapping it with last element of the list of decreasing size continues until all the elements are selected and placed in their correct position. The time complexity of this algorithm is O(n²)

We can create a java program to sort array elements using selection sort. In selection sort algorithm, we search for the lowest element and arrange it to the proper location. We swap the current element with the next lowest number.

How does selection sort work?

The selection sort algorithm works in a very simple way. It maintains two subarray for the given array.

· The subarray is already sorted.
· And the second subarray is unsorted.

With every iteration of selection sort, an element is picked from the unsorted subarray and moved to the sorted subarray.

Selection Sort Java Example:

public class SelectionSortExample {

public static void selectionSort(int[] arr){

for (int i = 0; i < arr.length - 1; i++)

{

int index = i;

for (int j = i + 1; j < arr.length; j++){

if (arr[j] < arr[index]){

index = j;//searching for lowest index

}

int smallerNumber = arr[index];

arr[index] = arr[i];

arr[i] = smallerNumber;

}

public static void main(String a[]){

int[] arr1 = {9,14,3,2,43,11,58,22};

System.out.println("Before Selection Sort");

for(int i:arr1){

System.out.print(i+" ");

}

System.out.println();

selectionSort(arr1);//sorting array using selection sort

System.out.println("After Selection Sort");

for(int i:arr1){

System.out.print(i+" ");

}

Output:

Before Selection Sort

9 14 3 2 43 11 58 22

After Selection Sort

2 3 9 11 14 22 43 58

MergeSort:

MergeSort is based on divide and conquer algorithm. A array or list of size n is divided until n lists with one element is formed. Then those individual n lists are merged. First from n lists, two consecutive lists are considered, merged and sorted to form n/2 lists with two elements. Then two lists of two elements are merged and sorted to form total n/4 lists. This process will continue until one single sorted list is formed. The time complexity of this algorithm is O(nlogn)

Working of Merge sort Algorithm

Now, let's see the working of merge sort Algorithm.

To understand the working of the merge sort algorithm, let's take an unsorted array. It will be easier to understand the merge sort via an example.

Let the elements of array are -

According to the merge sort, first divide the given array into two equal halves. Merge sort keeps dividing the list into equal parts until it cannot be further divided.

As there are eight elements in the given array, so it is divided into two arrays of size 4.

Write a program to implement merge sort in Java.

class Merge {

/* Function to merge the subarrays of a[] */

void merge(int a[], int beg, int mid, int end)

{

int i, j, k;

int n1 = mid - beg + 1;

int n2 = end - mid;

/* temporary Arrays */

int LeftArray[] = new int[n1];

int RightArray[] = new int[n2];

/* copy data to temp arrays */

for (i = 0; i < n1; i++)

LeftArray[i] = a[beg + i];

for (j = 0; j < n2; j++)

RightArray[j] = a[mid + 1 + j];

i = 0; /* initial index of first sub-array */

j = 0; /* initial index of second sub-array */

k = beg; /* initial index of merged sub-array */

while (i < n1 && j < n2)

{

if(LeftArray[i] <= RightArray[j])

{

a[k] = LeftArray[i];

i++;

}

else

{

a[k] = RightArray[j];

j++;

}

k++;

}

while (i<n1)

{

a[k] = LeftArray[i];

i++;

k++;

}

while (j<n2)

{

a[k] = RightArray[j];

j++;

k++;

}

void mergeSort(int a[], int beg, int end)

{

if (beg < end)

{

int mid = (beg + end) / 2;

mergeSort(a, beg, mid);

mergeSort(a, mid + 1, end);

merge(a, beg, mid, end);

}

/* Function to print the array */

void printArray(int a[], int n)

{

int i;

for (i = 0; i < n; i++)

System.out.print(a[i] + " ");

}

public static void main(String args[])

{

int a[] = { 11, 30, 24, 7, 31, 16, 39, 41 };

int n = a.length;

Merge m1 = new Merge();

System.out.println("\nBefore sorting array elements are - ");

m1.printArray(a, n);

m1.mergeSort(a, 0, n - 1);

System.out.println("\nAfter sorting array elements are - ");

m1.printArray(a, n);

System.out.println("");

}

Output:

Before sorting array elements are -

11 30 24 7 31 16 39 41

After sorting array elements are -

7 11 16 24 30 31 39 41

Quick Sort:

Quicksort is based on the concept of divide and conquer algorithm. One of the element of a list of size n is considered as pivot, elements smaller than that pivot is placed at the left side of the pivot, elements greater than or equal to the pivot are placed at the right of the pivot in the list. In this way two sublists are formed, one at the left of the pivot, another at the right of the pivot. This selection of pivot, placing smaller elements in the left of the pivot and greater or equal elements in the right of the pivot is continued with all the formed sub-list. In this way list is sorted. The time complexity of this algorithm is O(nlogn)

Write a program to implement quicksort in Java.

public class Quick

{

/* function that consider last element as pivot,

place the pivot at its exact position, and place

smaller elements to left of pivot and greater

elements to right of pivot. */

int partition (int a[], int start, int end)

{

int pivot = a[end]; // pivot element

int i = (start - 1);

for (int j = start; j <= end - 1; j++)

{

// If current element is smaller than the pivot

if (a[j] < pivot)

{

i++; // increment index of smaller element

int t = a[i];

a[i] = a[j];

a[j] = t;

}

int t = a[i+1];

a[i+1] = a[end];

a[end] = t;

return (i + 1);

}

/* function to implement quick sort */

void quick(int a[], int start, int end) /* a[] = array to be sorted, start = Starting index, end = Ending index */

{

if (start < end)

{

int p = partition(a, start, end); //p is partitioning index

quick(a, start, p - 1);

quick(a, p + 1, end);

}

/* function to print an array */

void printArr(int a[], int n)

{

int i;

for (i = 0; i < n; i++)

System.out.print(a[i] + " ");

}

public static void main(String[] args) {

int a[] = { 13, 18, 27, 2, 19, 25 };

int n = a.length;

System.out.println("\nBefore sorting array elements are - ");

Quick q1 = new Quick();

q1.printArr(a, n);

q1.quick(a, 0, n - 1);

System.out.println("\nAfter sorting array elements are - ");

q1.printArr(a, n);

System.out.println();

}

Output:

Before sorting array elements are -

13 18 27 2 19 25

After sorting array elements are -

2 13 18 19 25 27

Heap Sort:

The largest element of the list is determined and placed in the end of the list. This is continued until all the elements are placed in their correct position. Heap sort is better than selection sort, it uses a data structure called heap (a binary tree). Heap tree is from with the list of the data and element from the root are taken out and placed in the array, as, element of heap tree is removed from the root of the heap, and the properties of the heap is maintained with each element removal. The time complexity of this algorithm is O(nlogn)

Heap sort basically recursively performs two main operations -

Build a heap H, using the elements of array.
Repeatedly delete the root element of the heap formed in 1st phase.

Before knowing more about the heap sort, let's first see a brief description of Heap.

Write a program to implement heap sort in Java.

class HeapSort

{

/* function to heapify a subtree. Here 'i' is the

index of root node in array a[], and 'n' is the size of heap. */

static void heapify(int a[], int n, int i)

{

int largest = i; // Initialize largest as root

int left = 2 * i + 1; // left child

int right = 2 * i + 2; // right child

// If left child is larger than root

if (left < n && a[left] > a[largest])

largest = left;

// If right child is larger than root

if (right < n && a[right] > a[largest])

largest = right;

// If root is not largest

if (largest != i) {

// swap a[i] with a[largest]

int temp = a[i];

a[i] = a[largest];

a[largest] = temp;

heapify(a, n, largest);

}

/*Function to implement the heap sort*/

static void heapSort(int a[], int n)

{

for (int i = n / 2 - 1; i >= 0; i--)

heapify(a, n, i);

// One by one extract an element from heap

for (int i = n - 1; i >= 0; i--) {

/* Move current root element to end*/

// swap a[0] with a[i]

int temp = a[0];

a[0] = a[i];

a[i] = temp;

heapify(a, i, 0);

}

/* function to print the array elements */

static void printArr(int a[], int n)

{

for (int i = 0; i < n; ++i)

System.out.print(a[i] + " ");

}

public static void main(String args[])

{

int a[] = {45, 7, 20, 40, 25, 23, -2};

int n = a.length;

System.out.print("Before sorting array elements are - \n");

printArr(a, n);

heapSort(a, n);

System.out.print("\nAfter sorting array elements are - \n");

printArr(a, n);

}

Output:

Before sorting array elements are -

45 7 20 40 25 23 -2

After sorting array elements are -

-2 7 20 23 25 40 45

Sorting and Its types with Examples (Data Structure and Algorithm)

Post a Comment

Contact Form