logo

TechCodeview

Cyklické triedenie

Vyskúšajte to na GfG Practice Cyklické triedenie' title=

Cyklické triedenie je na mieste nestabilný triediaci algoritmus, ktorý je užitočný najmä pri triedení polí obsahujúcich prvky s malým rozsahom hodnôt. Bol vyvinutý W. D. Jonesom a publikovaný v roku 1963.

Základnou myšlienkou triedenia cyklov je rozdeliť vstupné pole do cyklov, kde každý cyklus pozostáva z prvkov, ktoré patria na rovnakú pozíciu v triedenom výstupnom poli. Algoritmus potom vykoná sériu swapov, aby umiestnil každý prvok na správnu pozíciu v rámci svojho cyklu, kým nie sú všetky cykly dokončené a pole nie je zoradené.

Tu je podrobné vysvetlenie algoritmu triedenia cyklu:

  1. Začnite s nezoradeným poľom n prvkov.
  2. Inicializujte premennú cycleStart na 0.
  3. Pre každý prvok v poli ho porovnajte s každým iným prvkom napravo. Ak existujú nejaké prvky, ktoré sú menšie ako aktuálny prírastok prvku cycleStart.
  4. Ak je cycleStart po porovnaní prvého prvku so všetkými ostatnými prvkami stále 0, prejdite na ďalší prvok a zopakujte krok 3.
  5. Keď sa nájde menší prvok, vymeňte aktuálny prvok za prvý prvok v jeho cykle. Cyklus potom pokračuje, kým sa aktuálny prvok nevráti do pôvodnej polohy.

Opakujte kroky 3-5, kým sa nedokončia všetky cykly.



Pole je teraz zoradené.

Jednou z výhod triedenia cyklu je, že má nízku pamäťovú stopu, pretože triedi pole na mieste a nevyžaduje dodatočnú pamäť pre dočasné premenné alebo vyrovnávacie pamäte. V určitých situáciách však môže byť pomalý, najmä ak má vstupné pole veľký rozsah hodnôt. Cyklické triedenie však zostáva užitočným triediacim algoritmom v určitých kontextoch, ako napríklad pri triedení malých polí s obmedzenými rozsahmi hodnôt.

Cyklické triedenie je algoritmus triedenia na mieste nestabilný triediaci algoritmus a porovnávacie triedenie, ktoré je teoreticky optimálne z hľadiska celkového počtu zápisov do pôvodného poľa. 
 

arraylist
  • Je optimálny z hľadiska počtu zápisov do pamäte. to minimalizuje počet zápisov do pamäte na zoradenie (Každá hodnota sa buď zapíše nulakrát, ak už je na správnej pozícii, alebo sa zapíše raz na správnu pozíciu.)
  • Je založený na myšlienke, že pole, ktoré sa má triediť, môže byť rozdelené do cyklov. Cykly je možné zobraziť ako graf. Máme n uzlov a hranu smerujúcu z uzla i do uzla j, ak prvok na i-tom indexe musí byť prítomný na j-tom indexe v triedenom poli. 
    Cyklus v arr[] = {2 4 5 1 3} 
     
Cyklické triedenieCyklus v arr[] = {2 4 5 1 3}
  • Cyklus v arr[] = {4 3 2 1} 
     
Cyklus v arr[] = {4 3 2 1} 


Jeden po druhom zvážime všetky cykly. Najprv zvážime cyklus, ktorý obsahuje prvý prvok. Nájdeme správnu polohu prvého prvku a umiestnime ho na jeho správnu pozíciu, povedzme j. Berieme do úvahy starú hodnotu arr[j] a nájdeme jej správnu polohu. Takto pokračujeme dovtedy, kým nie sú všetky prvky aktuálneho cyklu umiestnené v správnej polohe, t. j. nevrátime sa do počiatočného bodu cyklu.

fcfs

Pseudokód: 

Begin  
for  
start:= 0 to n - 2 do  
key := array[start]  
location := start  
for i:= start + 1 to n-1 do  
 if array[i] < key then  
 location: =location +1  
done  
if location = start then  
 ignore lower part go for next iteration  
while key = array[location] do  
 location: = location + 1  
done  
if location != start then  
 swap array[location] with key  
while location != start do  
 location start  
  
  
for i:= start + 1 to n-1 do  
 if array[i] < key then  
 location: =location +1  
done  
while key= array[location]  
 location := location +1  
 if key != array[location]  
 Swap array[location] and key  
 done  
 done  
End

vysvetlenie:  

 arr[] = {10 5 2 3}  
 index = 0 1 2 3  
cycle_start = 0   
    item    = 10 = arr[0]  
  
Find position where we put the item   
pos = cycle_start  
i=pos+1  
while(i  
if (arr[i] < item)   
 pos++;  
  
We put 10 at arr[3] and change item to   
old value of arr[3].  
arr[] = {10 5 2       10     }   
    item    = 3   
  
Again rotate rest cycle that start with     index '0'      
Find position where we put the item = 3   
we swap item with element at arr[1] now   
arr[] = {10       3      2       10     }   
    item    = 5  
  
Again rotate rest cycle that start with index '0' and item = 5   
we swap item with element at arr[2].  
arr[] = {10       3            5            10      }   
    item    = 2  
  
Again rotate rest cycle that start with index '0' and item = 2  
arr[] = {      2            3                    5            10     }   
  
Above is one iteration for cycle_stat = 0.  
Repeat above steps for cycle_start = 1 2 ..n-2

Nižšie je uvedená implementácia vyššie uvedeného prístupu:

CPP 
// C++ program to implement cycle sort #include    using namespace std; // Function sort the array using Cycle sort 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) {  swap(item arr[pos]);  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]) {  swap(item arr[pos]);  writes++;  }  }  }  // Number of memory writes or swaps  // cout << writes << endl ; } // Driver program to test above function int main() {  int arr[] = { 1 8 3 9 10 10 2 4 };  int n = sizeof(arr) / sizeof(arr[0]);  cycleSort(arr n);  cout << 'After sort : ' << endl;  for (int i = 0; i < n; i++)  cout << arr[i] << ' ';  return 0; }
Java 
// Java program to implement cycle sort import java.util.*; import java.lang.*; class GFG {  // 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] + ' ');  } } // Code Contributed by Mohit Gupta_OMG <(0_o)>
Python3 
# Python program to implement cycle sort def cycleSort(array): writes = 0 # Loop through the array to find cycles to rotate. for cycleStart in range(0 len(array) - 1): item = array[cycleStart] # Find where to put the item. pos = cycleStart for i in range(cycleStart + 1 len(array)): if array[i] < item: pos += 1 # If the item is already there this is not a cycle. if pos == cycleStart: continue # Otherwise put the item there or right after any duplicates. while item == array[pos]: pos += 1 array[pos] item = item array[pos] writes += 1 # Rotate the rest of the cycle. while pos != cycleStart: # Find where to put the item. pos = cycleStart for i in range(cycleStart + 1 len(array)): if array[i] < item: pos += 1 # Put the item there or right after any duplicates. while item == array[pos]: pos += 1 array[pos] item = item array[pos] writes += 1 return writes # driver code  arr = [1 8 3 9 10 10 2 4 ] n = len(arr) cycleSort(arr) print('After sort : ') for i in range(0 n) : print(arr[i] end = ' ') # Code Contributed by Mohit Gupta_OMG <(0_o)>
C# 
// C# program to implement cycle sort using System; class GFG {    // 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()  {  int[] arr = { 1 8 3 9 10 10 2 4 };  int n = arr.Length;    // Function calling  cycleSort(arr n);  Console.WriteLine('After sort : ');  for (int i = 0; i < n; i++)  Console.Write(arr[i] + ' ');  } } // This code is contributed by Nitin Mittal
JavaScript 
<script> // Javascript program to implement cycle sort  // Function sort the array using Cycle sort  function cycleSort(arr n)  {    // count number of memory writes  let writes = 0;    // traverse array elements and put it to on  // the right place  for (let cycle_start = 0; cycle_start <= n - 2; cycle_start++)  {    // initialize item as starting point  let item = arr[cycle_start];    // Find position where we put the item. We basically  // count all smaller elements on right side of item.  let pos = cycle_start;  for (let 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)  {  let 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 (let 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]) {  let temp = item;  item = arr[pos];  arr[pos] = temp;  writes++;  }  }  }  }   // Driver code   let arr = [ 1 8 3 9 10 10 2 4 ];  let n = arr.length;  cycleSort(arr n);    document.write('After sort : ' + '  
');  for (let i = 0; i < n; i++)  document.write(arr[i] + ' ');    // This code is contributed by susmitakundugoaldanga. </script>

Výstup 
After sort : 1 2 3 4 8 9 10 10

Analýza časovej zložitosti : 

  • Najhorší prípad: O(n2) 
  • Priemerný prípad: O(n2) 
  • Najlepší prípad: O(n2)

Pomocný priestor: O(1)

  • Priestorová zložitosť je konštantná, pretože tento algoritmus je zavedený, takže na triedenie nepoužíva žiadnu dodatočnú pamäť.

Metóda 2: Táto metóda je použiteľná iba vtedy, keď sú dané hodnoty alebo prvky poľa v rozsahu 1 až N alebo 0 až N. Pri tejto metóde nepotrebujeme otáčať pole

prístup: Všetky uvedené hodnoty poľa by mali byť v rozsahu 1 až N alebo 0 až N. Ak je rozsah 1 až N  , potom správna pozícia každého prvku poľa bude index == hodnota-1, t. j. znamená, že na 0. hodnote indexu bude 1, podobne na 1. pozícii indexu bude hodnota 2 a tak ďalej až do n-tej hodnoty.

podobne pre hodnoty 0 až N bude správna poloha indexu každého prvku poľa alebo hodnota rovnaká ako jeho hodnota, t. j. na 0. indexe bude 0 tam bude 1. poloha 1.

vysvetlenie: 

plsql 
arr[] = {5 3 1 4 2}  
index = 0 1 2 3 4  
  
i = 0;  
while( i < arr.length)  
 correctposition = arr[i]-1;   
   
 find ith item correct position  
 for the first time i = 0 arr[0] = 5 correct index of 5 is 4 so arr[i] - 1 = 5-1 = 4  
   
   
 if( arr[i] <= arr.length && arr[i] != arr[correctposition])  
   
   
 arr[i] = 5 and arr[correctposition] = 4   
 so 5 <= 5 && 5 != 4 if condition true   
 now swap the 5 with 4   
   
   
 int temp = arr[i];  
 arr[i] = arr[correctposition];  
 arr[correctposition] = temp;  
   
 now resultant arr at this after 1st swap   
 arr[] = {2 3 1 4 5} now 5 is shifted at its correct position   
   
 now loop will run again check for i = 0 now arr[i] is = 2   
 after swapping 2 at its correct position   
 arr[] = {3 2 1 4 5}  
   
 now loop will run again check for i = 0 now arr[i] is = 3   
 after swapping 3 at its correct position   
 arr[] = {1 2 3 4 5}  
   
 now loop will run again check for i = 0 now arr[i] is = 1  
 this time 1 is at its correct position so else block will execute and i will increment i = 1;  
 once i exceeds the size of array will get array sorted.  
 arr[] = {1 2 3 4 5}  
   
   
 else  
   
 i++;  
loop end;  
  
once while loop end we get sorted array just print it   
for( index = 0 ; index < arr.length; index++)  
 print(arr[index] + ' ')  
sorted arr[] = {1 2 3 4 5}

Nižšie je uvedená implementácia vyššie uvedeného prístupu:

C++ 
#include    using namespace std; void cyclicSort(int arr[] int n){  int i = 0;   while(i < n)  {  // as array is of 1 based indexing so the  // correct position or index number of each  // element is element-1 i.e. 1 will be at 0th  // index similarly 2 correct index will 1 so  // on...  int correct = arr[i] - 1 ;  if(arr[i] != arr[correct]){  // if array element should be lesser than  // size and array element should not be at  // its correct position then only swap with  // its correct position or index value  swap(arr[i] arr[correct]) ;  }else{  // if element is at its correct position  // just increment i and check for remaining  // array elements  i++ ;  }  } } void printArray(int arr[] int size) {  int i;  for (i = 0; i < size; i++)  cout << arr[i] << ' ';  cout << endl; } int main() {  int arr[] = { 3 2 4 5 1};  int n = sizeof(arr) / sizeof(arr[0]);  cout << 'Before sorting array: n';  printArray(arr n);  cyclicSort(arr n);  cout << 'Sorted array: n';  printArray(arr n);  return 0; }
Java 
// java program to check implement cycle sort import java.util.*; public class MissingNumber {  public static void main(String[] args)  {  int[] arr = { 3 2 4 5 1 };  int n = arr.length;  System.out.println('Before sort :');  System.out.println(Arrays.toString(arr));  CycleSort(arr n);    }  static void CycleSort(int[] arr int n)  {  int i = 0;  while (i < n) {  // as array is of 1 based indexing so the  // correct position or index number of each  // element is element-1 i.e. 1 will be at 0th  // index similarly 2 correct index will 1 so  // on...  int correctpos = arr[i] - 1;  if (arr[i] < n && arr[i] != arr[correctpos]) {  // if array element should be lesser than  // size and array element should not be at  // its correct position then only swap with  // its correct position or index value  swap(arr i correctpos);  }  else {  // if element is at its correct position  // just increment i and check for remaining  // array elements  i++;  }  }  System.out.println('After sort : ');  System.out.print(Arrays.toString(arr));      }  static void swap(int[] arr int i int correctpos)  {  // swap elements with their correct indexes  int temp = arr[i];  arr[i] = arr[correctpos];  arr[correctpos] = temp;  } } // this code is contributed by devendra solunke
Python 
# Python program to check implement cycle sort def cyclicSort(arr n): i = 0 while i < n: # as array is of 1 based indexing so the # correct position or index number of each # element is element-1 i.e. 1 will be at 0th # index similarly 2 correct index will 1 so # on... correct = arr[i] - 1 if arr[i] != arr[correct]: # if array element should be lesser than # size and array element should not be at # its correct position then only swap with # its correct position or index value arr[i] arr[correct] = arr[correct] arr[i] else: # if element is at its correct position # just increment i and check for remaining # array elements i += 1 def printArray(arr): print(*arr) arr = [3 2 4 5 1] n = len(arr) print('Before sorting array:') printArray(arr) # Function Call cyclicSort(arr n) print('Sorted array:') printArray(arr) # This Code is Contributed by Prasad Kandekar(prasad264)
C# 
using System; public class GFG {  static void CycleSort(int[] arr int n)  {  int i = 0;  while (i < n) {  // as array is of 1 based indexing so the  // correct position or index number of each  // element is element-1 i.e. 1 will be at 0th  // index similarly 2 correct index will 1 so  // on...  int correctpos = arr[i] - 1;  if (arr[i] < n && arr[i] != arr[correctpos]) {  // if array element should be lesser than  // size and array element should not be at  // its correct position then only swap with  // its correct position or index value  swap(arr i correctpos);  }  else {  // if element is at its correct position  // just increment i and check for remaining  // array elements  i++;  }  }  Console.Write('nAfter sort : ');  for (int index = 0; index < n; index++)  Console.Write(arr[index] + ' ');  }  static void swap(int[] arr int i int correctpos)  {  // swap elements with their correct indexes  int temp = arr[i];  arr[i] = arr[correctpos];  arr[correctpos] = temp;  }  static public void Main()  {  // Code  int[] arr = { 3 2 4 5 1 };  int n = arr.Length;  Console.Write('Before sort : ');  for (int i = 0; i < n; i++)  Console.Write(arr[i] + ' ');  CycleSort(arr n);  } } // This code is contributed by devendra solunke
JavaScript 
// JavaScript code for the above code function cyclicSort(arr n) {  var i = 0;  while (i < n)  {    // as array is of 1 based indexing so the  // correct position or index number of each  // element is element-1 i.e. 1 will be at 0th  // index similarly 2 correct index will 1 so  // on...  let correct = arr[i] - 1;  if (arr[i] !== arr[correct])  {    // if array element should be lesser than  // size and array element should not be at  // its correct position then only swap with  // its correct position or index value  [arr[i] arr[correct]] = [arr[correct] arr[i]];  }  else {  // if element is at its correct position  // just increment i and check for remaining  // array elements  i++;  }  } } function printArray(arr size) {  for (var i = 0; i < size; i++) {  console.log(arr[i] + ' ');  }  console.log('n'); } var arr = [3 2 4 5 1]; var n = arr.length; console.log('Before sorting array: n'); printArray(arr n); cyclicSort(arr n); console.log('Sorted array: n'); printArray(arr n); // This Code is Contributed by Prasad Kandekar(prasad264)

Výstup 
Before sorting array: 3 2 4 5 1 Sorted array: 1 2 3 4 5

Analýza časovej zložitosti:

  • Najhorší prípad: O(n) 
  • Priemerný prípad: O(n) 
  • Najlepší prípad: O(n)

Pomocný priestor: O(1)

Výhoda cyklického triedenia:

  1. Nevyžaduje sa žiadne ďalšie úložisko.
  2.  algoritmus triedenia na mieste.
  3.  Minimálny počet zápisov do pamäte
  4.  Cyklické triedenie je užitočné, keď je pole uložené v EEPROM alebo FLASH. 

Nevýhoda  cyklického triedenia:

  1.  Väčšinou sa nepoužíva.
  2.  Má väčšiu časovú zložitosť o (n^2)
  3.  Nestabilný algoritmus triedenia.

Aplikácia  cyklického triedenia:

  • Tento triediaci algoritmus je najvhodnejší pre situácie, kde sú operácie zápisu alebo výmeny pamäte nákladné.
  • Užitočné pri zložitých problémoch. 
     
Vytvoriť kvíz