SORTOWANIE CYKLICZNE

Wypróbuj w praktyce GfG Sortowanie cykliczne' title=

Sortowanie cykliczne to niestabilny algorytm sortowania w miejscu, który jest szczególnie przydatny podczas sortowania tablic zawierających elementy o małym zakresie wartości. Został opracowany przez WD Jonesa i opublikowany w 1963 roku.

Podstawową ideą sortowania cyklicznego jest podzielenie tablicy wejściowej na cykle, z których każdy cykl składa się z elementów należących do tej samej pozycji w posortowanej tablicy wyjściowej. Następnie algorytm wykonuje serię zamian, aby umieścić każdy element we właściwej pozycji w swoim cyklu, aż do zakończenia wszystkich cykli i posortowania tablicy.

Oto szczegółowe wyjaśnienie algorytmu sortowania cyklicznego:

Zacznij od nieposortowanej tablicy n elementów.
Zainicjuj zmienną cyklStart na 0.
Dla każdego elementu tablicy porównaj go z każdym innym elementem po jego prawej stronie. Jeśli są jakieś elementy mniejsze niż bieżący element, zwiększ cyklStart.
Jeżeli cyklStart po porównaniu pierwszego elementu ze wszystkimi innymi elementami nadal wynosi 0, przejdź do następnego elementu i powtórz krok 3.
Po znalezieniu mniejszego elementu zamień bieżący element na pierwszy element w swoim cyklu. Cykl jest następnie kontynuowany, aż bieżący element powróci do swojej pierwotnej pozycji.

Powtarzaj kroki 3-5, aż wszystkie cykle zostaną zakończone.

Tablica jest teraz posortowana.

Jedną z zalet sortowania cyklicznego jest to, że zajmuje mało pamięci, ponieważ sortuje tablicę w miejscu i nie wymaga dodatkowej pamięci na zmienne tymczasowe ani bufory. Jednak w niektórych sytuacjach może to działać powoli, szczególnie gdy tablica wejściowa ma duży zakres wartości. Niemniej jednak sortowanie cykliczne pozostaje użytecznym algorytmem sortowania w pewnych kontekstach, na przykład podczas sortowania małych tablic o ograniczonych zakresach wartości.

Sortowanie cykliczne to algorytm sortowania w miejscu niestabilny algorytm sortowania oraz sortowanie porównawcze, które jest teoretycznie optymalne pod względem całkowitej liczby zapisów do oryginalnej tablicy.

para Java

Jest optymalny pod względem ilości zapisów do pamięci. To minimalizuje liczbę zapisów do pamięci sortować (każda wartość jest albo zapisywana zero razy, jeśli znajduje się już na właściwej pozycji, albo zapisywana jeden raz we właściwym miejscu).
Opiera się na założeniu, że sortowaną tablicę można podzielić na cykle. Cykle można przedstawić w formie wykresu. Mamy n węzłów i krawędź skierowaną od węzła i do węzła j, jeśli element o i-tym indeksie musi znajdować się pod j-tym indeksem w posortowanej tablicy.
Cykl w arr[] = {2 4 5 1 3}

Cykl w arr[] = {2 4 5 1 3}

Cykl w arr[] = {4 3 2 1}

Cykl w arr[] = {4 3 2 1}

Po kolei rozważamy wszystkie cykle. Najpierw rozważymy cykl, który zawiera pierwszy element. Znajdujemy właściwą pozycję pierwszego elementu i umieszczamy go we właściwej pozycji, powiedzmy j. Rozważamy starą wartość arr[j] i znajdujemy jej właściwą pozycję. Robimy to tak długo, aż wszystkie elementy bieżącego cyklu znajdą się na właściwych pozycjach, czyli nie wrócimy do punktu początkowego cyklu.

Losowa matematyka Java

Pseudokod:

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

Wyjaśnienie :

 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

Poniżej implementacja powyższego podejścia:

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

Wyjście

After sort : 1 2 3 4 8 9 10 10

Analiza złożoności czasu :

Najgorszy przypadek: NA²)
Przeciętny przypadek: NA²)
Najlepszy przypadek: NA²)

Przestrzeń pomocnicza: O(1)

Złożoność przestrzeni jest stała, ponieważ ten algorytm istnieje, więc nie wymaga dodatkowej pamięci do sortowania.

Metoda 2: Ta metoda ma zastosowanie tylko wtedy, gdy podane wartości tablicy lub elementy mieszczą się w zakresie od 1 do N lub 0 do N. W tej metodzie nie musimy obracać tablicy

Zbliżać się : Wszystkie podane wartości tablicy powinny mieścić się w zakresie od 1 do N lub od 0 do N. Jeśli zakres wynosi od 1 do N, wówczas poprawną pozycją każdego elementu tablicy będzie indeks == wartość-1, co oznacza, że przy 0. wartości indeksu będzie 1, podobnie przy 1. pozycji indeksu wartość będzie wynosić 2 i tak dalej, aż do n-tej wartości.

program macierzowy w języku c

podobnie dla wartości od 0 do N poprawna pozycja indeksu każdego elementu tablicy lub wartości będzie taka sama jak jego wartość, tj. przy 0-tym indeksie będzie 0, 1-sza pozycja będzie tam.

Wyjaśnienie :

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}

Poniżej implementacja powyższego podejścia:

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)

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)

Wyjście

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

Analiza złożoności czasu:

Najgorszy przypadek: NA)
Przeciętny przypadek: NA)
Najlepszy przypadek: NA)

Przestrzeń pomocnicza: O(1)

Zaleta sortowania cyklicznego:

Nie jest wymagane żadne dodatkowe miejsce do przechowywania.
algorytm sortowania w miejscu.
Minimalna liczba zapisów do pamięci
Sortowanie cykliczne jest przydatne, gdy tablica jest przechowywana w pamięci EEPROM lub FLASH.

Wady sortowania cyklicznego:

Nie jest najczęściej używany.
Ma większą złożoność czasową o(n^2)
Niestabilny algorytm sortowania.

Zastosowanie sortowania cyklicznego:

Ten algorytm sortowania najlepiej sprawdza się w sytuacjach, gdy operacje zapisu lub zamiany pamięci są kosztowne.
Przydatne w przypadku złożonych problemów.

Utwórz quiz