Skip to main content

Cycle Sort

Cycle Sort is an in-place, comparison-based sorting algorithm that is highly efficient in terms of time complexity, especially for situations where memory writes are more expensive than memory reads. It was developed in 1960 by W. D. Frazer and A. C. McKellar.

The basic idea behind Cycle Sort is to minimize the number of writes to memory by moving each element of the input list to its correct position in the sorted order, one at a time. It does this by repeatedly finding the correct position of the current element and then swapping it with the element at that position. This process is repeated until all elements are in their correct positions.

The algorithm is called "Cycle Sort" because it works by finding cycles in the permutation of the input list. A cycle is a sequence of elements that can be moved to their correct positions by just one swap.

The key advantage of Cycle Sort over other sorting algorithms is that it minimizes the number of writes to memory. This makes it ideal for situations where writes to memory are expensive, such as in embedded systems, or when sorting large datasets that don't fit entirely in memory.

The time complexity of Cycle Sort is O(n^2), but in practice, it performs much better than other O(n^2) algorithms such as Bubble Sort, Selection Sort, or Insertion Sort, especially when the input list is partially sorted or contains a small number of unique elements.

Here given code implementation process.

// C Program 
// Sort array elements by using Cycle Sort
#include <stdio.h>

//Function which is display array elements
void display(int arr[], int size)
{
	for (int i = 0; i < size; ++i)
	{
		printf("  %d", arr[i]);
	}
	printf("\n");
}
// When given item is not sorted of given array in right side 
// then they are returns new location of right side. 
// Otherwise they returns current location
int valid_position(int arr[], int cycle_start, int item, int size)
{
	int pos = cycle_start;
	//loop controlling variable
	int i = cycle_start + 1;
	while (i < size)
	{
		if (arr[i] < item)
		{
			//Find new position of current cycle element
			pos++;
		}
		i++;
	}
	return pos;
}
//This are used to find the location of next different element
int skip_duplicates(int arr[], int location, int item)
{
	int pos = location;
	//Skip similar elements
	while (item == arr[pos])
	{
		pos++;
	}
	return pos;
}
//Perform the cycle sort in given array
void cycle_sort(int arr[], int size)
{
	// Loop controlling variables
	int pos = 0;
	int item = 0;
	int temp = 0;
	int cycle_start = 0;
	// count number of memory writes operation 
	int writes = 0;
	for (cycle_start = 0; cycle_start < size - 1; cycle_start++)
	{
		//Get current cycle element
		item = arr[cycle_start];
		//Find actual valid location
		pos = valid_position(arr, cycle_start, item, size);
		//Check whether given current cycle elements is need to modified or not
		if (pos != cycle_start)
		{
			pos = skip_duplicates(arr, pos, item);
			if (item != arr[pos])
			{
				//When new location element are different to current cycle element
				temp = arr[pos];
				arr[pos] = item;
				item = temp;
				writes++;
			}
			while (pos != cycle_start)
			{
				//Find actual valid location
				pos = valid_position(arr, cycle_start, item, size);
				pos = skip_duplicates(arr, pos, item);
				if (item != arr[pos])
				{
					temp = arr[pos];
					arr[pos] = item;
					item = temp;
					writes++;
				}
			}
		}
	}
}
int main()
{
	//Define an sorted array of integers
	int arr[] = {
		11,
		8,
		3,
		8,
		32,
		-3,
		1,
		9,
		23,
		2,
		4,
		0,
		5
	};
	//Get the size of array
	int size = sizeof(arr) / sizeof(arr[0]);
	//Before sort
	printf("\n  Before Sort  :\n");
	display(arr, size);
	//Sort element
	cycle_sort(arr, size);
	//After sort
	printf("\n  After Sort  :\n");
	display(arr, size);
	return 0;
}

Output

  Before Sort  :
  11  8  3  8  32  -3  1  9  23  2  4  0  5

  After Sort  :
  -3  0  1  2  3  4  5  8  8  9  11  23  32
/*
	Java Program
	Sort array elements by using Cycle Sort
*/
class MySort
{
	//Function which is display array elements
	public void display(int[] arr, int size)
	{
		for (int i = 0; i < size; ++i)
		{
			System.out.print(" " + arr[i]);
		}
		System.out.print("\n");
	}
	// When given item is not sorted of given array in right side 
	// then they are returns new location of right side. 
	// Otherwise they returns current location
	public int valid_position(int[] arr, int cycle_start, int item, int size)
	{
		int pos = cycle_start;
		//loop controlling variable
		int i = cycle_start + 1;
		while (i < size)
		{
			if (arr[i] < item)
			{
				//Find new position of current cycle element
				pos++;
			}
			i++;
		}
		return pos;
	}
	//This are used to find the location of next different element
	public int skip_duplicates(int[] arr, int location, int item)
	{
		int pos = location;
		//Skip similar elements
		while (item == arr[pos])
		{
			pos++;
		}
		return pos;
	}
	//Perform the cycle sort in given array
	public void cycle_sort(int[] arr, int size)
	{
		// Loop controlling variables
		int pos = 0;
		int item = 0;
		int temp = 0;
		int cycle_start = 0;
		// count number of memory writes operation 
		int writes = 0;
		for (cycle_start = 0; cycle_start < size - 1; cycle_start++)
		{
			//Get current cycle element
			item = arr[cycle_start];
			//Find actual valid location
			pos = valid_position(arr, cycle_start, item, size);
			//Check whether given current cycle elements is need to modified or not
			if (pos != cycle_start)
			{
				pos = skip_duplicates(arr, pos, item);
				if (item != arr[pos])
				{
					//When new location element are different to current cycle element
					temp = arr[pos];
					arr[pos] = item;
					item = temp;
					writes++;
				}
				while (pos != cycle_start)
				{
					//Find actual valid location
					pos = valid_position(arr, cycle_start, item, size);
					pos = skip_duplicates(arr, pos, item);
					if (item != arr[pos])
					{
						temp = arr[pos];
						arr[pos] = item;
						item = temp;
						writes++;
					}
				}
			}
		}
	}
	public static void main(String[] args)
	{
		MySort obj = new MySort();
		//Define an sorted array of integers
		int[] arr = {
			11,
			8,
			3,
			8,
			32,
			-3,
			1,
			9,
			23,
			2,
			4,
			0,
			5
		};
		//Get the size of array
		int size = arr.length;
		System.out.print("\n Before Sort :\n");
		obj.display(arr, size);
		//Sort element
		obj.cycle_sort(arr, size);
		System.out.print("\n After Sort :\n");
		obj.display(arr, size);
	}
}

Output

 Before Sort :
 11 8 3 8 32 -3 1 9 23 2 4 0 5

 After Sort :
 -3 0 1 2 3 4 5 8 8 9 11 23 32
//Include header file
#include <iostream>

using namespace std;
/*
	C++ Program
	Sort array elements by using Cycle Sort
*/
class MySort
{
	public:
		//Function which is display array elements
		void display(int arr[], int size)
		{
			for (int i = 0; i < size; ++i)
			{
				cout << " " << arr[i];
			}
			cout << "\n";
		}
	// When given item is not sorted of given array in right side 
	// then they are returns new location of right side. 
	// Otherwise they returns current location
	int valid_position(int arr[], int cycle_start, int item, int size)
	{
		int pos = cycle_start;
		//loop controlling variable
		int i = cycle_start + 1;
		while (i < size)
		{
			if (arr[i] < item)
			{
				//Find new position of current cycle element
				pos++;
			}
			i++;
		}
		return pos;
	}
	//This are used to find the location of next different element
	int skip_duplicates(int arr[], int location, int item)
	{
		int pos = location;
		//Skip similar elements
		while (item == arr[pos])
		{
			pos++;
		}
		return pos;
	}
	//Perform the cycle sort in given array
	void cycle_sort(int arr[], int size)
	{
		// Loop controlling variables
		int pos = 0;
		int item = 0;
		int temp = 0;
		int cycle_start = 0;
		// count number of memory writes operation 
		int writes = 0;
		for (cycle_start = 0; cycle_start < size - 1; cycle_start++)
		{
			//Get current cycle element
			item = arr[cycle_start];
			//Find actual valid location
			pos = this->valid_position(arr, cycle_start, item, size);
			//Check whether given current cycle elements is need to modified or not
			if (pos != cycle_start)
			{
				pos = this->skip_duplicates(arr, pos, item);
				if (item != arr[pos])
				{
					//When new location element are different to current cycle element
					temp = arr[pos];
					arr[pos] = item;
					item = temp;
					writes++;
				}
				while (pos != cycle_start)
				{
					//Find actual valid location
					pos = this->valid_position(arr, cycle_start, item, size);
					pos = this->skip_duplicates(arr, pos, item);
					if (item != arr[pos])
					{
						temp = arr[pos];
						arr[pos] = item;
						item = temp;
						writes++;
					}
				}
			}
		}
	}
};
int main()
{
	MySort obj = MySort();
	int arr[] = {
		11 , 8 , 3 , 8 , 32 , -3 , 1 , 9 , 23 , 2 , 4 , 0 , 5
	};
	//Get the size of array
	int size = sizeof(arr) / sizeof(arr[0]);
	cout << "\n Before Sort :\n";
	obj.display(arr, size);
	//Sort element
	obj.cycle_sort(arr, size);
	cout << "\n After Sort :\n";
	obj.display(arr, size);
	return 0;
}

Output

 Before Sort :
 11 8 3 8 32 -3 1 9 23 2 4 0 5

 After Sort :
 -3 0 1 2 3 4 5 8 8 9 11 23 32
//Include namespace system
using System;
/*
	C# Program
	Sort array elements by using Cycle Sort
*/
class MySort
{
	//Function which is display array elements
	public void display(int[] arr, int size)
	{
		for (int i = 0; i < size; ++i)
		{
			Console.Write(" " + arr[i]);
		}
		Console.Write("\n");
	}
	// When given item is not sorted of given array in right side 
	// then they are returns new location of right side. 
	// Otherwise they returns current location
	public int valid_position(int[] arr, int cycle_start, int item, int size)
	{
		int pos = cycle_start;
		//loop controlling variable
		int i = cycle_start + 1;
		while (i < size)
		{
			if (arr[i] < item)
			{
				//Find new position of current cycle element
				pos++;
			}
			i++;
		}
		return pos;
	}
	//This are used to find the location of next different element
	public int skip_duplicates(int[] arr, int location, int item)
	{
		int pos = location;
		//Skip similar elements
		while (item == arr[pos])
		{
			pos++;
		}
		return pos;
	}
	//Perform the cycle sort in given array
	public void cycle_sort(int[] arr, int size)
	{
		// Loop controlling variables
		int pos = 0;
		int item = 0;
		int temp = 0;
		int cycle_start = 0;
		// count number of memory writes operation 
		int writes = 0;
		for (cycle_start = 0; cycle_start < size - 1; cycle_start++)
		{
			//Get current cycle element
			item = arr[cycle_start];
			//Find actual valid location
			pos = valid_position(arr, cycle_start, item, size);
			//Check whether given current cycle elements is need to modified or not
			if (pos != cycle_start)
			{
				pos = skip_duplicates(arr, pos, item);
				if (item != arr[pos])
				{
					//When new location element are different to current cycle element
					temp = arr[pos];
					arr[pos] = item;
					item = temp;
					writes++;
				}
				while (pos != cycle_start)
				{
					//Find actual valid location
					pos = valid_position(arr, cycle_start, item, size);
					pos = skip_duplicates(arr, pos, item);
					if (item != arr[pos])
					{
						temp = arr[pos];
						arr[pos] = item;
						item = temp;
						writes++;
					}
				}
			}
		}
	}
	public static void Main(String[] args)
	{
		MySort obj = new MySort();
		int[] arr = {
			11 , 8 , 3 , 8 , 32 , -3 , 1 , 9 , 23 , 2 , 4 , 0 , 5
		};
		//Get the size of array
		int size = arr.Length;
		Console.Write("\n Before Sort :\n");
		obj.display(arr, size);
		//Sort element
		obj.cycle_sort(arr, size);
		Console.Write("\n After Sort :\n");
		obj.display(arr, size);
	}
}

Output

 Before Sort :
 11 8 3 8 32 -3 1 9 23 2 4 0 5

 After Sort :
 -3 0 1 2 3 4 5 8 8 9 11 23 32
<?php
/*
	Php Program
	Sort array elements by using Cycle Sort
*/
class MySort
{
	//Function which is display array elements
	public	function display( $arr, $size)
	{
		for ($i = 0; $i < $size; ++$i)
		{
			echo " ". $arr[$i];
		}
		echo "\n";
	}
	// When given item is not sorted of given array in right side 
	// then they are returns new location of right side. 
	// Otherwise they returns current location
	public	function valid_position( & $arr, $cycle_start, $item, $size)
	{
		$pos = $cycle_start;
		//loop controlling variable
		$i = $cycle_start + 1;
		while ($i < $size)
		{
			if ($arr[$i] < $item)
			{
				//Find new position of current cycle element
				$pos++;
			}
			$i++;
		}
		return $pos;
	}
	//This are used to find the location of next different element
	public	function skip_duplicates( & $arr, $location, $item)
	{
		$pos = $location;
		//Skip similar elements
		while ($item == $arr[$pos])
		{
			$pos++;
		}
		return $pos;
	}
	//Perform the cycle sort in given array
	public	function cycle_sort( & $arr, $size)
	{
		// Loop controlling variables
		$pos = 0;
		$item = 0;
		$temp = 0;
		$cycle_start = 0;
		// count number of memory writes operation 
		$writes = 0;
		for ($cycle_start = 0; $cycle_start < $size - 1; $cycle_start++)
		{
			//Get current cycle element
			$item = $arr[$cycle_start];
			//Find actual valid location
			$pos = $this->valid_position($arr, $cycle_start, $item, $size);
			//Check whether given current cycle elements is need to modified or not
			if ($pos != $cycle_start)
			{
				$pos = $this->skip_duplicates($arr, $pos, $item);
				if ($item != $arr[$pos])
				{
					//When new location element are different to current cycle element
					$temp = $arr[$pos];
					$arr[$pos] = $item;
					$item = $temp;
					$writes++;
				}
				while ($pos != $cycle_start)
				{
					//Find actual valid location
					$pos = $this->valid_position($arr, $cycle_start, $item, $size);
					$pos = $this->skip_duplicates($arr, $pos, $item);
					if ($item != $arr[$pos])
					{
						$temp = $arr[$pos];
						$arr[$pos] = $item;
						$item = $temp;
						$writes++;
					}
				}
			}
		}
	}
}

function main()
{
	$obj = new MySort();
	//Define an sorted array of integers
	$arr = array(11, 8, 3, 8, 32, -3, 1, 9, 23, 2, 4, 0, 5);
	//Get the size of array
	$size = count($arr);
	echo "\n Before Sort :\n";
	$obj->display($arr, $size);
	//Sort element
	$obj->cycle_sort($arr, $size);
	echo "\n After Sort :\n";
	$obj->display($arr, $size);
}
main();

Output

 Before Sort :
 11 8 3 8 32 -3 1 9 23 2 4 0 5

 After Sort :
 -3 0 1 2 3 4 5 8 8 9 11 23 32
/*
	Node Js Program
	Sort array elements by using Cycle Sort
*/
class MySort
{
	//Function which is display array elements
	display(arr, size)
	{
		for (var i = 0; i < size; ++i)
		{
			process.stdout.write(" " + arr[i]);
		}
		process.stdout.write("\n");
	}
	// When given item is not sorted of given array in right side 
	// then they are returns new location of right side. 
	// Otherwise they returns current location
	valid_position(arr, cycle_start, item, size)
	{
		var pos = cycle_start;
		//loop controlling variable
		var i = cycle_start + 1;
		while (i < size)
		{
			if (arr[i] < item)
			{
				//Find new position of current cycle element
				pos++;
			}
			i++;
		}
		return pos;
	}
	//This are used to find the location of next different element
	skip_duplicates(arr, location, item)
	{
		var pos = location;
		//Skip similar elements
		while (item == arr[pos])
		{
			pos++;
		}
		return pos;
	}
	//Perform the cycle sort in given array
	cycle_sort(arr, size)
	{
		// Loop controlling variables
		var pos = 0;
		var item = 0;
		var temp = 0;
		var cycle_start = 0;
		// count number of memory writes operation 
		var writes = 0;
		for (cycle_start = 0; cycle_start < size - 1; cycle_start++)
		{
			//Get current cycle element
			item = arr[cycle_start];
			//Find actual valid location
			pos = this.valid_position(arr, cycle_start, item, size);
			//Check whether given current cycle elements is need to modified or not
			if (pos != cycle_start)
			{
				pos = this.skip_duplicates(arr, pos, item);
				if (item != arr[pos])
				{
					//When new location element are different to current cycle element
					temp = arr[pos];
					arr[pos] = item;
					item = temp;
					writes++;
				}
				while (pos != cycle_start)
				{
					//Find actual valid location
					pos = this.valid_position(arr, cycle_start, item, size);
					pos = this.skip_duplicates(arr, pos, item);
					if (item != arr[pos])
					{
						temp = arr[pos];
						arr[pos] = item;
						item = temp;
						writes++;
					}
				}
			}
		}
	}
}

function main()
{
	var obj = new MySort();
	//Define an sorted array of integers
	var arr = [11, 8, 3, 8, 32, -3, 1, 9, 23, 2, 4, 0, 5];
	//Get the size of array
	var size = arr.length;
	process.stdout.write("\n Before Sort :\n");
	obj.display(arr, size);
	//Sort element
	obj.cycle_sort(arr, size);
	process.stdout.write("\n After Sort :\n");
	obj.display(arr, size);
}
main();

Output

 Before Sort :
 11 8 3 8 32 -3 1 9 23 2 4 0 5

 After Sort :
 -3 0 1 2 3 4 5 8 8 9 11 23 32
# 	Python 3 Program
# 	Sort array elements by using Cycle Sort

class MySort :
	# Function which is display array elements
	def display(self, arr, size) :
		i = 0
		while (i < size) :
			print(" ", arr[i], end = "")
			i += 1
		
		print("\n", end = "")
	
	#  When given item is not sorted of given array in right side 
	#  then they are returns new location of right side. 
	#  Otherwise they returns current location
	def valid_position(self, arr, cycle_start, item, size) :
		pos = cycle_start
		# loop controlling variable
		i = cycle_start + 1
		while (i < size) :
			if (arr[i] < item) :
				# Find new position of current cycle element
				pos += 1
			
			i += 1
		
		return pos
	
	# This are used to find the location of next different element
	def skip_duplicates(self, arr, location, item) :
		pos = location
		# Skip similar elements
		while (item == arr[pos]) :
			pos += 1
		
		return pos
	
	# Perform the cycle sort in given array
	def cycle_sort(self, arr, size) :
		#  Loop controlling variables
		pos = 0
		item = 0
		temp = 0
		cycle_start = 0
		#  count number of memory writes operation 
		writes = 0
		cycle_start = 0
		while (cycle_start < size - 1) :
			# Get current cycle element
			item = arr[cycle_start]
			# Find actual valid location
			pos = self.valid_position(arr, cycle_start, item, size)
			# Check whether given current cycle elements is need to modified or not
			if (pos != cycle_start) :
				pos = self.skip_duplicates(arr, pos, item)
				if (item != arr[pos]) :
					# When new location element are different to current cycle element
					temp = arr[pos]
					arr[pos] = item
					item = temp
					writes += 1
				
				while (pos != cycle_start) :
					# Find actual valid location
					pos = self.valid_position(arr, cycle_start, item, size)
					pos = self.skip_duplicates(arr, pos, item)
					if (item != arr[pos]) :
						temp = arr[pos]
						arr[pos] = item
						item = temp
						writes += 1
					
				
			
			cycle_start += 1
		
	

def main() :
	obj = MySort()
	# Define an sorted array of integers
	arr = [11, 8, 3, 8, 32, -3, 1, 9, 23, 2, 4, 0, 5]
	# Get the size of array
	size = len(arr)
	print("\n Before Sort :\n", end = "")
	obj.display(arr, size)
	# Sort element
	obj.cycle_sort(arr, size)
	print("\n After Sort :\n", end = "")
	obj.display(arr, size)

if __name__ == "__main__": main()

Output

 Before Sort :
  11  8  3  8  32  -3  1  9  23  2  4  0  5

 After Sort :
  -3  0  1  2  3  4  5  8  8  9  11  23  32
# 	Ruby Program
# 	Sort array elements by using Cycle Sort

class MySort

	# Function which is display array elements
	def display(arr, size)
	
		i = 0
		while (i < size)
		
			print(" ", arr[i])
			i += 1
		end
		print("\n")
	end
	#  When given item is not sorted of given array in right side 
	#  then they are returns new location of right side. 
	#  Otherwise they returns current location
	def valid_position(arr, cycle_start, item, size)
	
		pos = cycle_start
		# loop controlling variable
		i = cycle_start + 1
		while (i < size)
		
			if (arr[i] < item)
			
				# Find new position of current cycle element
				pos += 1
			end
			i += 1
		end
		return pos
	end
	# This are used to find the location of next different element
	def skip_duplicates(arr, location, item)
	
		pos = location
		# Skip similar elements
		while (item == arr[pos])
		
			pos += 1
		end
		return pos
	end
	# Perform the cycle sort in given array
	def cycle_sort(arr, size)
	
		#  Loop controlling variables
		pos = 0
		item = 0
		temp = 0
		cycle_start = 0
		#  count number of memory writes operation 
		writes = 0
		cycle_start = 0
		while (cycle_start < size - 1)
		
			# Get current cycle element
			item = arr[cycle_start]
			# Find actual valid location
			pos = self.valid_position(arr, cycle_start, item, size)
			# Check whether given current cycle elements is need to modified or not
			if (pos != cycle_start)
			
				pos = self.skip_duplicates(arr, pos, item)
				if (item != arr[pos])
				
					# When new location element are different to current cycle element
					temp = arr[pos]
					arr[pos] = item
					item = temp
					writes += 1
				end
				while (pos != cycle_start)
				
					# Find actual valid location
					pos = self.valid_position(arr, cycle_start, item, size)
					pos = self.skip_duplicates(arr, pos, item)
					if (item != arr[pos])
					
						temp = arr[pos]
						arr[pos] = item
						item = temp
						writes += 1
					end
				end
			end
			cycle_start += 1
		end
	end
end
def main()

	obj = MySort.new()
	# Define an sorted array of integers
	arr = [11, 8, 3, 8, 32, -3, 1, 9, 23, 2, 4, 0, 5]
	# Get the size of array
	size = arr.length
	print("\n Before Sort :\n")
	obj.display(arr, size)
	# Sort element
	obj.cycle_sort(arr, size)
	print("\n After Sort :\n")
	obj.display(arr, size)
end
main()

Output

 Before Sort :
 11 8 3 8 32 -3 1 9 23 2 4 0 5

 After Sort :
 -3 0 1 2 3 4 5 8 8 9 11 23 32

/*
	Scala Program
	Sort array elements by using Cycle Sort
*/
class MySort
{
	//Function which is display array elements
	def display(arr: Array[Int], size: Int): Unit = {
		var i: Int = 0;
		while (i < size)
		{
			print(" " + arr(i));
			i += 1;
		}
		print("\n");
	}
	// When given item is not sorted of given array in right side 
	// then they are returns new location of right side. 
	// Otherwise they returns current location
	def valid_position(arr: Array[Int], cycle_start: Int, item: Int, size: Int): Int = {
		var pos: Int = cycle_start;
		//loop controlling variable
		var i: Int = cycle_start + 1;
		while (i < size)
		{
			if (arr(i) < item)
			{
				//Find new position of current cycle element
				pos += 1;
			}
			i += 1;
		}
		return pos;
	}
	//This are used to find the location of next different element
	def skip_duplicates(arr: Array[Int], location: Int, item: Int): Int = {
		var pos: Int = location;
		//Skip similar elements
		while (item == arr(pos))
		{
			pos += 1;
		}
		return pos;
	}
	//Perform the cycle sort in given array
	def cycle_sort(arr: Array[Int], size: Int): Unit = {
		// Loop controlling variables
		var pos: Int = 0;
		var item: Int = 0;
		var temp: Int = 0;
		var cycle_start: Int = 0;
		// count number of memory writes operation 
		var writes: Int = 0;
		cycle_start = 0;
		while (cycle_start < size - 1)
		{
			//Get current cycle element
			item = arr(cycle_start);
			//Find actual valid location
			pos = valid_position(arr, cycle_start, item, size);
			//Check whether given current cycle elements is need to modified or not
			if (pos != cycle_start)
			{
				pos = skip_duplicates(arr, pos, item);
				if (item != arr(pos))
				{
					//When new location element are different to current cycle element
					temp = arr(pos);
					arr(pos) = item;
					item = temp;
					writes += 1;
				}
				while (pos != cycle_start)
				{
					//Find actual valid location
					pos = valid_position(arr, cycle_start, item, size);
					pos = skip_duplicates(arr, pos, item);
					if (item != arr(pos))
					{
						temp = arr(pos);
						arr(pos) = item;
						item = temp;
						writes += 1;
					}
				}
			}
			cycle_start += 1;
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var obj: MySort = new MySort();
		//Define an sorted array of integers
		var arr: Array[Int] = Array(11, 8, 3, 8, 32, -3, 1, 9, 23, 2, 4, 0, 5);
		//Get the size of array
		var size: Int = arr.length;
		print("\n Before Sort :\n");
		obj.display(arr, size);
		//Sort element
		obj.cycle_sort(arr, size);
		print("\n After Sort :\n");
		obj.display(arr, size);
	}
}

Output

 Before Sort :
 11 8 3 8 32 -3 1 9 23 2 4 0 5

 After Sort :
 -3 0 1 2 3 4 5 8 8 9 11 23 32
/*
	Swift Program
	Sort array elements by using Cycle Sort
*/
class MySort
{
	//Function which is display array elements
	func display(_ arr: [Int], _ size: Int)
	{
		var i: Int = 0;
		while (i < size)
		{
			print(" ", arr[i], terminator: "");
			i += 1;
		}
		print("\n", terminator: "");
	}
	// When given item is not sorted of given array in right side 
	// then they are returns new location of right side. 
	// Otherwise they returns current location
	func valid_position(_ arr: [Int], _ cycle_start: Int, _ item: Int, _ size: Int) -> Int
	{
		var pos: Int = cycle_start;
		//loop controlling variable
		var i: Int = cycle_start + 1;
		while (i < size)
		{
			if (arr[i] < item)
			{
				//Find new position of current cycle element
				pos += 1;
			}
			i += 1;
		}
		return pos;
	}
	//This are used to find the location of next different element
	func skip_duplicates(_ arr: [Int], _ location: Int, _ item: Int) -> Int
	{
		var pos: Int = location;
		//Skip similar elements
		while (item == arr[pos])
		{
			pos += 1;
		}
		return pos;
	}
	//Perform the cycle sort in given array
	func cycle_sort(_ arr: inout[Int], _ size: Int)
	{
		// Loop controlling variables
		var pos: Int = 0;
		var item: Int = 0;
		var temp: Int = 0;
		var cycle_start: Int = 0;
		// count number of memory writes operation 
		var writes: Int = 0;
		cycle_start = 0;
		while (cycle_start < size - 1)
		{
			//Get current cycle element
			item = arr[cycle_start];
			//Find actual valid location
			pos = self.valid_position(arr, cycle_start, item, size);
			//Check whether given current cycle elements is need to modified or not
			if (pos != cycle_start)
			{
				pos = self.skip_duplicates(arr, pos, item);
				if (item != arr[pos])
				{
					//When new location element are different to current cycle element
					temp = arr[pos];
					arr[pos] = item;
					item = temp;
					writes += 1;
				}
				while (pos != cycle_start)
				{
					//Find actual valid location
					pos = self.valid_position(arr, cycle_start, item, size);
					pos = self.skip_duplicates(arr, pos, item);
					if (item != arr[pos])
					{
						temp = arr[pos];
						arr[pos] = item;
						item = temp;
						writes += 1;
					}
				}
			}
			cycle_start += 1;
		}
	}
}
func main()
{
	let obj: MySort = MySort();
	//Define an sorted array of integers
	var arr: [Int] = [11, 8, 3, 8, 32, -3, 1, 9, 23, 2, 4, 0, 5];
	//Get the size of array
	let size: Int = arr.count;
	print("\n Before Sort :\n", terminator: "");
	obj.display(arr, size);
	//Sort element
	obj.cycle_sort(&arr, size);
	print("\n After Sort :\n", terminator: "");
	obj.display(arr, size);
}
main();

Output

 Before Sort :
  11  8  3  8  32  -3  1  9  23  2  4  0  5

 After Sort :
  -3  0  1  2  3  4  5  8  8  9  11  23  32
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment