CareerCup

Convert the fancy swap into a proper swap and sort the array linearly.

using System;

namespace ConsoleApp1
{
    class Program
    {
        private const int c_Space = -1;
        private static int[] a = new int[]
        {
                1, c_Space, 5, 4, 2, 3
        };

        static void Main()
        {
            Sort();

            for (int i = 0; i < a.Length; i++)
            {
                Console.WriteLine(a[i]);
            }
        }

        static void Sort()
        {
            for (int i = 0; i < a.Length - 1; i++)
            {
                if (a[i] == c_Space)
                {
                    Swap(i, a.Length - 1);
                }
            }

            int index = 0;
            while (index < a.Length - 1)
            {
                if (a[index] == index + 1) index++;
                else ProperSwap(a[index] - 1, index);
            }
        }

        static void Swap(int i, int j)
        {
            if (a[i] != c_Space && a[j] != c_Space)
            {
                throw new Exception("Must include space");
            }

            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }

        static void ProperSwap(int i, int j)
        {
            Swap(i, a.Length - 1);
            Swap(i, j);
            Swap(j, a.Length - 1);
        }
    }
}

You can do this with a modified quicksort.

The trick is that when you are dividing with the pivot, you are always sorting the left branch first. So once you sort the left branch of any given partition, put the space at the end of the partition, so it is available at the front of the next partition down the list

This would be n lg n time

The simple to code process would just be a selection sort, where you go pick out the largest element each time. This would be n squared

O(n) soln. -

public static void main(String[] args){
    int[] arr = {3,2,999,1};
    int index = -1;
    int k = arr.length;
    for(int i = 0; i < arr.length; i++){
      if(arr[i] == 999){
        index = i;
      	break;
      }
    }
  
    sort(arr, index, k);
  }
  
  //considering ' ' as 999
  public static void sort(int[] arr, int index, int k){
  
    int n = arr.length;
    
    if(k == 0){
      for(int i = 1; i < n; i++){
        System.out.print(arr[i] + " ");
      }
      System.out.print(999);
      return;
    }else if(k > 0 && index == 0){
      index = n-2;
      for(int i = 1; i <= index; i++){
      	arr[i-1] = arr[i];
      }
      arr[index] = 999;
    }
    
    if(index-1 >= 0 && index+1 < n && arr[index-1] > arr[index+1]){
    	swap(arr, index, index+1);
      	swap(arr, index-1, index+1);
    }else{
    	swap(arr, index, index-1);
    }
   	sort(arr, index-1, k-1);
  }
  
  public static void swap(int[] arr, int i, int j){
  	int t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
  }

void Sort(vector<int> &a)
{
	int space_idx = -1;
	for (int i = 0; i < a.size() && space_idx == -1; ++i) {
		if (a[i] == 0) {
			space_idx = i;
		}
	}

	if (space_idx != -1) {
		for (int i = 0; i < a.size(); ++i) {
			while (i != space_idx &&
				a[i] != i + 1)
			{
				int space_idx_stored = space_idx;
				swap(a[a[i] - 1], a[space_idx]);
				space_idx = a[i] - 1;
				swap(a[i], a[space_idx]);
				space_idx = i;
				if (a[space_idx_stored] != space_idx_stored + 1) {
					swap(a[space_idx_stored], a[space_idx]);
					space_idx = space_idx_stored;
				}
			}
		}
	}
}

O(n) algorithm (at most 2*n swaps)

// 0 for the gap, 1...a.length - elements, k-th element must end up in a[k-1]

public class Swapper {
  private static final int GAP_VALUE = 0;
  private final int[] a;
  private int gap;

  public Swapper(final int[] a) {
    this.a = a;
    for (int i = 0; i < a.length; i++) {
      if (GAP_VALUE == a[i]) {
        gap = i;
        break;
      }
    }
    assert gap >= 0;
  }

  public void sortWithSwap() {
    for (int i = 0; i < a.length - 1; i++) {
      if (a[i] != i + 1) { // if not in place already
        if (gap != a[i] - 1) {
          swap(a[i] - 1);
        }
        swap(i);
      }
    }
    if (a[a.length - 1] != GAP_VALUE) {
      swap(a.length - 1);
    }
  }

  private void swap(final int idx) {
    assert GAP_VALUE == a[gap];
    a[gap] = a[idx];
    a[idx] = GAP_VALUE;
    gap = idx;
  }

  public static void main(String[] args) {
    final int[] arr = {7,9,3,0,1,4,2,8,5,6};
    new Swapper(arr).sortWithSwap();
    System.out.println(Arrays.toString(arr));
  }
}

@Eirk. My first version was the same. But it doesn't always work correctly.
E.g. 0, 3, 2, 5, 4, 1 gets sorted into 1, 4, 3, 2, 5, 0.

let array = [8,4,3,7,6,'',5,2,1];
const GAP = '';

function swap(i, j) {
    if((array[i] === GAP || array[j] === GAP)) {
        let leftItem = array[i];
        array[i] = array[j];
        array[j] = leftItem;
    }
}

var combSort = function (array) {
    let interval = Math.floor(array.length/1.3);
    let count = 0;
    
    swap(array.indexOf(GAP), array.length-1);
  
    while(interval > 0) {
        for(var i=0; i+interval<array.length; i++) {
            count++;
            if (array[i] > array[i+interval]) {
                let initialGapIndex = array.indexOf(GAP);

                swap(i+interval, array.indexOf(GAP));
                swap(array.indexOf(GAP), i);
                swap(array.indexOf(GAP), initialGapIndex);
            }
        }
        
        interval = Math.floor(interval/1.3);
    }
    
    return array;
};

console.log(combSort(array));