Sorting Algorithms - JAVA👽

 Sorting Algorithms - JAVA👽 

Sorting algorithms are used to arrange data into a specific pattern (ascending or descending).We mainly discuss 5 patterns in this blog.  We can use any of this methods to sort an array.
  • Selection sort
  • Insertion sort
  • Bubble sort
  • Merge sort
  • Quick sort 


Selection sort ...

Selection sort is well perform for small arrays and doesn't require extra temporary storage.  It uses selection method. It is poor to deal with huge list of items. It simple and easy to implement. It's time complexity is O(n^2) and space complexity is O(1).


Here is the basic code for selection sort.

for (int i=0; i< array.length-1; i++){
            int curruntMinimum = i;
            for (int curruntItem=i+1; curruntItem<array.length;curruntItem++){
                if(array[curruntItem] < array[curruntMinimum]){
                    curruntMinimum = curruntItem;
                }
            }
            if(i != curruntMinimum){
                int temp = array[i];
                array[i] = array[curruntMinimum];
                array[curruntMinimum] = temp;
            }
 }


Insertion sort ...

Insertion sort is well perform for small arrays and minimal storage is required.  It  twice faster than bubble sort. It does not deal  well with huge list of items. It is also
simple and easy to implement. It's time complexity is O(n^2) and space complexity is O(1) or O(n).
Here is the base code for insertion sort.

for (int elementIndex = 1; elementIndex < array.length; elementIndex++) {  
            int tempElement = array[elementIndex];
            int previousElementIndex = elementIndex - 1;

            while (previousElementIndex > -1 && array[] > tempElement) {
                array[previousElementIndex + 1] = array[previousElementIndex];
                previousElementIndex--;
            }

            array[previousElementIndex + 1] = tempElemnt;
}

Bubble sort ...

Insertion sort is well perform for small arrays and minimal storage is required.  It  twice faster than bubble sort. It does not deal  well with huge list of items. It is also
simple and easy to implement. It's time complexity is O(n^2) and space complexity is O(1) or O(n).


Here is the base code for bubble sort.

public static void sort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Swap elements 
int temp = arr[j]; 
arr[j] = arr[j + 1]; 
arr[j + 1] = temp; 
}
  }
}
}

Merge sort ...

Merge sort can be applied to files of any size and extra storage is required.  Merge sort follows divide and conquer approach in which, the list is first divided into the sets of equal elements and then each half of the list is sorted by using merge sort. The sorted list is combined again to from an elementary sorted array. It's time complexity is O(n log (n)) and space complexity is O(n).


Here is the base code for merge sort.

public static void sort(int[] arr, int left, int right) {
    if (left < right) {
      // Find the middle point
      int mid = left + (right - left) / 2;

      // Sort first and second halves
      sort(arr, left, mid);
      sort(arr, mid + 1, right);

      // Merge the sorted halves
      merge(arr, left, mid, right);
    }
  }

  private static void merge(int[] arr, int left, int mid, int right) {
    // Sizes of two subarrays
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // Create temporary arrays
    int[] leftArr = new int[n1];
    int[] rightArr = new int[n2];

    // Copy data to temporary arrays
    for (int i = 0; i < n1; i++) {
      leftArr[i] = arr[left + i];
    }
    for (int j = 0; j < n2; j++) {
      rightArr[j] = arr[mid + 1 + j];
    }

    // Merge the temporary arrays back into arr[left..right]
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
      if (leftArr[i] <= rightArr[j]) {
        arr[k] = leftArr[i];
        i++;
      } else {
        arr[k] = rightArr[j];
        j++;
      }
      k++;
    }

    // Copy the remaining elements of leftArr[] if there are any
    while (i < n1) {
      arr[k] = leftArr[i];
      i++;
      k++;
    }

    // Copy the remaining elements of rightArr[] if there are any
    while (j < n2) {
      arr[k] = rightArr[j];
      j++;
      k++;
    }
  }


Quick sort ...

Merge sort deals very well with large lists and extra storage is required. Quick sort is the most optimized sort algorithms which performs sorting in O(n log n) comparisons . Like Merge and Quick sort also work using divide and conquer approach. 

Here is the base code for quick sort.

static void quicksort(int[] arr, int start, int end ){

        int mid = (start+end)/2;
        int i = start;
        int j = end;
        int pivot = arr[mid];
        while (i<=j){
            while (arr[i] < pivot){
                i++;
            }
            while (arr[j]>pivot){
                j--;
            }
            if(i<=j){
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
                j--;

            }
        }

        if(start < j){
            quicksort(arr,start,j);
        }
        if(end>i){
            quicksort(arr,i,end);
        }

}

  

Comments

Post a Comment

Popular posts from this blog

Object Oriented Programming - JAVA- class boundary, variable types, modifiers, java main method

Image
Object Oriented Programming - JAVA👽 There are certain aspects of Object Oriented Programming. So when we use OOP we need to know about those elements. In this blog, Let's discuss about class, variables, modifiers and methods & main method . Class.... A class is a blueprint that defines common variables and methods for objects of a particular type. A class has a boundary. Inside this boundary we only have the class, constructor and main method. Even if a method is in the class, we cannot take it to the class boundary. Variables.... Variables   are used to store information to be referenced and manipulated in a computer program. There are two variable types. Static variable Non - static variable Static variable The easiest way to find static variable is to find out if there is a static key ward.      ex :         static int i ; These can be accessed anywhere within the class. It can be accessed even without creating an object. Non - ...
Read more

Object Oriented Programming - JAVA- Method Overriding

Image
Object Oriented Programming - JAVA👽 Sometimes we have to fetch the same method name more than once. It is not possible in the programming process. But we can use method override to solve that error. So, in this blog we will discuss Method Overriding. Method overriding ... In a method inherited from a super class to a subclass, the process of changing the body is called as method overriding. So, To overriding the classes should inherit with one class to another class. Ex:   class Monkey{   void climb(){   sout ("Monkey climbs with their legs on jumping");   }    }   class Man extends Monkey{   void climb(){   sout ("Man climbs with using ladder");   }   } Here, above the subclass is the method of the superclass, and above that is the method of the subclass. That means, according to the example code,  The method of Man class is at the top The method of Monkey class is next The Man class is below the method o...
Read more