java/sorting/Cyclesort.java at master · AllAlgorithms/java · GitHub

This repository was archived by the owner on Sep 7, 2025. It is now read-only.

History

82 lines (69 loc) · 1.78 KB

Raw

// Java program to impleament cycle sort

import java.util.*;

import java.lang.*;

class Cyclesort

{

// Function sort the array using Cycle sort

public static void cycleSort (int arr[], int n)

{

// count number of memory writes

int writes = 0;

// traverse array elements and put it to on

// the right place

for (int cycle_start=0; cycle_start<=n-2; cycle_start++)

{

// initialize item as starting point

int item = arr[cycle_start];

// Find position where we put the item. We basically

// count all smaller elements on right side of item.

int pos = cycle_start;

for (int i = cycle_start+1; i<n; i++)

if (arr[i] < item)

pos++;

// If item is already in correct position

if (pos == cycle_start)

continue;

// ignore all duplicate elements

while (item == arr[pos])

pos += 1;

// put the item to it's right position

if (pos != cycle_start)

{

int temp = item;

item = arr[pos];

arr[pos] = temp;

writes++;

}

// Rotate rest of the cycle

while (pos != cycle_start)

{

pos = cycle_start;

// Find position where we put the element

for (int i = cycle_start+1; i<n; i++)

if (arr[i] < item)

pos += 1;

// ignore all duplicate elements

while (item == arr[pos])

pos += 1;

// put the item to it's right position

if (item != arr[pos])

{

int temp = item;

item = arr[pos];

arr[pos] = temp;

writes++;

}

// Driver program to test above function

public static void main(String[] args)

{

int arr[] = {1, 8, 3, 9, 10, 10, 2, 4 };

int n = arr.length;

cycleSort(arr, n) ;

System.out.println("After sort : ");

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

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

}

java/sorting/Cyclesort.java at master · AllAlgorithms/java · GitHub

Uh oh!

Expand file tree

Breadcrumbs

Cyclesort.java

Latest commit

History

Breadcrumbs

Cyclesort.java

File metadata and controls