Cycle Sorting in Java

Hello guys, today we are going to learn about implementing cycle sorting in Java.

Cycle Sorting is the process of arranging data items into some specific pattern. There are different techniques of sorting algorithms with different time and space complexity. Cycle Sorting is a type of in-place sorting algorithm which means it doesn’t take extra space. It is unstable and mostly, it is divided into a number of cycles where it operates to rotate in order to produce the sorted array.

Algorithm

Below is given the algorithm for Cycle Sorting in Java programming:

  • Start
  • First, take an input an array of n different element’s
  • In addition, to start a loop through the elements for comparing and assign a position variable in order to specify the exact location.
  • At the specific element of an array, just count the number of elements that are smaller than the present element.
  • If the present algorithm will help the element at a given index is available to be at its correct position then leave it.
  • If not then find the correct position by counting a number of elements moreover, its present element to specify the exact position where it should be placed.
  • And the other element is replaced with the moved one then the process will continue until it gets into the right place by rotating the array usually.
  • Above all, If there are duplicate elements then it will skip and the rest of other operations will perform.
  • End
import java.util.*;
public class CycleSort{  
        public static int[] rotate(int position,int element,int array[],int strt){
            while (position != strt) 
       { 
      position = strt; 
                        for (int i = strt+1; i<array.length; i++) 
                            if (array[i] < element)
                                position += 1; 
                        while(element == array[position])
                            position += 1; 
                        if(element != array[position]) 
                            { 
        int temp = element; 
        element = array[position]; 
        array[position] = temp; 				
                            } 
      } 
            return array;
        }
      
    public static void main(String args[]){  
        Scanner in = new Scanner(System.in);
        System.out.println("Enter the number of elements you want to add : ");
        int n=in.nextInt();
        System.out.println("Enter all the elements : ");
        int a[]=new int[n];
        for(int i=0;i<n;i++){
            a[i]=in.nextInt();
        } 
       
        System.out.print("Before Sorting : "); 
            for (int i =0; i<n; i++) 
    System.out.print(a[i] + " "); 
  
        System.out.println();
        int writes = 0; 
        for (int strt=0; strt<=n-2; strt++) 
  { 
            int element = a[strt]; 
            int position = strt; 
      for (int i = strt+1; i<n; i++) 
    if (a[i] < element)
                    position++; 
   
            if (position == strt) 
    continue; 	
            while (element == a[position]) 
    position += 1; 		
            if (position != strt) 
                { 
                    int temp = element; 
      element = a[position]; 
      a[position] = temp; 	
    } 
            rotate( position, element, a, strt);
      System.out.print("After Sorting  : "); 
            for (int i =0; i<n; i++) 
    System.out.print(a[i] + " "); 
  }
    }
}


OUTPUT

Enter the number of elements you want to add :
5
Enter all the elements :
0 122 12 434 5
Before Sorting : 0 122 12 434 5
After Sorting : 0 5 12 122 434

Cycle sorting time and space complexity analysis

  • Average time complexity – O(n^2)
  • Best-Case time complexity – O(n^2)
  • Worst-Case time complexity – O(n^2)
  • Space Complexity -O(1)
  • Worst-case space complexity – O(n)

In conclusion, Cycle Sorting is well efficient mostly to demonstrate situations where memory write or swap operations are costly.

Summary Points

  • In-place
  • Unstable
  • Tasks divide into a number of cycles
  • Mostly it takes a minimum number of writes to the memory
  • It helps in swap operations and analyzes them.

 

 

Leave a Reply