Cycle Sort

Speed

Number of Elements

[Range: 10-100]

Implementations

          
            void cycleSort(int array[], int n){
              int temp;

              for (int start = 0; start <= n - 2; start++){
                int item = array[start];
                int position = start;

                for (int i = start + 1; i < n; i++){
                  if (array[i] < item){
                    position++;
                  }
                }

                if (position == start) continue;

                while (item == array[position]){
                  position++;
                }

                if (position != start){
                  temp = array[position];
                  array[position] = item;
                  item = temp;
                }

                while (position != start){
                  position = start;

                  for (int i = start + 1; i < n; i++){
                    if (array[i] < item){
                      position++;
                    }

                    while (item == array[position]){
                      position++;
                    }

                    if (item != array[position]){
                      temp = array[position];
                      array[position] = item;
                      item = temp;
                    }
                  }
                }
              }
            }
          
        
          
            def cycleSort(array):
              n = len(array)

              for (start in range(0, n - 1)):
                item = array[start]
                position = start

                for i in range(start + 1, n):
                  if array[i] < item:
                    position = position + 1

                if position == start:
                  continue

                while item == array[position]:
                  position = position + 1
                
                array[position], item = item, array[position]

                while position != start:
                  positoin = start
                  
                  for i in range(start + 1, n):
                    if array[i] < item:
                      position = position + 1

                  while item == array[position]:
                    position = position + 1
                  
                  array[position], item = item, array[position]

          
        
          
            function cycleSort(array){
              var n = array.length;
              let temp;

              for (let start = 0; start <= n - 2; start++){
                let item = array[start];
                let position = start;

                for (let i = start + 1; i < n; i++){
                  if (array[i] < item){
                    position++;
                  }
                }

                if (position == start){
                  continue;
                }

                while (item == array[position]){
                  position++;
                }

                if (position != start){
                  temp = array[position];
                  array[position] = item;
                  item = temp;
                }

                while (position != start){
                  position = start;

                  for (let i = start + 1; i < n; i++){
                    if (array[i] < item){
                      position++;
                    }

                    while (item == array[position]){
                      position++;
                    }

                    if (item != array[position]){
                      temp = array[position];
                      array[position] = item;
                      item = temp;
                    }
                  }
                }
              }
            }

About Cycle Sort

The Cycle sorting method is a comparison sort that specializes in the least amount of writes. In other words, this sorting method will only write a value to the array if it is sure that is where the value belongs.


Time Complexity

The Cycle sorting method has a time complexity of: O(N2)