educative.io

Educative

Cyclic Sort (easy)

int j = nums[i] - 1; why this logic applied in the below code

class CyclicSort {

public static void sort(int[] nums) {

int i = 0;

while (i < nums.length) {

  int j = nums[i] - 1;

  if (nums[i] != nums[j])

    swap(nums, i, j);

  else

    i++;

}

}

private static void swap(int[] arr, int i, int j) {

int temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

}

public static void main(String[] args) {

int[] arr = new int[] { 3, 1, 5, 4, 2 };

CyclicSort.sort(arr);

for (int num : arr)

  System.out.print(num + " ");

System.out.println();

arr = new int[] { 2, 6, 4, 3, 1, 5 };

CyclicSort.sort(arr);

for (int num : arr)

  System.out.print(num + " ");

System.out.println();

arr = new int[] { 1, 5, 6, 4, 3, 2 };

CyclicSort.sort(arr);

for (int num : arr)

  System.out.print(num + " ");

System.out.println();

}

}


Course: Grokking the Coding Interview: Patterns for Coding Questions - Learn Interactively
Lesson: Cyclic Sort (easy) - Grokking the Coding Interview: Patterns for Coding Questions

Hi @rishabh_verma
Thanks for reaching out to us. In the code, the logic of writing int j = nums[i] - 1 is that it holds the value of the correct index with which we need to swap.
Let’s take an example for better clarity, let’s suppose:
We have an array of num : 2, 6, 4, 3
i points at index 0 initially it means it holds the value 2 at start
j points at index 1 it means it holds the value 6 ( j= nums[i] - 1 => num [0]-1 => 2-1 =>1, we can only calculate the value of j if we have this logic in our code j = nums[i] - 1)
Now we check the values at index i and j and so on.

Hope it will help , Happy learning :blush: