# 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

You must be logged in to post a comment.