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
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