CareerCup

How about following?
Input: sequence a

i = 1
for j = 1 to n
  if a[j] == i
     i++
return length(a)-i;

The idea behind is that when we scan a from left, all number without consecutive order should be delete and push on back. Hope it works

This can be done in O(n), or O(2*n) to be exact. Also don't need to do the swap operation.

Use a 2nd array, swapped[n] (initialized to 0), to record which number needs to be swapped. Also use a variable, min_swapped, to record the current min swapped number (initialized to n+1). Then use another variable, next_min, for the next min value (initialized to 1) which isn't marked as swapped.

The basic idea is

(1) If the current number is larger than the next_min, it needs to be swapped.
(2) If a number is larger than the current min_swapped, it also needs to be swapped.

For (1), use 234561789 as example, all the numbers (ie. 2, 3, 4, 5, 6) before 1 need to be swapped so 1 can be the first element in the array.

For (2), use the same example, 234561789. Before we parse 7, the min_swapped is 2. Thus, 7, 8, and 9 also need to be swapped because, after 2 is moved to the end of the array, 7, 8, and 9 need to be swapped so 2 can be right after 1.

a pseudo code is like following:

swap_count=0;
for (x=0; x<n; x++) {
    if (input[x]>next_min || input[x]>min_swapped) {  
        swap_count++;
        swapped[input[x]-1]=1;
        if (input[x]<min_swapped) min_swapped=input[x];
    }
    else if (input[x]==next_min) {
        for (y=next_min+1; y<=n; y++)
            if (swapped[y-1]==0) break;
        if (y==n+1) break;
        else if (y > min_swapped) {
            swap_count+=n-x-1;
            break;
        }
        else next_min=y;
    }
}

printf("swap count: %d\n", swap_count);

A question for interpretation of "How to do it less than O(n^2)"
What do you mean by "it"
you mean the algo for sorting the array?
or you mean the algo to calculate minimum steps to sort the array using swap?

How about applying quicksort algorithm on that array. While portioning the array wrt to pivot element we need swaps to find the index of pivot position. We can use above swap function to easily append all the elements > pivot to the back of the array fixing index position for pivot element. In this way we can keep swaps are always going to be O(nlogn).

When

Scan the array from the first element to last, compare consecutive elements. If first is greater then second, then swap first (put it at end of list); else continue. Do so until you don't find any unordered pairs. Something like this:

int[] input = new int[] (3, 1, 2, 4);
int a = input[0]; int b = input[1]; int i = 0;
while(b != null) {
  if (a > b) {
    input.swap(a);
  } else {
    i = i + 1;
    a = input[i];
    b = input[i+1];
  }
}

Worst case would be when list is sorted in descending order, meaning we would have to do a swap at each time, so n times.

Assumption: swap is not equal to copying and/or overwriting the value.

arr[4]= 3124

sort(arr)
{
for(int i=0;i<arr.length-1;i++)
{
if(arr[i]>arr[i+1])
{

rotate(arr,i);
}
}
}

rotate function will rotate the part of the array that is given to rotate them.

It will always rotate the array from the given point to the end of the array.

eg.
3124 -> rotate function will rotate whole array to the left by one. So 3 will be appended to end.

1243 -> if(4>3) than rotate function will rotate that array of 2 to left. So 4 will be appended to the end.

Hope this helps.

Nice explanation by all of you as Algo is easy to understand then code.....

bt all logic are quite same.... O(n^2)
no one gave sol in complexity < O(n^2) as asked in qus

Concept is below:
10, 17, 6, 5
10 compare 17 ok
17 compare 6 not-ok array{10, 6, 5, 17}
10 compare 6 not-ok array{6, 5, 17, 10}
6 compare 5 not-ok array{5, 17, 10, 6}
5 compare 17 ok
17 compare 10 not-ok array{5, 10, 6, 17}
10 compare 6 not-ok array{5, 6, 17, 10}
6 compare 17 ok
17 compare 10 not-ok array{5, 6, 10, 17}
so output 5, 6, 10, 17 and number of times swap is called 6.

include <stdio.h>
#define SIZE(x) sizeof(x)/sizeof(x[0])

void swap(int a[], int i, int j)
{
int temp = j - i;
int store = a[i];
j = i + 1;
/* first shift */
while(temp){
a[i] = a[j];
i++;
j++;
temp--;
}
a[i] = store;
printf("called\n");
}

int main()
{
int a[] = {10, 5, 7, 6, 4};
int i = 0;
int j = 1;

while(i != (SIZE(a) - 1)) {
if(a[i] < a[j]) {
i++;
j++;
} else {
swap(a, i, (SIZE(a) - 1));
if(i) {
i--;
j--;
}
}
}
return 0;
}

anon's solution provides a pattern of number of steps required to solve the problem.
One of the worst case scenario's: all numbers are in descending order

For n = 1: 0 steps
For n = 2: 1 steps
For n = 3: 3 steps
For n = 4: 6 steps
For n = 5: 10 steps
For n = 6: 15 steps

i.e. 1 + 2 + 3 + 4 + 5 ... (n-1) = O(n^2)

The actual number of swaps is determined by the first element in sequence that is out of the order in the unsorted list.

def f(arr):
    # O(n log n) time to sort the list
    n = len(arr)
    tuples = [(x, i) for i, x in enumerate(arr)]
    sorted_tuples = sorted(tuples)

    # linear time to count the swaps
    positions = [0] * n
    for i, tuple in enumerate(sorted_tuples):
        val, pos = tuple
        positions[i] = pos

    def count_swaps():
        for i in range(n - 1):
            if positions[i+1] < positions[i]:
                return n - (i + 1)
        return 0
    num_swaps = count_swaps()
    print
    print 'arr', arr
    print num_swaps, 'swaps'

    # actually performing the swaps is N-squared
    if num_swaps:
        print 'start:', arr
        which_elem = n - num_swaps
        for i in range(which_elem, n):
            pos = positions[i]
            if pos < n - 1:
                val = arr.pop(pos)
                arr.append(val)
                print 'swap: ', arr
                for j in range(n):
                    if positions[j] > pos:
                        positions[j] -= 1

arr = [2, 3, 5, 7, 11, 13]
f(arr)

arr = list(reversed(arr))
f(arr)

import random
for i in range(3):
    random.shuffle(arr)
    f(arr)

One expensive way to do a BFS taking the given array as root and having all the arrangements obtained by swapping each element as child. BFS would give the shortest path from the root to destination node (sorted array) .

def swap(a: Array[Int]): Array[Int] = {
 val len = a.length-1
 var i = 0
 var arr = a
 while(i < len){
  if(arr(i) > arr(i+1)){
   val tmp = arr(i)
   val bef = arr.take(i)
   val aft = arr.drop(i+1)
   arr = bef ++ aft :+ tmp
   i = if(i > 0) i-1 else i
  }else { i = i+1 }
 }
 arr
}

scala> val v = swap(Array(8,3,5,6,1,6,9,0,-1, 78,45))
v: Array[Int] = Array(-1, 0, 1, 3, 5, 6, 6, 8, 9, 45, 78)

Selection sort does it in n-1 swaps

Find max, append it to the end. Repeat n-1 times (but exclude the previously appended items from your scan for max)

public class SortingBySwapping {

static void swap(int [] arr1, int n){
int temp = arr1[n];
int i=0;
for(i=n ; i<arr1.length-1;i++){
arr1[i]=arr1[i+1];
}
arr1[i]= temp;
}

public static void main(String[] args) {
int[] arr1 = {3,1,2,4};
int count =0;
for(int j =0;j<arr1.length-1;j++){
if(arr1[j] > arr1[j+1]){
swap(arr1,j);
count++;
}
}
System.out.println("No of Swap "+ count);
for(int i: arr1){
System.out.print(i+" ");

}
}

}

O(N) complexity :

static int findMin(int[] a)
	{
		int mid, start = 0;
		int end = a.length -1;
		
		while(start < end){
			mid = start + (end - start)/2;
			if(a[mid] > a[end])
				start = mid + 1;
			else
				end = mid;
		}
		return start;
	}

O(N) complexity

static int findMin(int[] a)
	{
		int mid, start = 0;
		int end = a.length -1;
		
		while(start < end){
			mid = start + (end - start)/2;
			if(a[mid] > a[end])
				start = mid + 1;
			else
				end = mid;
		}
		return start;
	}

1. Maintain a min heap of size of N.
2. open a loop, and input traverse the array.
3. For every traversed element, insert the same in MinHeap(along with index).
4. Take the top of heap(minimum number so far) and swap it.
5. At the end of the loop, we will have sorted array with minimum swaps.
Space Complexity---0(n) ---- for Heap.
Time Complexity---- 0(nlogn).

do merge sort or heap sort and count the number of times swap happens... o(n log n)