CareerCup

The following pseudo code solve it in O(n) time:

index = 1
While (index <= N){
swap(a[index],a[a[index]]);
while(a[index] == index)
index++;
}

Just think for it using disjoint cycles of the given permutation
For example if N = 5, and given a permutation (3, 4, 1, 5, 2) and want to sort it

Then you have 2 disjoint cycles in this permutation
1st: 3 --> 1 --> 3
2nd: 4 --> 5 --> 2 --> 4
(generate these cycles using the index of every number, 3 will point to the 3rd place in the permutation which is 1 and 1 will show to the 1st place which is 3)

Then given these disjoint cycles, just rotate them till they are all adjusted.

Try bubble sort or comb sort.

//given an array of size n, it holds distinct integers from 1 to n. Give an algorithm to sort the array? one way is to just assign a[i]=i in the array. how to sort the array using the elements of the array and not just assigning directly

public class Sort {
	public static void main(String[] args) {
		int[] arr = { 2, 4, 1, 3 };
		int i = 0;
		int j = 0;
		while (j < arr.length-1) {
			i=j;
			int x=i+1;
			while (arr[i] != i+1) {
				swap(arr, i, x);
				x++;
			}
			j++;
		}
		
		for(int a: arr)
		{
			System.out.print(a + ", ");
		}
	}

	private static void swap(int[] arr, int x, int y) {
		int tmp = arr[x];
		arr[x] = arr[y];
		arr[y] = tmp;

	}
}

The time complexity is O(n^2), no additional space is required - O(n) - the size of the array itself

Use CountSort relatively small n

Why not directly assign? Do they contain additional data? So it is like an array of structs or something?

int i = 1
while i < length of the array
do
if arr[i] is not equal to i
then
swap arr[arr[i]] and arr[i]
else
i++