logo

TechCodeview

Cikel Razvrščanje

Preizkusite na GfG Practice Cikel Razvrščanje' title=

Cikel razvrščanja je nestabilen algoritem za razvrščanje na mestu, ki je še posebej uporaben pri razvrščanju nizov, ki vsebujejo elemente z majhnim obsegom vrednosti. Razvil jo je W. D. Jones in objavil leta 1963.

Osnovna ideja cikličnega razvrščanja je razdelitev vhodne matrike na cikle, kjer je vsak cikel sestavljen iz elementov, ki pripadajo istemu položaju v razvrščeni izhodni matriki. Algoritem nato izvede niz zamenjav, da postavi vsak element na pravilno mesto v njegovem ciklu, dokler niso vsi cikli dokončani in je matrika razvrščena.

Tukaj je razlaga algoritma cikličnega razvrščanja po korakih:

  1. Začnite z nerazvrščenim nizom n elementov.
  2. Inicializirajte spremenljivko cycleStart na 0.
  3. Za vsak element v matriki ga primerjajte z vsemi drugimi elementi na desni strani. Če obstajajo elementi, ki so manjši od trenutnega prirastka elementa cycleStart.
  4. Če je cycleStart po primerjavi prvega elementa z vsemi drugimi elementi še vedno 0, se premaknite na naslednji element in ponovite 3. korak.
  5. Ko je najden manjši element, zamenjajte trenutni element s prvim elementom v njegovem ciklu. Cikel se nato nadaljuje, dokler se trenutni element ne vrne v prvotni položaj.

Ponavljajte korake 3–5, dokler niso zaključeni vsi cikli.



Matrika je zdaj razvrščena.

Ena od prednosti cikličnega razvrščanja je, da ima malo pomnilniškega odtisa, saj razvrsti matriko na mestu in ne potrebuje dodatnega pomnilnika za začasne spremenljivke ali medpomnilnike. Vendar pa je lahko v določenih situacijah počasen, zlasti če ima vhodna matrika velik razpon vrednosti. Kljub temu ostaja ciklično razvrščanje uporaben algoritem razvrščanja v določenih okoliščinah, na primer pri razvrščanju majhnih nizov z omejenimi razponi vrednosti.

Cikel razvrščanja je algoritem za razvrščanje na mestu nestabilen algoritem razvrščanja in primerjalno razvrščanje, ki je teoretično optimalno glede na skupno število zapisov v izvirno matriko. 
 

javascript trim
  • Optimalen je glede števila zapisov v pomnilnik. To zmanjša število zapisov v pomnilnik za razvrščanje (Vsaka vrednost je bodisi zapisana ničkrat, če je že na pravilnem položaju, bodisi enkrat zapisana na pravilnem položaju.)
  • Temelji na ideji, da lahko niz, ki ga je treba razvrstiti, razdelimo na cikle. Cikle lahko vizualiziramo kot graf. Imamo n vozlišč in rob, usmerjen od vozlišča i do vozlišča j, če mora biti element na i-tem indeksu prisoten na j-tem indeksu v razvrščeni matriki. 
    Cikel v arr[] = {2 4 5 1 3} 
     
Cikel RazvrščanjeCikel v arr[] = {2 4 5 1 3}
  • Cikel v arr[] = {4 3 2 1} 
     
Cikel v arr[] = {4 3 2 1} 


Enega za drugim upoštevamo vse cikle. Najprej razmislimo o ciklu, ki vključuje prvi element. Poiščemo pravilen položaj prvega elementa in ga postavimo na pravilno mesto, recimo j. Upoštevamo staro vrednost arr[j] in poiščemo njen pravilni položaj. To počnemo, dokler niso vsi elementi trenutnega cikla postavljeni na pravilen položaj, tj. ne pridemo nazaj na začetno točko cikla.

slika kot ozadje v css

Psevdokoda: 

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

Pojasnilo:  

 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

Spodaj je izvedba zgornjega pristopa:

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>

Izhod 
After sort : 1 2 3 4 8 9 10 10

Analiza časovne kompleksnosti : 

  • Najslabši primer: O(n2) 
  • Povprečni primer: O(n2) 
  • Najboljši primer: O(n2)

Pomožni prostor: O(1)

  • Kompleksnost prostora je stalna, ker je ta algoritem na mestu, tako da ne uporablja dodatnega pomnilnika za razvrščanje.

2. način: Ta metoda je uporabna le, če so podane vrednosti ali elementi polja v območju od 1 do N ali od 0 do N. Pri tej metodi nam ni treba zasukati polja

Pristop: Vse dane vrednosti matrike bi morale biti v območju od 1 do N ali od 0 do N. Če je obseg od 1 do N, bo pravilen položaj vsakega elementa matrike indeks == vrednost-1, kar pomeni, da bo vrednost 0. indeksa 1, podobno bo vrednost položaja 1. indeksa 2 in tako naprej do n-te vrednosti.

kontradiktorno iskanje

podobno za vrednosti od 0 do N bo pravilen položaj indeksa vsakega elementa matrike ali vrednosti enak njegovi vrednosti, tj. pri 0. indeksu bo tam 0, tam bo 1. položaj 1.

Pojasnilo:  

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}

Spodaj je izvedba zgornjega pristopa:

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)

Izhod 
Before sorting array: 3 2 4 5 1 Sorted array: 1 2 3 4 5

Analiza časovne kompleksnosti:

  • Najslabši primer: O(n) 
  • Povprečni primer: O(n) 
  • Najboljši primer: O(n)

Pomožni prostor: O(1)

Prednost Cycle sort:

  1. Dodaten prostor za shranjevanje ni potreben.
  2.  algoritem za razvrščanje na mestu.
  3.  Najmanjše število zapisov v pomnilnik
  4.  Cikelno razvrščanje je uporabno, ko je polje shranjeno v EEPROM ali FLASH. 

Slabost ciklične vrste:

  1.  Večinoma se ne uporablja.
  2.  Ima večjo časovno zapletenost o(n^2)
  3.  Nestabilen algoritem razvrščanja.

Uporaba ciklične vrste:

  • Ta algoritem razvrščanja je najprimernejši za situacije, ko so operacije zapisovanja ali zamenjave v pomnilnik drage.
  • Uporabno za zapletene probleme. 
     
Ustvari kviz