āĻŦāĻžāĻāĻžāĻ āĻšāĻ˛ āĻāĻāĻāĻŋ āĻŽā§āĻ˛āĻŋāĻ āĻā§āĻ°āĻŋāĻ¯āĻŧāĻžāĻāĻ˛āĻžāĻĒ āĻ¯āĻž āĻāĻŽāĻ°āĻž āĻŦāĻ¸ā§āĻ¤ā§āĻ¤ā§ āĻ¸āĻŽā§āĻĒāĻžāĻĻāĻ¨ āĻāĻ°āĻŋāĨ¤ āĻāĻŽāĻ¨āĻāĻŋ āĻļā§āĻļāĻŦāĻāĻžāĻ˛ā§, āĻļāĻŋāĻļā§āĻĻā§āĻ° āĻ¤āĻžāĻĻā§āĻ° āĻāĻŋāĻ¨ā§āĻ¤āĻžāĻ° āĻĻāĻā§āĻˇāĻ¤āĻž āĻŦāĻŋāĻāĻžāĻļā§āĻ° āĻ¸āĻžāĻĨā§ āĻ¸āĻžāĻĨā§ āĻ¸āĻžāĻāĻžāĻ¤ā§ āĻļā§āĻāĻžāĻ¨ā§ āĻšāĻ¯āĻŧāĨ¤ āĻāĻŽā§āĻĒāĻŋāĻāĻāĻžāĻ° āĻāĻŦāĻ āĻ¸āĻĢāĻāĻāĻ¯āĻŧā§āĻ¯āĻžāĻ° āĻāĻ° āĻŦā§āĻ¯āĻ¤āĻŋāĻā§āĻ°āĻŽ āĻ¨āĻ¯āĻŧāĨ¤ āĻāĻžāĻāĻžāĻ¤ā§ āĻŦāĻŋāĻāĻŋāĻ¨ā§āĻ¨ āĻ§āĻ°āĻŖā§āĻ° āĻ¸āĻžāĻāĻžāĻ¨ā§āĻ° āĻ
ā§āĻ¯āĻžāĻ˛āĻāĻ°āĻŋāĻĻāĻŽ āĻ°āĻ¯āĻŧā§āĻā§ āĨ¤ āĻāĻŽāĻŋ āĻāĻĒāĻ¨āĻžāĻā§ āĻ¸ā§āĻā§āĻ˛āĻŋ āĻā§ āĻāĻŦāĻ āĻā§āĻāĻžāĻŦā§ āĻāĻžāĻ āĻāĻ°ā§ āĻ¤āĻž āĻĒāĻ°ā§āĻā§āĻˇāĻž āĻāĻ°ā§ āĻĻā§āĻāĻžāĻ° āĻĒāĻ°āĻžāĻŽāĻ°ā§āĻļ āĻĻāĻŋāĻā§āĻāĻŋāĨ¤ āĻ¯āĻĻāĻŋ āĻā§āĻ¨ āĻĻāĻŋāĻ¨ āĻāĻāĻāĻŋ āĻ¸āĻžāĻā§āĻˇāĻžāĻ¤ā§āĻāĻžāĻ°ā§ āĻāĻĒāĻ¨āĻžāĻā§ āĻ¤āĻžāĻĻā§āĻ° āĻāĻāĻāĻ¨ āĻ¸āĻŽā§āĻĒāĻ°ā§āĻā§ āĻāĻŋāĻā§āĻāĻžāĻ¸āĻž āĻāĻ°āĻž āĻšāĻ¯āĻŧ?
L āĻāĻ° āĻ¸āĻŽāĻžāĻ¨ āĻšāĻ¯āĻŧā§ āĻ¯āĻžāĻ¯āĻŧ
āĻā§āĻŽāĻŋāĻāĻž
āĻ ā§āĻ¯āĻžāĻ˛āĻāĻ°āĻŋāĻĻāĻŽāĻā§āĻ˛āĻŋāĻ° āĻāĻāĻāĻŋ āĻŦāĻŋāĻāĻžāĻ āĻ¯āĻž āĻāĻāĻāĻ¨ āĻŦāĻŋāĻāĻžāĻļāĻāĻžāĻ°ā§āĻā§ āĻ āĻŦāĻļā§āĻ¯āĻ āĻāĻžāĻ¨āĻ¤ā§ āĻšāĻŦā§āĨ¤ āĻāĻŽāĻŋ āĻ¯āĻāĻ¨ āĻ¸ā§āĻā§āĻ˛ā§ āĻāĻŋāĻ˛āĻžāĻŽ āĻ¤āĻāĻ¨ āĻāĻŽā§āĻĒāĻŋāĻāĻāĻžāĻ° āĻŦāĻŋāĻā§āĻāĻžāĻ¨āĻā§ āĻāĻāĻŦāĻžāĻ° āĻā§āĻ°ā§āĻ¤ā§āĻŦā§āĻ° āĻ¸āĻžāĻĨā§ āĻ¨āĻž āĻ¨ā§āĻāĻ¯āĻŧāĻž āĻšāĻ˛ā§, āĻāĻāĻā§āĻ° āĻāĻžāĻ¤ā§āĻ°āĻ°āĻž āĻ āĻŦāĻļā§āĻ¯āĻ āĻ¸āĻžāĻāĻžāĻ¨ā§āĻ° āĻ ā§āĻ¯āĻžāĻ˛āĻāĻ°āĻŋāĻĻāĻŽāĻā§āĻ˛āĻŋ āĻŦāĻžāĻ¸ā§āĻ¤āĻŦāĻžāĻ¯āĻŧāĻ¨ āĻāĻ°āĻ¤ā§ āĻāĻŦāĻ āĻŦā§āĻāĻ¤ā§ āĻ¸āĻā§āĻˇāĻŽ āĻšāĻŦā§āĨ¤ āĻŽā§āĻ˛āĻŋāĻ āĻ ā§āĻ¯āĻžāĻ˛āĻāĻ°āĻŋāĻĻāĻŽ, āĻ¸āĻŦāĻā§āĻ¯āĻŧā§ āĻ¸āĻšāĻ, āĻāĻāĻāĻŋ āĻ˛ā§āĻĒ āĻŦā§āĻ¯āĻŦāĻšāĻžāĻ° āĻāĻ°ā§ āĻĒā§āĻ°āĻ¯āĻŧā§āĻ āĻāĻ°āĻž āĻšāĻ¯āĻŧ āĨ¤ āĻ¸ā§āĻŦāĻžāĻāĻžāĻŦāĻŋāĻāĻāĻžāĻŦā§āĻ, āĻāĻĒāĻžāĻĻāĻžāĻ¨āĻā§āĻ˛āĻŋāĻ° āĻāĻāĻāĻŋ āĻ¸āĻāĻā§āĻ°āĻš āĻŦāĻžāĻāĻžāĻ āĻāĻ°āĻžāĻ° āĻāĻ¨ā§āĻ¯, āĻ¯ā§āĻŽāĻ¨ āĻāĻāĻāĻŋ āĻ ā§āĻ¯āĻžāĻ°ā§āĻ°, āĻāĻĒāĻ¨āĻžāĻā§ āĻā§āĻ¨āĻāĻāĻžāĻŦā§ āĻ¸āĻāĻā§āĻ°āĻšā§āĻ° āĻŽāĻ§ā§āĻ¯ āĻĻāĻŋāĻ¯āĻŧā§ āĻ¯ā§āĻ¤ā§ āĻšāĻŦā§āĨ¤ āĻāĻĻāĻžāĻšāĻ°āĻŖ āĻ¸ā§āĻŦāĻ°ā§āĻĒ:int[] array = {10, 2, 10, 3, 1, 2, 5};
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
āĻā§āĻĄ āĻāĻ āĻ¸ā§āĻāĻŽā§āĻ¨ā§āĻ āĻ¸āĻŽā§āĻĒāĻ°ā§āĻā§ āĻāĻŋ āĻŦāĻ˛āĻž āĻ¯ā§āĻ¤ā§ āĻĒāĻžāĻ°ā§? āĻāĻŽāĻžāĻĻā§āĻ° āĻāĻāĻāĻŋ āĻ˛ā§āĻĒ āĻāĻā§ āĻ¯ā§āĻāĻžāĻ¨ā§ āĻāĻŽāĻ°āĻž āĻ¸ā§āĻāĻ ( int i
) 0 āĻĨā§āĻā§ āĻ
ā§āĻ¯āĻžāĻ°ā§āĻ° āĻļā§āĻˇ āĻāĻĒāĻžāĻĻāĻžāĻ¨ā§ āĻĒāĻ°āĻŋāĻŦāĻ°ā§āĻ¤āĻ¨ āĻāĻ°āĻŋāĨ¤ āĻāĻ¸āĻ˛ā§, āĻāĻŽāĻ°āĻž āĻā§āĻŦāĻ˛ āĻ
ā§āĻ¯āĻžāĻ°ā§āĻ° āĻĒā§āĻ°āĻ¤āĻŋāĻāĻŋ āĻāĻĒāĻžāĻĻāĻžāĻ¨ āĻ¨āĻŋāĻā§āĻāĻŋ āĻāĻŦāĻ āĻāĻ° āĻŦāĻŋāĻˇāĻ¯āĻŧāĻŦāĻ¸ā§āĻ¤ā§ āĻŽā§āĻĻā§āĻ°āĻŖ āĻāĻ°āĻāĻŋāĨ¤ āĻ
ā§āĻ¯āĻžāĻ°ā§āĻ¤ā§ āĻ¯āĻ¤ āĻŦā§āĻļāĻŋ āĻāĻĒāĻžāĻĻāĻžāĻ¨ āĻĨāĻžāĻāĻŦā§, āĻā§āĻĄāĻāĻŋ āĻļā§āĻˇ āĻšāĻ¤ā§ āĻ¤āĻ¤ āĻŦā§āĻļāĻŋ āĻ¸āĻŽāĻ¯āĻŧ āĻ˛āĻžāĻāĻŦā§āĨ¤ āĻ
āĻ°ā§āĻĨāĻžā§, āĻ¯āĻĻāĻŋ n
āĻāĻĒāĻžāĻĻāĻžāĻ¨ā§āĻ° āĻ¸āĻāĻā§āĻ¯āĻž āĻšāĻ¯āĻŧ, āĻāĻāĻ¨ n = 10
āĻĒā§āĻ°ā§āĻā§āĻ°āĻžāĻŽāĻāĻŋ āĻ°āĻžāĻ¨ āĻāĻ°āĻ¤ā§ āĻĻā§āĻŦāĻŋāĻā§āĻŖ āĻ¸āĻŽāĻ¯āĻŧ āĻ¨ā§āĻŦā§ āĻāĻāĻ¨ āĻĨā§āĻā§ n = 5
āĨ¤ āĻ¯āĻĻāĻŋ āĻāĻŽāĻžāĻĻā§āĻ° āĻĒā§āĻ°ā§āĻā§āĻ°āĻžāĻŽā§āĻ° āĻāĻāĻāĻŋ āĻāĻāĻ āĻ˛ā§āĻĒ āĻĨāĻžāĻā§, āĻ¤āĻžāĻšāĻ˛ā§ āĻāĻā§āĻ¸āĻŋāĻāĻŋāĻāĻļāĻ¨ā§āĻ° āĻ¸āĻŽāĻ¯āĻŧ āĻ°ā§āĻāĻŋāĻāĻāĻžāĻŦā§ āĻŦā§āĻĻā§āĻ§āĻŋ āĻĒāĻžāĻ¯āĻŧ: āĻ¯āĻ¤ āĻŦā§āĻļāĻŋ āĻāĻĒāĻžāĻĻāĻžāĻ¨ āĻĨāĻžāĻāĻŦā§, āĻāĻā§āĻ¸āĻŋāĻāĻŋāĻāĻļāĻ¨ā§āĻ° āĻ¸āĻŽāĻ¯āĻŧ āĻ¤āĻ¤ āĻŦā§āĻļāĻŋ āĻšāĻŦā§āĨ¤ āĻĻā§āĻāĻž āĻ¯āĻžāĻā§āĻā§ āĻ¯ā§ āĻāĻĒāĻ°ā§āĻ° āĻ
ā§āĻ¯āĻžāĻ˛āĻāĻ°āĻŋāĻĻāĻŽāĻāĻŋ āĻ˛āĻŋāĻ¨āĻŋāĻ¯āĻŧāĻžāĻ° āĻāĻžāĻāĻŽā§ āĻāĻžāĻ āĻāĻ°ā§ (n āĻāĻ° āĻ˛āĻŋāĻ¨āĻŋāĻ¯āĻŧāĻžāĻ° āĻĢāĻžāĻāĻļāĻ¨)āĨ¤ āĻāĻ āĻ§āĻ°āĻ¨ā§āĻ° āĻā§āĻˇā§āĻ¤ā§āĻ°ā§, āĻāĻŽāĻ°āĻž āĻŦāĻ˛āĻŋ āĻ¯ā§ āĻ
ā§āĻ¯āĻžāĻ˛āĻāĻ°āĻŋāĻĻāĻŽā§āĻ° āĻāĻāĻŋāĻ˛āĻ¤āĻž āĻšāĻ˛ "O(n)"āĨ¤ āĻāĻ āĻ¸ā§āĻŦāĻ°āĻ˛āĻŋāĻĒāĻŋāĻā§ "āĻŦāĻŋāĻ āĻ" āĻŦāĻž "āĻ
ā§āĻ¯āĻžāĻ¸āĻŋāĻŽā§āĻĒā§āĻāĻŋāĻ āĻāĻāĻ°āĻŖ"āĻ āĻŦāĻ˛āĻž āĻšāĻ¯āĻŧāĨ¤ āĻāĻŋāĻ¨ā§āĻ¤ā§ āĻ¤ā§āĻŽāĻŋ āĻļā§āĻ§ā§ āĻŽāĻ¨ā§ āĻ°āĻžāĻāĻ¤ā§ āĻĒāĻžāĻ°ā§"
āĻ¸āĻŦāĻā§āĻ¯āĻŧā§ āĻ¸āĻšāĻ āĻŦāĻžāĻāĻžāĻ āĻ ā§āĻ¯āĻžāĻ˛āĻāĻ°āĻŋāĻĻāĻŽ (āĻŦāĻžāĻŦāĻ˛ āĻŦāĻžāĻāĻžāĻ)
āĻ§āĻ°ā§āĻ¨ āĻāĻŽāĻžāĻĻā§āĻ° āĻāĻāĻāĻŋ āĻ ā§āĻ¯āĻžāĻ°ā§ āĻāĻā§ āĻāĻŦāĻ āĻāĻŽāĻ°āĻž āĻāĻāĻŋāĻ° āĻŽāĻžāĻ§ā§āĻ¯āĻŽā§ āĻĒā§āĻ¨āĻ°āĻžāĻŦā§āĻ¤ā§āĻ¤āĻŋ āĻāĻ°āĻ¤ā§ āĻĒāĻžāĻ°āĻŋāĨ¤ āĻĻāĻžāĻ°ā§āĻŖāĨ¤ āĻāĻāĻ¨ āĻāĻāĻŋāĻā§ āĻā§āĻ°āĻŽāĻŦāĻ°ā§āĻ§āĻŽāĻžāĻ¨ āĻā§āĻ°āĻŽā§ āĻ¸āĻžāĻāĻžāĻ¨ā§āĻ° āĻā§āĻˇā§āĻāĻž āĻāĻ°āĻž āĻ¯āĻžāĻāĨ¤ āĻāĻāĻžāĻ° āĻŽāĻžāĻ¨ā§ āĻāĻŋ? āĻāĻ° āĻŽāĻžāĻ¨ā§ āĻšāĻ˛ āĻ¯ā§ āĻĻā§āĻāĻŋ āĻāĻĒāĻžāĻĻāĻžāĻ¨ āĻĻā§āĻāĻ¯āĻŧāĻž āĻšāĻ¯āĻŧā§āĻā§ (āĻāĻĻāĻžāĻšāĻ°āĻŖāĻ¸ā§āĻŦāĻ°ā§āĻĒ,a = 6
, b = 5
), āĻāĻŽāĻžāĻĻā§āĻ° āĻ
āĻŦāĻļā§āĻ¯āĻ āĻĒā§āĻ¨āĻ°ā§āĻŦāĻŋāĻ¨ā§āĻ¯āĻžāĻ¸ āĻāĻ°āĻ¤ā§ āĻšāĻŦā§ a
āĻāĻŦāĻ b
āĻ¯āĻĻāĻŋ (āĻ¯āĻĻāĻŋ ) a
āĻāĻ° āĻĨā§āĻā§ āĻŦāĻĄāĻŧ āĻšāĻ¯āĻŧ āĨ¤ āĻ¯āĻāĻ¨ āĻāĻŽāĻ°āĻž āĻāĻāĻāĻŋ āĻ¸āĻāĻā§āĻ°āĻšā§āĻ° āĻ¸āĻžāĻĨā§ āĻāĻžāĻ āĻāĻ°āĻžāĻ° āĻāĻ¨ā§āĻ¯ āĻāĻāĻāĻŋ āĻ¸ā§āĻāĻ āĻŦā§āĻ¯āĻŦāĻšāĻžāĻ° āĻāĻ°āĻāĻŋ (āĻ¯ā§āĻŽāĻ¨ āĻāĻāĻāĻŋ āĻ
ā§āĻ¯āĻžāĻ°ā§āĻ° āĻā§āĻˇā§āĻ¤ā§āĻ°ā§) āĻ¤āĻāĻ¨ āĻāĻ° āĻ
āĻ°ā§āĻĨ āĻā§? āĻāĻ° āĻŽāĻžāĻ¨ā§ āĻšāĻ˛ āĻ¯ā§ āĻ¯āĻĻāĻŋ āĻ¸ā§āĻā§ a āĻ¸āĻš āĻāĻĒāĻžāĻĻāĻžāĻ¨āĻāĻŋ āĻ¸ā§āĻāĻ ( ) āĻ¸āĻš āĻāĻĒāĻžāĻĻāĻžāĻ¨āĻāĻŋāĻ° āĻā§āĻ¯āĻŧā§ āĻŦāĻĄāĻŧ āĻšāĻ¯āĻŧ āĻ¤āĻŦā§ āĻāĻĒāĻžāĻĻāĻžāĻ¨āĻā§āĻ˛āĻŋāĻā§ āĻ
āĻĻāĻ˛āĻŦāĻĻāĻ˛ āĻāĻ°āĻ¤ā§ āĻšāĻŦā§āĨ¤ āĻ¸ā§āĻĨāĻžāĻ¨ āĻĒāĻ°āĻŋāĻŦāĻ°ā§āĻ¤āĻ¨ āĻāĻ°āĻžāĻ° āĻŦāĻŋāĻāĻŋāĻ¨ā§āĻ¨ āĻāĻĒāĻžāĻ¯āĻŧ āĻāĻā§āĨ¤ āĻāĻŋāĻ¨ā§āĻ¤ā§ āĻāĻŽāĻ°āĻž āĻāĻŽāĻ¨ āĻāĻāĻāĻŋ āĻā§āĻļāĻ˛ āĻŦā§āĻ¯āĻŦāĻšāĻžāĻ° āĻāĻ°āĻŦ āĻ¯āĻž āĻ¸āĻšāĻ, āĻŦā§āĻ§āĻāĻŽā§āĻ¯ āĻāĻŦāĻ āĻŽāĻ¨ā§ āĻ°āĻžāĻāĻž āĻ¸āĻšāĻ: b
a > b
b
array[a] > array[b]
private void swap(int[] array, int ind1, int ind2) {
int tmp = array[ind1];
array[ind1] = array[ind2];
array[ind2] = tmp;
}
āĻāĻāĻ¨ āĻāĻŽāĻ°āĻž āĻ¨āĻŋāĻŽā§āĻ¨āĻ˛āĻŋāĻāĻŋāĻ¤ āĻ˛āĻŋāĻāĻ¤ā§ āĻĒāĻžāĻ°āĻŋ:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i-1);
}
}
System.out.println(Arrays.toString(array));
āĻāĻĒāĻ¨āĻŋ āĻĻā§āĻāĻ¤ā§ āĻĒāĻžāĻā§āĻā§āĻ¨, āĻāĻĒāĻžāĻĻāĻžāĻ¨āĻā§āĻ˛āĻŋ āĻ¸āĻ¤ā§āĻ¯āĻŋāĻ āĻ
āĻĻāĻ˛āĻŦāĻĻāĻ˛ āĻāĻ°āĻž āĻšāĻ¯āĻŧā§āĻāĻŋāĻ˛āĨ¤ āĻāĻŽāĻ°āĻž āĻ¸ā§āĻā§ 1 āĻĻāĻŋāĻ¯āĻŧā§ āĻļā§āĻ°ā§ āĻāĻ°ā§āĻāĻŋ, āĻāĻžāĻ°āĻŖ āĻ
ā§āĻ¯āĻžāĻ°ā§āĻ¤ā§ āĻ¯āĻĻāĻŋ āĻļā§āĻ§ā§āĻŽāĻžāĻ¤ā§āĻ° āĻāĻāĻāĻŋ āĻāĻĒāĻžāĻĻāĻžāĻ¨ āĻĨāĻžāĻā§ āĻ¤āĻŦā§ āĻ
āĻāĻŋāĻŦā§āĻ¯āĻā§āĻ¤āĻŋāĻāĻŋ array[i] < array[i-1]
index āĻāĻ° āĻāĻ¨ā§āĻ¯ āĻ
āĻŦā§āĻ§ 0
āĨ¤ āĻāĻāĻŋ āĻāĻ°āĻž āĻāĻŽāĻžāĻĻā§āĻ°āĻā§ āĻāĻŽāĻ¨ āĻā§āĻˇā§āĻ¤ā§āĻ°ā§ āĻĨā§āĻā§āĻ āĻ°āĻā§āĻˇāĻž āĻāĻ°ā§ āĻ¯ā§āĻāĻžāĻ¨ā§ āĻ
ā§āĻ¯āĻžāĻ°ā§āĻ° āĻā§āĻ¨āĻ āĻāĻĒāĻžāĻĻāĻžāĻ¨ āĻ¨ā§āĻ āĻŦāĻž āĻļā§āĻ§ā§āĻŽāĻžāĻ¤ā§āĻ° āĻāĻāĻāĻŋ āĻāĻĒāĻžāĻĻāĻžāĻ¨ āĻ¨ā§āĻ āĻāĻŦāĻ āĻāĻāĻŋ āĻā§āĻĄāĻāĻŋāĻā§ āĻāĻ°āĻ āĻāĻžāĻ˛ āĻĻā§āĻāĻžāĻ¯āĻŧāĨ¤ āĻāĻŋāĻ¨ā§āĻ¤ā§ āĻĢāĻ˛āĻžāĻĢāĻ˛ā§āĻ° āĻ
ā§āĻ¯āĻžāĻ°ā§āĻāĻŋ āĻāĻāĻ¨āĻ āĻ¸āĻžāĻāĻžāĻ¨ā§ āĻšāĻ¯āĻŧāĻ¨āĻŋ, āĻāĻžāĻ°āĻŖ āĻŦāĻžāĻāĻžāĻ āĻāĻ°āĻžāĻ° āĻāĻ¨ā§āĻ¯ āĻāĻāĻāĻŋ āĻĒāĻžāĻ¸ āĻ¯āĻĨā§āĻˇā§āĻ āĻ¨āĻ¯āĻŧāĨ¤ āĻāĻŽāĻžāĻĻā§āĻ° āĻāĻ°ā§āĻāĻāĻŋ āĻ˛ā§āĻĒ āĻ¯ā§āĻ āĻāĻ°āĻ¤ā§ āĻšāĻŦā§ āĻ¯ā§āĻāĻžāĻ¨ā§ āĻāĻŽāĻ°āĻž āĻāĻāĻāĻŋ āĻ¸āĻžāĻāĻžāĻ¨ā§ āĻ
ā§āĻ¯āĻžāĻ°ā§ āĻ¨āĻž āĻĒāĻžāĻāĻ¯āĻŧāĻž āĻĒāĻ°ā§āĻ¯āĻ¨ā§āĻ¤ āĻāĻŽāĻ°āĻž āĻŦāĻžāĻ°āĻŦāĻžāĻ° āĻĒāĻžāĻ¸ āĻ¸āĻŽā§āĻĒāĻžāĻĻāĻ¨ āĻāĻ°āĻŦ:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
boolean needIteration = true;
while (needIteration) {
needIteration = false;
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i-1);
needIteration = true;
}
}
}
System.out.println(Arrays.toString(array));
āĻ¤āĻžāĻ āĻāĻŽāĻ°āĻž āĻāĻŽāĻžāĻĻā§āĻ° āĻĒā§āĻ°āĻĨāĻŽ āĻ¸āĻžāĻāĻžāĻ¨ā§āĻ° āĻ
ā§āĻ¯āĻžāĻ˛āĻāĻ°āĻŋāĻĻāĻŽ āĻļā§āĻˇ āĻāĻ°ā§āĻāĻŋāĨ¤ āĻāĻŽāĻ°āĻž āĻŦāĻžāĻāĻ°ā§āĻ° āĻ˛ā§āĻĒ ( while
) āĻĒā§āĻ¨āĻ°āĻžāĻŦā§āĻ¤ā§āĻ¤āĻŋ āĻāĻ°āĻŋ āĻ¯āĻ¤āĻā§āĻˇāĻŖ āĻ¨āĻž āĻāĻŽāĻ°āĻž āĻ¸āĻŋāĻĻā§āĻ§āĻžāĻ¨ā§āĻ¤ āĻ¨āĻŋāĻ āĻ¯ā§ āĻāĻ° āĻā§āĻ¨ā§ āĻĒā§āĻ¨āĻ°āĻžāĻŦā§āĻ¤ā§āĻ¤āĻŋāĻ° āĻĒā§āĻ°āĻ¯āĻŧā§āĻāĻ¨ āĻ¨ā§āĻāĨ¤ āĻĄāĻŋāĻĢāĻ˛ā§āĻāĻ°ā§āĻĒā§, āĻĒā§āĻ°āĻ¤āĻŋāĻāĻŋ āĻ¨āĻ¤ā§āĻ¨ āĻĒā§āĻ¨āĻ°āĻžāĻŦā§āĻ¤ā§āĻ¤āĻŋāĻ° āĻāĻā§, āĻāĻŽāĻ°āĻž āĻ§āĻ°ā§ āĻ¨āĻŋāĻ āĻ¯ā§ āĻāĻŽāĻžāĻĻā§āĻ° āĻ
ā§āĻ¯āĻžāĻ°ā§ āĻ¸āĻžāĻāĻžāĻ¨ā§ āĻšāĻ¯āĻŧā§āĻā§ āĻāĻŦāĻ āĻāĻŽāĻžāĻĻā§āĻ° āĻāĻ° āĻ˛ā§āĻĒ āĻāĻ°āĻžāĻ° āĻĻāĻ°āĻāĻžāĻ° āĻ¨ā§āĻāĨ¤ āĻ¤āĻĻāĻ¨ā§āĻ¸āĻžāĻ°ā§, āĻāĻŽāĻ°āĻž āĻāĻĒāĻžāĻĻāĻžāĻ¨āĻā§āĻ˛āĻŋāĻ° āĻŽāĻžāĻ§ā§āĻ¯āĻŽā§ āĻā§āĻ°āĻŽāĻžāĻ¨ā§āĻ¸āĻžāĻ°ā§ āĻ¸āĻ°ā§ āĻ¯āĻžāĻ āĻāĻŦāĻ āĻāĻ āĻ
āĻ¨ā§āĻŽāĻžāĻ¨āĻāĻŋ āĻĒāĻ°ā§āĻā§āĻˇāĻž āĻāĻ°āĻŋāĨ¤ āĻāĻŋāĻ¨ā§āĻ¤ā§ āĻ¯āĻĻāĻŋ āĻāĻĒāĻžāĻĻāĻžāĻ¨āĻā§āĻ˛āĻŋ āĻā§āĻ°āĻŽāĻžāĻ¨ā§āĻ¸āĻžāĻ°ā§ āĻ¨āĻž āĻĨāĻžāĻā§, āĻ¤āĻžāĻšāĻ˛ā§ āĻāĻŽāĻ°āĻž āĻāĻĒāĻžāĻĻāĻžāĻ¨āĻā§āĻ˛āĻŋāĻā§ āĻ
āĻĻāĻ˛āĻŦāĻĻāĻ˛ āĻāĻ°āĻŋ āĻāĻŦāĻ āĻŦā§āĻāĻ¤ā§ āĻĒāĻžāĻ°āĻŋ āĻ¯ā§ āĻāĻĒāĻžāĻĻāĻžāĻ¨āĻā§āĻ˛āĻŋ āĻ¸āĻ āĻŋāĻ āĻā§āĻ°āĻŽā§ āĻ°āĻ¯āĻŧā§āĻā§ āĻāĻŋāĻ¨āĻž āĻ¤āĻž āĻāĻŽāĻžāĻĻā§āĻ° āĻāĻāĻ¨ āĻā§āĻ¨ āĻā§āĻ¯āĻžāĻ°āĻžāĻ¨ā§āĻāĻŋ āĻ¨ā§āĻāĨ¤ āĻāĻ° āĻŽāĻžāĻ¨ā§ āĻšāĻ˛ āĻ¯ā§ āĻāĻŽāĻžāĻĻā§āĻ° āĻāĻ°ā§āĻāĻāĻŋ āĻĒā§āĻ¨āĻ°āĻžāĻŦā§āĻ¤ā§āĻ¤āĻŋ āĻāĻ°āĻ¤ā§ āĻšāĻŦā§āĨ¤ āĻāĻĻāĻžāĻšāĻ°āĻŖāĻ¸ā§āĻŦāĻ°ā§āĻĒ, āĻ§āĻ°ā§āĻ¨ āĻāĻŽāĻžāĻĻā§āĻ° āĻāĻā§ [3, 5, 2]
āĨ¤ 5
āĻāĻ° āĻā§āĻ¯āĻŧā§ āĻŦā§āĻļāĻŋ 3
- āĻ¸āĻŦ āĻ āĻŋāĻ āĻāĻā§āĨ¤ āĻāĻŋāĻ¨ā§āĻ¤ā§ 2
āĻāĻ° āĻā§āĻ¯āĻŧā§ āĻāĻŽ 5
āĨ¤ āĻ¯āĻžāĻāĻšā§āĻ, [3, 2, 5]
āĻ
āĻ¨ā§āĻ¯ āĻĒāĻžāĻ¸ āĻĒā§āĻ°āĻ¯āĻŧā§āĻāĻ¨, āĻ¯ā§āĻšā§āĻ¤ā§3 > 2
āĻāĻŦāĻ āĻ¤āĻžāĻĻā§āĻ° āĻ
āĻĻāĻ˛āĻŦāĻĻāĻ˛ āĻāĻ°āĻž āĻĻāĻ°āĻāĻžāĻ°āĨ¤ āĻ¯ā§āĻšā§āĻ¤ā§ āĻāĻŽāĻ°āĻž āĻāĻāĻāĻŋ āĻ˛ā§āĻĒā§āĻ° āĻŽāĻ§ā§āĻ¯ā§ āĻāĻāĻāĻŋ āĻ˛ā§āĻĒ āĻŦā§āĻ¯āĻŦāĻšāĻžāĻ° āĻāĻ°āĻāĻŋ, āĻāĻŽāĻžāĻĻā§āĻ° āĻ
ā§āĻ¯āĻžāĻ˛āĻāĻ°āĻŋāĻĻāĻŽā§āĻ° āĻāĻāĻŋāĻ˛āĻ¤āĻž āĻŦā§āĻĻā§āĻ§āĻŋ āĻĒāĻžāĻ¯āĻŧāĨ¤ n
āĻāĻĒāĻžāĻĻāĻžāĻ¨ āĻĻā§āĻāĻ¯āĻŧāĻž āĻšāĻ˛ā§ , āĻāĻāĻŋ āĻšāĻ¯āĻŧā§ āĻ¯āĻžāĻ¯āĻŧ n * n
, āĻ
āĻ°ā§āĻĨāĻžā§, O(n^2)
. āĻāĻā§ āĻŦāĻ˛āĻž āĻšāĻ¯āĻŧ āĻĻā§āĻŦāĻŋāĻāĻžāĻ¤ āĻāĻāĻŋāĻ˛āĻ¤āĻžāĨ¤ āĻ¸āĻžāĻ§āĻžāĻ°āĻŖāĻāĻžāĻŦā§, āĻāĻŽāĻ°āĻž āĻ āĻŋāĻ āĻāĻ¤āĻā§āĻ˛āĻŋ āĻĒā§āĻ¨āĻ°āĻžāĻŦā§āĻ¤ā§āĻ¤āĻŋāĻ° āĻĒā§āĻ°āĻ¯āĻŧā§āĻāĻ¨ āĻšāĻŦā§ āĻ¤āĻž āĻāĻžāĻ¨āĻ¤ā§ āĻĒāĻžāĻ°āĻŋ āĻ¨āĻžāĨ¤ āĻāĻāĻāĻŋ āĻ
ā§āĻ¯āĻžāĻ˛āĻāĻ°āĻŋāĻĻāĻŽā§āĻ° āĻāĻāĻŋāĻ˛āĻ¤āĻžāĻ° āĻ
āĻāĻŋāĻŦā§āĻ¯āĻā§āĻ¤āĻŋ āĻĻā§āĻāĻžāĻ¯āĻŧ āĻāĻŋāĻāĻžāĻŦā§ āĻāĻāĻŋāĻ˛āĻ¤āĻž āĻ¸āĻŦāĻā§āĻ¯āĻŧā§ āĻāĻžāĻ°āĻžāĻĒ āĻā§āĻˇā§āĻ¤ā§āĻ°ā§ āĻŦā§āĻĻā§āĻ§āĻŋ āĻĒāĻžāĻ¯āĻŧāĨ¤ n
āĻ
āĻ°ā§āĻĨāĻžā§, āĻāĻāĻŋ āĻ¨āĻŋāĻ°ā§āĻĻā§āĻļ āĻāĻ°ā§ āĻ¯ā§ āĻāĻĒāĻžāĻĻāĻžāĻ¨ā§āĻ° āĻ¸āĻāĻā§āĻ¯āĻž āĻĒāĻ°āĻŋāĻŦāĻ°ā§āĻ¤āĻ¨ā§āĻ° āĻ¸āĻžāĻĨā§ āĻ¸āĻžāĻĨā§ āĻāĻžāĻ°ā§āĻ¯āĻāĻ° āĻāĻ°āĻžāĻ° āĻ¸āĻŽāĻ¯āĻŧ āĻāĻ¤āĻāĻž āĻŦāĻžāĻĄāĻŧāĻŦā§ āĨ¤ āĻŦā§āĻĻā§āĻŦā§āĻĻ āĻ¸āĻžāĻāĻžāĻ¨ā§āĻ° āĻ¸āĻšāĻāĻ¤āĻŽ āĻāĻŦāĻ āĻ¸āĻŦāĻā§āĻ¯āĻŧā§ āĻ
āĻĻāĻā§āĻˇ āĻŦāĻžāĻāĻžāĻ āĻ
ā§āĻ¯āĻžāĻ˛āĻāĻ°āĻŋāĻĻāĻŽ āĻāĻ. āĻāĻā§ āĻāĻāĻ¨ā§ āĻāĻāĻ¨ā§ "āĻ¸ā§āĻā§āĻĒāĻŋāĻĄ āĻ¸āĻ°ā§āĻ"āĻ āĻŦāĻ˛āĻž āĻšāĻ¯āĻŧāĨ¤ āĻāĻ āĻŦāĻŋāĻˇāĻ¯āĻŧā§ āĻāĻĒāĻžāĻĻāĻžāĻ¨:
āĻ¨āĻŋāĻ°ā§āĻŦāĻžāĻāĻ¨ āĻŦāĻžāĻāĻžāĻ
āĻāĻ°ā§āĻāĻāĻŋ āĻ¸āĻžāĻāĻžāĻ¨ā§āĻ° āĻ ā§āĻ¯āĻžāĻ˛āĻāĻ°āĻŋāĻĻāĻŽ āĻšāĻ˛ āĻ¨āĻŋāĻ°ā§āĻŦāĻžāĻāĻ¨ āĻ¸āĻžāĻāĻžāĻ¨ā§āĨ¤ āĻāĻāĻŋāĻ¤ā§ āĻāĻ¤ā§āĻ°ā§āĻŽā§āĻā§ āĻāĻāĻŋāĻ˛āĻ¤āĻžāĻ āĻ°āĻ¯āĻŧā§āĻā§, āĻ¤āĻŦā§ āĻāĻ°āĻ āĻĒāĻ°ā§āĨ¤ āĻ¤āĻžāĻ āĻ§āĻžāĻ°āĻŖāĻž āĻ¸āĻšāĻ. āĻĒā§āĻ°āĻ¤āĻŋāĻāĻŋ āĻĒāĻžāĻ¸ā§, āĻāĻŽāĻ°āĻž āĻā§āĻˇā§āĻĻā§āĻ°āĻ¤āĻŽ āĻāĻĒāĻžāĻĻāĻžāĻ¨ āĻ¨āĻŋāĻ°ā§āĻŦāĻžāĻāĻ¨ āĻāĻ°āĻŋ āĻāĻŦāĻ āĻāĻāĻŋāĻā§ āĻļā§āĻ°ā§āĻ¤ā§ āĻ¸ā§āĻĨāĻžāĻ¨āĻžāĻ¨ā§āĻ¤āĻ° āĻāĻ°āĻŋāĨ¤ āĻāĻĒāĻ°āĻ¨ā§āĻ¤ā§, āĻĒā§āĻ°āĻ¤āĻŋāĻāĻŋ āĻĒāĻžāĻ¸ āĻĄāĻžāĻ¨āĻĻāĻŋāĻā§ āĻāĻ āĻ§āĻžāĻĒ āĻļā§āĻ°ā§ āĻšāĻ¯āĻŧāĨ¤ āĻ āĻ¨ā§āĻ¯ āĻāĻĨāĻžāĻ¯āĻŧ, āĻĒā§āĻ°āĻĨāĻŽ āĻĒāĻžāĻ¸āĻāĻŋ āĻāĻŋāĻ°ā§āĻĨ āĻāĻĒāĻžāĻĻāĻžāĻ¨ āĻĨā§āĻā§ āĻļā§āĻ°ā§ āĻšāĻ¯āĻŧ, āĻĻā§āĻŦāĻŋāĻ¤ā§āĻ¯āĻŧ āĻĒāĻžāĻ¸āĻāĻŋ āĻĒā§āĻ°āĻĨāĻŽ āĻĨā§āĻā§ āĻāĻ¤ā§āĻ¯āĻžāĻĻāĻŋāĨ¤ āĻāĻāĻŋ āĻĻā§āĻāĻ¤ā§ āĻāĻ°āĻāĻŽ āĻšāĻŦā§:int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
int minInd = left;
for (int i = left; i < array.length; i++) {
if (array[i] < array[minInd]) {
minInd = i;
}
}
swap(array, left, minInd);
}
System.out.println(Arrays.toString(array));
āĻāĻ āĻŦāĻžāĻāĻžāĻāĻāĻŋ āĻ
āĻ¸ā§āĻĨāĻŋāĻ°, āĻāĻžāĻ°āĻŖ āĻ
āĻāĻŋāĻ¨ā§āĻ¨ āĻāĻĒāĻžāĻĻāĻžāĻ¨āĻā§āĻ˛āĻŋ (āĻāĻŽāĻ°āĻž āĻāĻĒāĻžāĻĻāĻžāĻ¨āĻā§āĻ˛āĻŋāĻā§ āĻ¸āĻžāĻāĻžāĻ¨ā§āĻ° āĻāĻ¨ā§āĻ¯ āĻ¯ā§ āĻā§āĻ¨āĻ āĻŦā§āĻļāĻŋāĻˇā§āĻā§āĻ¯ā§āĻ° āĻĒāĻ°āĻŋāĻĒā§āĻ°ā§āĻā§āĻˇāĻŋāĻ¤ā§ āĻŦā§āĻ¯āĻŦāĻšāĻžāĻ° āĻāĻ°āĻāĻŋ) āĻ¤āĻžāĻĻā§āĻ° āĻāĻĒā§āĻā§āĻˇāĻŋāĻ āĻ
āĻŦāĻ¸ā§āĻĨāĻžāĻ¨ āĻĒāĻ°āĻŋāĻŦāĻ°ā§āĻ¤āĻ¨ āĻāĻ°āĻ¤ā§ āĻĒāĻžāĻ°ā§āĨ¤ āĻāĻāĻāĻŋ āĻāĻžāĻ˛ āĻāĻĻāĻžāĻšāĻ°āĻŖ āĻāĻā§ āĻāĻāĻāĻŋāĻĒāĻŋāĻĄāĻŋāĻ¯āĻŧāĻž āĻ¨āĻŋāĻŦāĻ¨ā§āĻ§ā§ āĻ¨āĻŋāĻ°ā§āĻŦāĻžāĻāĻ¨ āĻ¸āĻžāĻāĻžāĻ¨ā§āĻ° āĻŦāĻŋāĻˇāĻ¯āĻŧā§ āĨ¤ āĻāĻ āĻŦāĻŋāĻˇāĻ¯āĻŧā§ āĻāĻĒāĻžāĻĻāĻžāĻ¨:
āĻ¸āĻ¨ā§āĻ¨āĻŋāĻŦā§āĻļ āĻŦāĻžāĻāĻžāĻ
āĻ¸āĻ¨ā§āĻ¨āĻŋāĻŦā§āĻļ āĻŦāĻžāĻāĻžāĻ āĻāĻāĻžāĻĄāĻŧāĻžāĻ āĻĻā§āĻŦāĻŋāĻāĻžāĻ¤ āĻāĻāĻŋāĻ˛āĻ¤āĻž āĻāĻā§, āĻ¯ā§āĻšā§āĻ¤ā§ āĻāĻŽāĻ°āĻž āĻāĻŦāĻžāĻ° āĻāĻāĻāĻŋ āĻ˛ā§āĻĒā§āĻ° āĻŽāĻ§ā§āĻ¯ā§ āĻāĻāĻāĻŋ āĻ˛ā§āĻĒ āĻāĻā§. āĻāĻŋ āĻ¸āĻ¨ā§āĻ¨āĻŋāĻŦā§āĻļ āĻ¸āĻžāĻāĻžāĻ¨ā§āĻ° āĻāĻŋāĻ¨ā§āĻ¨ āĻāĻ°ā§ āĻ¤ā§āĻ˛ā§? āĻāĻ āĻŦāĻžāĻāĻžāĻ āĻ ā§āĻ¯āĻžāĻ˛āĻāĻ°āĻŋāĻĻāĻŽ "āĻ¸ā§āĻĨāĻŋāĻ¤āĻŋāĻļā§āĻ˛āĨ¤" āĻāĻ° āĻŽāĻžāĻ¨ā§ āĻšāĻ˛ āĻ¯ā§ āĻ āĻāĻŋāĻ¨ā§āĻ¨ āĻāĻĒāĻžāĻĻāĻžāĻ¨āĻā§āĻ˛āĻŋ āĻ¤āĻžāĻĻā§āĻ° āĻāĻĒā§āĻā§āĻˇāĻŋāĻ āĻā§āĻ°āĻŽ āĻĒāĻ°āĻŋāĻŦāĻ°ā§āĻ¤āĻ¨ āĻāĻ°āĻŦā§ āĻ¨āĻžāĨ¤ āĻāĻŦāĻžāĻ°, āĻāĻŽāĻ°āĻž āĻ¯ā§ āĻŦā§āĻļāĻŋāĻˇā§āĻā§āĻ¯āĻā§āĻ˛āĻŋ āĻĻā§āĻŦāĻžāĻ°āĻž āĻŦāĻžāĻāĻžāĻ āĻāĻ°āĻāĻŋ āĻ¤āĻžāĻ° āĻĒāĻ°āĻŋāĻĒā§āĻ°ā§āĻā§āĻˇāĻŋāĻ¤ā§ āĻ āĻāĻŋāĻ¨ā§āĻ¨ āĻŽāĻžāĻ¨ā§āĨ¤int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
// Get an element
int value = array[left];
// Iterate through the elements that are in front of this element
int i = left - 1;
for (; i >= 0; i--) {
// If the current element is smaller, then move the larger element to the right.
if (value < array[i]) {
array[i + 1] = array[i];
} else {
// If the current element is larger, we stop
break;
}
}
// Insert the current value in the empty space
array[i + 1] = value;
}
System.out.println(Arrays.toString(array));
āĻļāĻžāĻāĻ˛ āĻ¸āĻžāĻāĻžāĻ¨ā§āĻ°
āĻāĻ°ā§āĻāĻāĻŋ āĻ¸āĻšāĻ āĻŦāĻžāĻāĻžāĻ āĻ ā§āĻ¯āĻžāĻ˛āĻāĻ°āĻŋāĻĻāĻŽ āĻāĻā§: āĻļāĻžāĻāĻ˛ āĻ¸āĻžāĻāĻžāĻ¨ā§āĻ°āĨ¤ āĻāĻāĻŋ āĻāĻāĻāĻŋ āĻĻā§āĻŦāĻŋāĻŽā§āĻā§ āĻŦā§āĻĻāĻŦā§āĻĻ āĻŦāĻž āĻāĻāĻā§āĻ˛ āĻļā§āĻāĻžāĻ° āĻ¸āĻžāĻāĻžāĻ¨ā§āĻ° āĻ¨āĻžāĻŽā§āĻ āĻĒāĻ°āĻŋāĻāĻŋāĻ¤āĨ¤ āĻāĻ āĻŦāĻŋāĻāĻ˛ā§āĻĒ āĻ¨āĻžāĻŽāĻā§āĻ˛āĻŋ āĻāĻŽāĻžāĻĻā§āĻ° āĻŦāĻ˛ā§ āĻ¯ā§ āĻļāĻžāĻāĻ˛ āĻ¸āĻžāĻāĻžāĻ¨ā§āĻ° āĻ¸ā§āĻĒā§āĻ¸ āĻļāĻžāĻāĻ˛ āĻ¸āĻŽā§āĻĒāĻ°ā§āĻā§ āĻ¨āĻ¯āĻŧāĨ¤ āĻāĻāĻŋ āĻāĻŽāĻ¨ āĻāĻŋāĻā§ āĻ¸āĻŽā§āĻĒāĻ°ā§āĻā§ āĻ¯āĻž āĻ¸āĻžāĻŽāĻ¨ā§ āĻĒāĻŋāĻāĻ¨ā§ āĻāĻ˛ā§ āĻ¯āĻžāĻ¯āĻŧāĨ¤ āĻāĻĒāĻ¨āĻŋ āĻ¯āĻāĻ¨ āĻāĻ āĻ ā§āĻ¯āĻžāĻ˛āĻāĻ°āĻŋāĻĻāĻŽāĻāĻŋ āĻŽāĻ¨ā§ āĻāĻ°ā§āĻ¨ āĻ¤āĻāĻ¨ āĻāĻĒāĻ¨āĻŋ āĻāĻāĻŋ āĻāĻžāĻŦāĻ¤ā§ āĻĒāĻžāĻ°ā§āĻ¨āĨ¤ āĻ ā§āĻ¯āĻžāĻ˛āĻāĻ°āĻŋāĻĻāĻŽ āĻ¸āĻžāĻ°āĻžāĻāĻļ āĻāĻŋ? āĻ ā§āĻ¯āĻžāĻ˛āĻāĻ°āĻŋāĻĻāĻŽā§āĻ° āĻ¸āĻžāĻ°āĻŽāĻ°ā§āĻŽ āĻšāĻ˛ āĻ¯ā§ āĻāĻŽāĻ°āĻž āĻŦāĻžāĻŽ āĻĨā§āĻā§ āĻĄāĻžāĻ¨ā§ āĻĒā§āĻ¨āĻ°āĻžāĻŦā§āĻ¤ā§āĻ¤āĻŋ āĻāĻ°āĻŋ, āĻāĻĒāĻžāĻĻāĻžāĻ¨āĻā§āĻ˛āĻŋāĻā§ āĻ āĻĻāĻ˛āĻŦāĻĻāĻ˛ āĻāĻ°āĻŋ āĻāĻŦāĻ āĻ āĻ¨ā§āĻ¯ āĻĻāĻŋāĻā§ āĻ āĻŦāĻļāĻŋāĻˇā§āĻ āĻāĻĒāĻžāĻĻāĻžāĻ¨āĻā§āĻ˛āĻŋāĻ° āĻŽāĻ§ā§āĻ¯ā§ āĻā§āĻ¨āĻāĻŋ āĻ āĻĻāĻ˛āĻŦāĻĻāĻ˛ āĻāĻ°āĻž āĻĻāĻ°āĻāĻžāĻ° āĻāĻŋāĻ¨āĻž āĻ¤āĻž āĻĒāĻ°ā§āĻā§āĻˇāĻž āĻāĻ°āĻŋāĨ¤int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i - 1);
for (int z = i - 1; (z - 1) >= 0; z--) {
if (array[z] < array[z - 1]) {
swap(array, z, z - 1);
} else {
break;
}
}
}
}
System.out.println(Arrays.toString(array));
āĻāĻ āĻŦāĻŋāĻˇāĻ¯āĻŧā§ āĻāĻĒāĻžāĻĻāĻžāĻ¨:
āĻļā§āĻ˛ āĻ¸āĻžāĻāĻžāĻ¨ā§āĻ°
āĻāĻ°ā§āĻāĻāĻŋ āĻ¸āĻšāĻ āĻŦāĻžāĻāĻžāĻ āĻ ā§āĻ¯āĻžāĻ˛āĻāĻ°āĻŋāĻĻāĻŽ āĻšāĻ˛ āĻļā§āĻ˛ āĻ¸āĻžāĻāĻžāĻ¨ā§āĨ¤ āĻāĻ° āĻ¸āĻžāĻ°āĻžāĻāĻļāĻāĻŋ āĻŦā§āĻĻāĻŦā§āĻĻ āĻ¸āĻžāĻāĻžāĻ¨ā§āĻ° āĻ āĻ¨ā§āĻ°ā§āĻĒ, āĻ¤āĻŦā§ āĻĒā§āĻ°āĻ¤āĻŋāĻāĻŋ āĻĒā§āĻ¨āĻ°āĻžāĻŦā§āĻ¤ā§āĻ¤āĻŋāĻ¤ā§ āĻāĻŽāĻžāĻĻā§āĻ° āĻ¤ā§āĻ˛āĻ¨āĻžāĻŽā§āĻ˛āĻ āĻāĻĒāĻžāĻĻāĻžāĻ¨āĻā§āĻ˛āĻŋāĻ° āĻŽāĻ§ā§āĻ¯ā§ āĻāĻāĻāĻŋ āĻāĻ˛āĻžāĻĻāĻž āĻŦā§āĻ¯āĻŦāĻ§āĻžāĻ¨ āĻ°āĻ¯āĻŧā§āĻā§āĨ¤ āĻāĻāĻŋ āĻĒā§āĻ°āĻ¤āĻŋāĻāĻŋ āĻĒā§āĻ¨āĻ°āĻžāĻŦā§āĻ¤ā§āĻ¤āĻŋāĻ° āĻ¸āĻžāĻĨā§ āĻ āĻ°ā§āĻ§ā§āĻ āĻāĻžāĻāĻž āĻšāĻ¯āĻŧāĨ¤ āĻāĻāĻžāĻ¨ā§ āĻāĻāĻāĻŋ āĻŦāĻžāĻ¸ā§āĻ¤āĻŦāĻžāĻ¯āĻŧāĻ¨ āĻāĻā§:int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
// Calculate the gap between the checked elements
int gap = array.length / 2;
// As long as there is a gap between the elements
while (gap >= 1) {
for (int right = 0; right < array.length; right++) {
// Shift the right index until we find one for which
// there is the necessary gap between it and the element before it
for (int c = right - gap; c >= 0; c -= gap) {
if (array[c] > array[c + gap]) {
swap(array, c, c + gap);
}
}
}
// Recalculate the gap
gap = gap / 2;
}
System.out.println(Arrays.toString(array));
āĻāĻ āĻŦāĻŋāĻˇāĻ¯āĻŧā§ āĻāĻĒāĻžāĻĻāĻžāĻ¨:
āĻŽāĻžāĻ°ā§āĻ āĻ¸āĻžāĻāĻžāĻ¨
āĻāĻ āĻ¸āĻšāĻ āĻŦāĻžāĻāĻžāĻ āĻ ā§āĻ¯āĻžāĻ˛āĻāĻ°āĻŋāĻĻāĻŽāĻā§āĻ˛āĻŋ āĻāĻžāĻĄāĻŧāĻžāĻ, āĻāĻ°āĻ āĻāĻāĻŋāĻ˛ āĻŦāĻžāĻāĻžāĻ āĻ ā§āĻ¯āĻžāĻ˛āĻāĻ°āĻŋāĻĻāĻŽ āĻ°āĻ¯āĻŧā§āĻā§āĨ¤ āĻāĻĻāĻžāĻšāĻ°āĻŖāĻ¸ā§āĻŦāĻ°ā§āĻĒ, āĻ¸āĻžāĻāĻžāĻ¨ āĻŽāĻžāĻ°ā§āĻ. āĻĻā§āĻāĻŋ āĻŦāĻŋāĻˇāĻ¯āĻŧ āĻ˛āĻā§āĻˇāĻ¨ā§āĻ¯āĻŧāĨ¤ āĻĒā§āĻ°āĻĨāĻŽāĻ¤, āĻĒā§āĻ¨āĻ°āĻžāĻŦā§āĻ¤ā§āĻ¤āĻŋ āĻāĻāĻžāĻ¨ā§ āĻāĻŽāĻžāĻĻā§āĻ° āĻāĻĻā§āĻ§āĻžāĻ°ā§ āĻāĻ¸ā§āĨ¤ āĻĻā§āĻŦāĻŋāĻ¤ā§āĻ¯āĻŧāĻ¤, āĻ ā§āĻ¯āĻžāĻ˛āĻāĻ°āĻŋāĻĻāĻŽā§āĻ° āĻāĻāĻŋāĻ˛āĻ¤āĻž āĻāĻ° āĻĻā§āĻŦāĻŋāĻāĻžāĻ¤ āĻ¨āĻ¯āĻŧ, āĻ¯ā§āĻŽāĻ¨āĻāĻž āĻāĻŽāĻ°āĻž āĻ āĻā§āĻ¯āĻ¸ā§āĻ¤āĨ¤ āĻāĻ āĻ ā§āĻ¯āĻžāĻ˛āĻāĻ°āĻŋāĻĻāĻŽā§āĻ° āĻāĻāĻŋāĻ˛āĻ¤āĻž āĻ˛āĻāĻžāĻ°āĻŋāĻĻāĻŽāĻŋāĻāĨ¤ āĻāĻ āĻšāĻŋāĻ¸āĻžāĻŦā§ āĻ˛ā§āĻāĻž āĻšāĻ¯āĻŧO(n log n)
. āĻ¤āĻžāĻ āĻāĻ° āĻŦāĻžāĻ¸ā§āĻ¤āĻŦāĻžāĻ¯āĻŧāĻ¨ āĻāĻ°āĻž āĻ¯āĻžāĻ. āĻĒā§āĻ°āĻĨāĻŽā§, āĻāĻŽāĻ°āĻž āĻ¸āĻžāĻāĻžāĻ¨ā§āĻ° āĻĒāĻĻā§āĻ§āĻ¤āĻŋāĻ¤ā§ āĻāĻāĻāĻŋ āĻĒā§āĻ¨āĻ°āĻžāĻŦā§āĻ¤ā§āĻ¤ āĻāĻ˛ āĻ˛āĻŋāĻāĻŦ:
public static void mergeSort(int[] source, int left, int right) {
// Select the delimiter, i.e. split the input array in half
int delimiter = left + ((right - left) / 2) + 1;
// Recursively execute this function on the two halves (if we can split the input array)
if (delimiter > 0 && right > (left + 1)) {
mergeSort(source, left, delimiter - 1);
mergeSort(source, delimiter, right);
}
}
āĻāĻāĻ¨, āĻāĻŽāĻžāĻĻā§āĻ° āĻŦāĻžāĻ¸ā§āĻ¤āĻŦāĻžāĻ¯āĻŧāĻ¨ā§ āĻŽā§āĻ˛ āĻā§āĻ°āĻŋāĻ¯āĻŧāĻž āĻ¯ā§āĻ āĻāĻ°āĻž āĻ¯āĻžāĻāĨ¤ āĻāĻāĻžāĻ¨ā§ āĻāĻŽāĻžāĻĻā§āĻ° āĻ¸ā§āĻĒāĻžāĻ° āĻĒāĻĻā§āĻ§āĻ¤āĻŋ:
public static void mergeSort(int[] source, int left, int right) {
// Select the delimiter, i.e. split the input array in half
int delimiter = left + ((right - left) / 2) + 1;
// Recursively execute this function on the two halves (if we can split the input array)
if (delimiter > 0 && right > (left + 1)) {
mergeSort(source, left, delimiter - 1);
mergeSort(source, delimiter, right);
}
// Create a temporary array with the required size
int[] buffer = new int[right - left + 1];
// Starting from the specified left index, go through each element.
int cursor = left;
for (int i = 0; i < buffer.length; i++) {
// We use delimeter to point to the element on the right half
// If delimeter> right, then the right half has no elements that haven't been added
if (delimiter > right || source[cursor] > source[delimiter]) {
buffer[i] = source[cursor];
cursor++;
} else {
buffer[i] = source[delimiter];
delimiter++;
}
}
System.arraycopy(buffer, 0, source, left, buffer.length);
}
āĻāĻŽāĻ°āĻž āĻāĻ˛ āĻāĻ°ā§ āĻāĻŽāĻžāĻĻā§āĻ° āĻāĻĻāĻžāĻšāĻ°āĻŖ āĻāĻžāĻ˛āĻžāĻ¤ā§ āĻĒāĻžāĻ°āĻŋmergeSort(array, 0, array.length-1)
. āĻ¯ā§āĻŽāĻ¨ āĻāĻĒāĻ¨āĻŋ āĻĻā§āĻāĻ¤ā§ āĻĒāĻžāĻā§āĻā§āĻ¨, āĻĒā§āĻ°āĻā§āĻ°āĻŋāĻ¯āĻŧāĻžāĻāĻŋ āĻāĻāĻāĻŋ āĻāĻ¨āĻĒā§āĻ āĻ
ā§āĻ¯āĻžāĻ°ā§ āĻā§āĻ°āĻšāĻŖ āĻāĻ°āĻžāĻ° āĻāĻ¨ā§āĻ¯ āĻĢā§āĻā§ āĻāĻ ā§ āĻāĻŦāĻ āĻ¸ā§āĻ āĻŦāĻŋāĻāĻžāĻā§āĻ° āĻļā§āĻ°ā§ āĻāĻŦāĻ āĻļā§āĻˇā§āĻ° āĻāĻā§āĻāĻŋāĻ¤ āĻĻā§āĻ¯āĻŧ āĻ¯āĻž āĻ¸āĻžāĻāĻžāĻ¨ā§ āĻĻāĻ°āĻāĻžāĻ°āĨ¤ āĻŦāĻžāĻāĻžāĻ āĻļā§āĻ°ā§ āĻšāĻ˛ā§, āĻāĻ āĻ
ā§āĻ¯āĻžāĻ°ā§āĻ° āĻļā§āĻ°ā§ āĻāĻŦāĻ āĻļā§āĻˇ āĻšāĻ¯āĻŧ. āĻ¤āĻžāĻ°āĻĒāĻ° āĻāĻŽāĻ°āĻž āĻĄāĻŋāĻ˛āĻŋāĻŽāĻŋāĻāĻžāĻ° āĻāĻŖāĻ¨āĻž āĻāĻ°āĻŋ, āĻ¯ā§āĻāĻŋ āĻ¸ā§āĻāĻ āĻ¯ā§āĻāĻžāĻ¨ā§ āĻāĻŽāĻ°āĻž āĻ
ā§āĻ¯āĻžāĻ°ā§āĻā§ āĻŦāĻŋāĻāĻā§āĻ¤ āĻāĻ°āĻŦāĨ¤ āĻ¯āĻĻāĻŋ āĻ
ā§āĻ¯āĻžāĻ°ā§āĻāĻŋāĻā§ 2 āĻāĻžāĻā§ āĻāĻžāĻ āĻāĻ°āĻž āĻ¯āĻžāĻ¯āĻŧ, āĻ¤āĻŦā§ āĻāĻŽāĻ°āĻž āĻ
ā§āĻ¯āĻžāĻ°ā§āĻ° āĻĻā§āĻāĻŋ āĻ
āĻ°ā§āĻ§ā§āĻā§āĻ° āĻāĻ¨ā§āĻ¯ āĻŦāĻžāĻ°āĻŦāĻžāĻ° āĻ¸āĻžāĻāĻžāĻ¨ā§āĻ° āĻĒāĻĻā§āĻ§āĻ¤āĻŋāĻāĻŋāĻā§ āĻŦāĻ˛āĻŋāĨ¤ āĻāĻŽāĻ°āĻž āĻāĻāĻāĻŋ āĻ
āĻā§āĻāĻŋāĻ˛āĻŋāĻ¯āĻŧāĻžāĻ°ā§ āĻŦāĻžāĻĢāĻžāĻ° āĻĒā§āĻ°āĻ¸ā§āĻ¤ā§āĻ¤ āĻāĻ°āĻŋ āĻ¯ā§āĻāĻžāĻ¨ā§ āĻāĻŽāĻ°āĻž āĻ¸āĻžāĻāĻžāĻ¨ā§ āĻŦāĻŋāĻāĻžāĻāĻāĻŋ āĻ¸āĻ¨ā§āĻ¨āĻŋāĻŦā§āĻļ āĻāĻ°āĻŦāĨ¤ āĻāĻ°āĻĒāĻ°ā§, āĻ¸āĻžāĻāĻžāĻ¨ā§āĻ° āĻāĻ¨ā§āĻ¯ āĻŦāĻŋāĻāĻžāĻā§āĻ° āĻļā§āĻ°ā§āĻ¤ā§ āĻ¸ā§āĻā§ āĻ¸ā§āĻ āĻāĻ°ā§āĻ¨ āĻāĻŦāĻ āĻāĻžāĻ˛āĻŋ āĻŦāĻžāĻĢāĻžāĻ°ā§āĻ° āĻĒā§āĻ°āĻ¤āĻŋāĻāĻŋ āĻāĻĒāĻžāĻĻāĻžāĻ¨ā§āĻ° āĻŽāĻ§ā§āĻ¯ āĻĻāĻŋāĻ¯āĻŧā§ āĻšāĻžāĻāĻāĻž āĻļā§āĻ°ā§ āĻāĻ°ā§āĻ¨, āĻāĻāĻŋ āĻā§āĻˇā§āĻĻā§āĻ°āĻ¤āĻŽ āĻāĻĒāĻžāĻĻāĻžāĻ¨ āĻĻāĻŋāĻ¯āĻŧā§ āĻĒā§āĻ°āĻŖ āĻāĻ°ā§āĻ¨āĨ¤ āĻ¯āĻĻāĻŋ āĻ¸ā§āĻāĻ āĻĻā§āĻŦāĻžāĻ°āĻž āĻ¨āĻŋāĻ°ā§āĻĻā§āĻļāĻŋāĻ¤ āĻāĻĒāĻžāĻĻāĻžāĻ¨āĻāĻŋ āĻŦāĻŋāĻāĻžāĻāĻ¨āĻāĻžāĻ°ā§ āĻĻā§āĻŦāĻžāĻ°āĻž āĻ¨āĻŋāĻ°ā§āĻĻā§āĻļāĻŋāĻ¤ āĻāĻĒāĻžāĻĻāĻžāĻ¨ā§āĻ° āĻā§āĻ¯āĻŧā§ āĻāĻŽ āĻšāĻ¯āĻŧ, āĻāĻŽāĻ°āĻž āĻāĻĒāĻžāĻĻāĻžāĻ¨āĻāĻŋāĻā§ āĻŦāĻžāĻĢāĻžāĻ°ā§ āĻ°āĻžāĻāĻŋ āĻāĻŦāĻ āĻ¸ā§āĻāĻāĻāĻŋ āĻ¸ā§āĻĨāĻžāĻ¨āĻžāĻ¨ā§āĻ¤āĻ° āĻāĻ°āĻŋāĨ¤ āĻ
āĻ¨ā§āĻ¯āĻĨāĻžāĻ¯āĻŧ, āĻāĻŽāĻ°āĻž āĻĄāĻŋāĻ˛āĻŋāĻŽāĻŋāĻāĻžāĻ° āĻĻā§āĻŦāĻžāĻ°āĻž āĻ¨āĻŋāĻ°ā§āĻĻā§āĻļāĻŋāĻ¤ āĻāĻĒāĻžāĻĻāĻžāĻ¨āĻāĻŋāĻā§ āĻŦāĻžāĻĢāĻžāĻ°ā§ āĻ°āĻžāĻāĻŋ āĻāĻŦāĻ āĻŦāĻŋāĻāĻžāĻāĻ¨āĻāĻžāĻ°ā§ āĻ¸ā§āĻĨāĻžāĻ¨āĻžāĻ¨ā§āĻ¤āĻ° āĻāĻ°āĻŋāĨ¤ āĻ¯āĻ¤ āĻ¤āĻžāĻĄāĻŧāĻžāĻ¤āĻžāĻĄāĻŧāĻŋ āĻĄāĻŋāĻ˛āĻŋāĻŽāĻŋāĻāĻžāĻ° āĻŦāĻžāĻāĻžāĻ āĻāĻ°āĻž āĻŦāĻŋāĻāĻžāĻā§āĻ° āĻ¸ā§āĻŽāĻžāĻ¨āĻž āĻ
āĻ¤āĻŋāĻā§āĻ°āĻŽ āĻāĻ°ā§ āĻŦāĻž āĻāĻŽāĻ°āĻž āĻ¸āĻŽā§āĻĒā§āĻ°ā§āĻŖ āĻ
ā§āĻ¯āĻžāĻ°ā§ āĻĒā§āĻ°āĻŖ āĻāĻ°āĻŋ, āĻ¨āĻŋāĻ°ā§āĻĻāĻŋāĻˇā§āĻ āĻĒāĻ°āĻŋāĻ¸āĻ°āĻāĻŋ āĻ¸āĻžāĻāĻžāĻ¨ā§ āĻŦāĻ˛ā§ āĻŽāĻ¨ā§ āĻāĻ°āĻž āĻšāĻ¯āĻŧāĨ¤āĻāĻ āĻŦāĻŋāĻˇāĻ¯āĻŧā§ āĻāĻĒāĻžāĻĻāĻžāĻ¨:
- CS50: āĻ¸āĻžāĻāĻžāĻ¨ā§āĻ° āĻŽāĻžāĻ°ā§āĻ
- āĻāĻāĻĄāĻŋāĻ¯āĻŧāĻž āĻ¨āĻŋāĻ°ā§āĻĻā§āĻļāĻžāĻŦāĻ˛ā§ - āĻŽāĻžāĻ°ā§āĻ āĻ¸āĻžāĻāĻžāĻ¨
āĻāĻžāĻāĻ¨ā§āĻāĻŋāĻ āĻ¸āĻ°ā§āĻ āĻāĻŦāĻ āĻ°ā§āĻĄāĻŋāĻā§āĻ¸ āĻŦāĻžāĻāĻžāĻ
āĻāĻ°ā§āĻāĻāĻŋ āĻāĻāĻ°ā§āĻˇāĻŖā§āĻ¯āĻŧ āĻ¸āĻžāĻāĻžāĻ¨ā§āĻ° āĻ ā§āĻ¯āĻžāĻ˛āĻāĻ°āĻŋāĻĻāĻŽ āĻšāĻ˛ āĻāĻŖāĻ¨āĻž āĻ¸āĻžāĻāĻžāĻ¨ā§āĨ¤ āĻāĻāĻžāĻ¨ā§ āĻ ā§āĻ¯āĻžāĻ˛āĻāĻ°āĻŋāĻĻāĻŽāĻŋāĻ āĻāĻāĻŋāĻ˛āĻ¤āĻž āĻšāĻ˛O(n+k)
, āĻ¯ā§āĻāĻžāĻ¨ā§ n
āĻāĻĒāĻžāĻĻāĻžāĻ¨ā§āĻ° āĻ¸āĻāĻā§āĻ¯āĻž āĻāĻŦāĻ k
āĻāĻāĻāĻŋ āĻāĻĒāĻžāĻĻāĻžāĻ¨ā§āĻ° āĻ¸āĻ°ā§āĻŦā§āĻā§āĻ āĻŽāĻžāĻ¨āĨ¤ āĻāĻ āĻ
ā§āĻ¯āĻžāĻ˛āĻāĻ°āĻŋāĻĻāĻŽā§āĻ° āĻāĻāĻāĻŋ āĻ¤ā§āĻ°ā§āĻāĻŋ āĻ°āĻ¯āĻŧā§āĻā§: āĻāĻŽāĻžāĻĻā§āĻ° āĻ
ā§āĻ¯āĻžāĻ°ā§āĻ° āĻ¸āĻ°ā§āĻŦāĻ¨āĻŋāĻŽā§āĻ¨ āĻāĻŦāĻ āĻ¸āĻ°ā§āĻŦāĻžāĻ§āĻŋāĻ āĻŽāĻžāĻ¨āĻā§āĻ˛āĻŋ āĻāĻžāĻ¨āĻ¤ā§ āĻšāĻŦā§āĨ¤ āĻāĻāĻžāĻ¨ā§ āĻāĻŖāĻ¨āĻž āĻ¸āĻžāĻāĻžāĻ¨ā§āĻ° āĻāĻāĻāĻŋ āĻāĻĻāĻžāĻšāĻ°āĻŖ:
public static int[] countingSort(int[] theArray, int maxValue) {
// An array of "counters", ranging from 0 to the maximum value
int numCounts[] = new int[maxValue + 1];
// We increase the counter in the corresponding cell (index = value)
for (int num : theArray) {
numCounts[num]++;
}
// Create an array to hold the sorted result
int[] sortedArray = new int[theArray.length];
int currentSortedIndex = 0;
// Run through the array of "counters"
for (int n = 0; n < numCounts.length; n++) {
int count = numCounts[n];
// Run through the number of values
for (int k = 0; k < count; k++) {
sortedArray[currentSortedIndex] = n;
currentSortedIndex++;
}
}
return sortedArray;
}
āĻāĻĒāĻ¨āĻŋ āĻŦā§āĻāĻ¤ā§ āĻĒāĻžāĻ°ā§āĻ¨ āĻ¯ā§ āĻāĻāĻŋ āĻā§āĻŦ āĻ
āĻ¸ā§āĻŦāĻŋāĻ§āĻžāĻāĻ¨āĻ āĻ¯āĻāĻ¨ āĻāĻŽāĻžāĻĻā§āĻ° āĻ¸āĻ°ā§āĻŦāĻ¨āĻŋāĻŽā§āĻ¨ āĻāĻŦāĻ āĻ¸āĻ°ā§āĻŦāĻžāĻ§āĻŋāĻ āĻŽāĻžāĻ¨āĻā§āĻ˛āĻŋ āĻāĻā§ āĻĨā§āĻā§ āĻāĻžāĻ¨āĻ¤ā§ āĻšāĻŦā§āĨ¤ āĻāĻŦāĻ āĻāĻŽāĻ°āĻž āĻāĻāĻžāĻ¨ā§ āĻāĻ°ā§āĻāĻāĻŋ āĻ
ā§āĻ¯āĻžāĻ˛āĻāĻ°āĻŋāĻĻāĻŽ āĻĒā§āĻ¯āĻŧā§āĻāĻŋ: āĻ°ā§āĻĄāĻŋāĻā§āĻ¸ āĻ¸āĻ°ā§āĻāĨ¤ āĻāĻŽāĻŋ āĻāĻāĻžāĻ¨ā§ āĻļā§āĻ§ā§āĻŽāĻžāĻ¤ā§āĻ° āĻĻā§āĻļā§āĻ¯āĻ¤ āĻ
ā§āĻ¯āĻžāĻ˛āĻāĻ°āĻŋāĻĻāĻŽ āĻāĻĒāĻ¸ā§āĻĨāĻžāĻĒāĻ¨ āĻāĻ°āĻŦāĨ¤ āĻŦāĻžāĻ¸ā§āĻ¤āĻŦāĻžāĻ¯āĻŧāĻ¨ā§āĻ° āĻāĻ¨ā§āĻ¯ āĻ¸āĻŽā§āĻĒā§āĻ°āĻ āĻāĻĒāĻāĻ°āĻŖ āĻĻā§āĻā§āĻ¨: āĻāĻĒāĻāĻ°āĻŖ:
- āĻŦāĻžāĻāĻžāĻ āĻāĻŖāĻ¨āĻž āĻ¸āĻŽā§āĻĒāĻ°ā§āĻā§ āĻāĻŋāĻĄāĻŋāĻ
- āĻāĻŖāĻ¨āĻž āĻ¸āĻžāĻāĻžāĻ¨ā§āĻ° āĻ ā§āĻ¯āĻžāĻ˛āĻāĻ°āĻŋāĻĻāĻŽ
āĻĻā§āĻ°ā§āĻ¤ āĻŦāĻžāĻāĻžāĻ
āĻ āĻŋāĻ āĻāĻā§, āĻāĻāĻŋ āĻĄā§āĻāĻžāĻ°ā§āĻā§āĻ° āĻāĻ¨ā§āĻ¯ āĻ¸āĻŽāĻ¯āĻŧ - āĻĻā§āĻ°ā§āĻ¤ āĻŦāĻžāĻāĻžāĻ, āĻ¸āĻŦāĻā§āĻ¯āĻŧā§ āĻŦāĻŋāĻā§āĻ¯āĻžāĻ¤ āĻ¸āĻžāĻāĻžāĻ¨ā§āĻ° āĻ ā§āĻ¯āĻžāĻ˛āĻāĻ°āĻŋāĻĻāĻŽāĻā§āĻ˛āĻŋāĻ° āĻŽāĻ§ā§āĻ¯ā§ āĻāĻāĻāĻŋā§ˇ āĻāĻ° āĻ˛āĻāĻžāĻ°āĻŋāĻĻāĻŽāĻŋāĻ āĻāĻāĻŋāĻ˛āĻ¤āĻž āĻ°āĻ¯āĻŧā§āĻā§O(n log n)
: āĻāĻ āĻ¸āĻžāĻāĻžāĻ¨ā§āĻ° āĻ
ā§āĻ¯āĻžāĻ˛āĻāĻ°āĻŋāĻĻāĻŽ āĻāĻ¨āĻŋ āĻšā§āĻ¯āĻŧāĻžāĻ° āĻĻā§āĻŦāĻžāĻ°āĻž āĻ¤ā§āĻ°āĻŋ āĻāĻ°āĻž āĻšāĻ¯āĻŧā§āĻāĻŋāĻ˛āĨ¤ āĻŽāĻāĻžāĻ° āĻŦāĻŋāĻˇāĻ¯āĻŧ āĻšāĻ˛, āĻ¤āĻŋāĻ¨āĻŋ āĻ¸ā§āĻāĻŋāĻ¯āĻŧā§āĻ¤ āĻāĻāĻ¨āĻŋāĻ¯āĻŧāĻ¨ā§ āĻĨāĻžāĻāĻžāĻ° āĻ¸āĻŽāĻ¯āĻŧ āĻāĻāĻŋ āĻāĻŦāĻŋāĻˇā§āĻāĻžāĻ° āĻāĻ°ā§āĻāĻŋāĻ˛ā§āĻ¨, āĻ¯ā§āĻāĻžāĻ¨ā§ āĻ¤āĻŋāĻ¨āĻŋ āĻŽāĻ¸ā§āĻā§ āĻŦāĻŋāĻļā§āĻŦāĻŦāĻŋāĻĻā§āĻ¯āĻžāĻ˛āĻ¯āĻŧā§ āĻŽā§āĻļāĻŋāĻ¨ āĻ
āĻ¨ā§āĻŦāĻžāĻĻ āĻ
āĻ§ā§āĻ¯āĻ¯āĻŧāĻ¨ āĻāĻ°ā§āĻāĻŋāĻ˛ā§āĻ¨ āĻāĻŦāĻ āĻāĻāĻāĻŋ āĻ°āĻžāĻļāĻŋāĻ¯āĻŧāĻžāĻ¨-āĻāĻāĻ°ā§āĻāĻŋ āĻļāĻŦā§āĻĻāĻā§āĻā§āĻ āĻŦāĻ āĻ¤ā§āĻ°āĻŋ āĻāĻ°ā§āĻāĻŋāĻ˛ā§āĻ¨āĨ¤ āĻāĻ°āĻ āĻāĻŋ, āĻāĻžāĻāĻž āĻāĻ āĻ
ā§āĻ¯āĻžāĻ˛āĻāĻ°āĻŋāĻĻāĻŽā§āĻ° āĻāĻ°āĻ āĻāĻāĻŋāĻ˛ āĻ¸āĻāĻ¸ā§āĻāĻ°āĻŖ āĻŦā§āĻ¯āĻŦāĻšāĻžāĻ° āĻāĻ°ā§ Arrays.sort
āĨ¤ āĻāĻŋ āĻ¸āĻŽā§āĻĒāĻ°ā§āĻā§ Collections.sort
? āĻā§āĻ¨ āĻāĻŋāĻ¨āĻŋāĻ¸āĻā§āĻ˛āĻŋ "āĻšā§āĻĄā§āĻ° āĻ¨ā§āĻā§" āĻ¸āĻžāĻāĻžāĻ¨ā§ āĻšāĻ¯āĻŧ āĻ¤āĻž āĻĻā§āĻā§ āĻ¨āĻŋāĻ¨ āĻ¨āĻž? āĻāĻāĻžāĻ¨ā§ āĻā§āĻĄ āĻāĻā§:
public static void quickSort(int[] source, int leftBorder, int rightBorder) {
int leftMarker = leftBorder;
int rightMarker = rightBorder;
int pivot = source[(leftMarker + rightMarker) / 2];
do {
// Move the left marker from left to right as long as the element is less than pivot
while (source[leftMarker] < pivot) {
leftMarker++;
}
// Move the right marker as long as the element is greater than pivot
while (source[rightMarker] > pivot) {
rightMarker--;
}
// Check whether we need to swap the elements pointed to by the markers
if (leftMarker <= rightMarker) {
// The left marker will be less than the right one only if we need to do a swap
if (leftMarker < rightMarker) {
int tmp = source[leftMarker];
source[leftMarker] = source[rightMarker];
source[rightMarker] = tmp;
}
// Shift the markers to get new borders
leftMarker++;
rightMarker--;
}
} while (leftMarker <= rightMarker);
// Execute recursively on the parts
if (leftMarker < rightBorder) {
quickSort(source, leftMarker, rightBorder);
}
if (leftBorder < rightMarker) {
quickSort(source, leftBorder, rightMarker);
}
}
āĻāĻ āĻ¸āĻŦ āĻā§āĻŦ āĻā§āĻ¤āĻŋāĻāĻ° āĻāĻĒāĻžāĻĻāĻžāĻ¨, āĻ¤āĻžāĻ āĻāĻāĻŋ āĻāĻ¨āĻ¨ āĻāĻ°āĻž āĻ¯āĻžāĻ. āĻāĻ¨āĻĒā§āĻ āĻ
ā§āĻ¯āĻžāĻ°ā§āĻ° āĻāĻ¨ā§āĻ¯ ( int[]
āĻāĻ¤ā§āĻ¸), āĻāĻŽāĻ°āĻž āĻĻā§āĻāĻŋ āĻŽāĻžāĻ°ā§āĻāĻžāĻ° āĻ¤ā§āĻ°āĻŋ āĻāĻ°āĻŋ: āĻŦāĻžāĻŽ ( L
) āĻāĻŦāĻ āĻĄāĻžāĻ¨ ( R
)āĨ¤ āĻĒā§āĻ°āĻĨāĻŽ āĻĒāĻĻā§āĻ§āĻ¤āĻŋ āĻāĻ˛ā§āĻ° āĻ¸āĻŽāĻ¯āĻŧ, āĻ¤āĻžāĻ°āĻž āĻ
ā§āĻ¯āĻžāĻ°ā§āĻ° āĻļā§āĻ°ā§ āĻāĻŦāĻ āĻļā§āĻˇā§āĻ° āĻ¸āĻžāĻĨā§ āĻ¸āĻā§āĻāĻ¤āĻŋāĻĒā§āĻ°ā§āĻŖāĨ¤ āĻ¤āĻžāĻ°āĻĒāĻ° āĻāĻŽāĻ°āĻž āĻĒāĻŋāĻāĻ āĻāĻĒāĻžāĻĻāĻžāĻ¨ āĻ¸āĻ¨āĻžāĻā§āĻ¤ āĻāĻ°āĻŋ, āĻ¯āĻž āĻ¯āĻĨāĻžāĻ¯āĻĨāĻāĻžāĻŦā§ āĻ¨āĻžāĻŽāĻāĻ°āĻŖ āĻāĻ°āĻž āĻšāĻ¯āĻŧ pivot
āĨ¤ pivot
āĻāĻ° āĻĒāĻ°ā§, āĻāĻŽāĻžāĻĻā§āĻ° āĻāĻžāĻ āĻšāĻ˛ -āĻāĻ° āĻĨā§āĻā§ āĻā§āĻ āĻŽāĻžāĻ¨āĻā§āĻ˛āĻŋāĻā§ āĻŦāĻžāĻŽ āĻĻāĻŋāĻā§ pivot
āĻāĻŦāĻ āĻŦāĻĄāĻŧāĻā§āĻ˛āĻŋāĻā§ â āĻĄāĻžāĻ¨āĻĻāĻŋāĻā§ āĻ¸āĻ°āĻžāĻ¨ā§ ā§ˇ āĻāĻāĻŋ āĻāĻ°āĻžāĻ° āĻāĻ¨ā§āĻ¯, āĻāĻŽāĻ°āĻž āĻĒā§āĻ°āĻĨāĻŽā§ L
āĻŽāĻžāĻ°ā§āĻāĻžāĻ°āĻāĻŋ āĻ¸āĻ°āĻžāĻ¤ā§ āĻĨāĻžāĻāĻŋ āĻ¯āĻ¤āĻā§āĻˇāĻŖ āĻ¨āĻž āĻāĻŽāĻ°āĻž āĻāĻ° āĻĨā§āĻā§ āĻŦāĻĄāĻŧ āĻāĻāĻāĻŋ āĻŽāĻžāĻ¨ āĻā§āĻāĻā§ āĻĒāĻžāĻ pivot
āĨ¤ āĻ¯āĻĻāĻŋ āĻā§āĻ¨ āĻā§āĻ āĻŽāĻžāĻ¨ āĻĒāĻžāĻāĻ¯āĻŧāĻž āĻ¯āĻžāĻ¯āĻŧ āĻ¨āĻž, āĻ¤āĻžāĻšāĻ˛ā§pivot
āĨ¤ āĻ¤āĻžāĻ°āĻĒāĻ°ā§ āĻāĻŽāĻ°āĻž
R
āĻŽāĻžāĻ°ā§āĻāĻžāĻ°āĻāĻŋ āĻ¸āĻ°āĻžāĻ¤ā§ āĻĨāĻžāĻāĻŋ āĻ¯āĻ¤āĻā§āĻˇāĻŖ āĻ¨āĻž āĻāĻŽāĻ°āĻž āĻāĻ° āĻĨā§āĻā§ āĻā§āĻ āĻāĻāĻāĻŋ āĻŽāĻžāĻ¨ āĻā§āĻāĻā§ āĻĒāĻžāĻ
pivot
āĨ¤ āĻ¯āĻĻāĻŋ āĻā§āĻ¨ āĻŦāĻĄāĻŧ āĻŽāĻžāĻ¨ āĻĒāĻžāĻāĻ¯āĻŧāĻž āĻ¨āĻž āĻ¯āĻžāĻ¯āĻŧ, āĻ¤āĻžāĻšāĻ˛ā§
R
āĻ¸āĻŽāĻžāĻ¨ āĻšāĻ¯āĻŧā§ āĻ¯āĻžāĻ¯āĻŧ
pivot
āĨ¤ āĻāĻ° āĻĒāĻ°ā§, āĻ¯āĻĻāĻŋ
L
āĻŽāĻžāĻ°ā§āĻāĻžāĻ°āĻāĻŋ āĻŽāĻžāĻ°ā§āĻāĻžāĻ°ā§āĻ° āĻāĻā§ āĻĨāĻžāĻā§
R
āĻŦāĻž āĻāĻāĻŋāĻ° āĻ¸āĻžāĻĨā§ āĻŽāĻŋāĻ˛ā§ āĻ¯āĻžāĻ¯āĻŧ, āĻ¤āĻžāĻšāĻ˛ā§ āĻāĻŽāĻ°āĻž āĻāĻĒāĻžāĻĻāĻžāĻ¨āĻā§āĻ˛āĻŋāĻā§ āĻ
āĻĻāĻ˛āĻŦāĻĻāĻ˛ āĻāĻ°āĻžāĻ° āĻā§āĻˇā§āĻāĻž āĻāĻ°āĻŋ āĻ¯āĻĻāĻŋ āĻāĻĒāĻžāĻĻāĻžāĻ¨āĻāĻŋ
L
āĻāĻĒāĻžāĻĻāĻžāĻ¨āĻāĻŋāĻ° āĻā§āĻ¯āĻŧā§ āĻāĻŽ āĻšāĻ¯āĻŧ
R
āĨ¤ āĻ¤āĻžāĻ°āĻĒāĻ°ā§ āĻāĻŽāĻ°āĻž
L
1 āĻĻā§āĻŦāĻžāĻ°āĻž āĻĄāĻžāĻ¨āĻĻāĻŋāĻā§ āĻ¸āĻ°ā§ āĻ¯āĻžāĻ, āĻāĻŦāĻ āĻāĻŽāĻ°āĻž
R
1 āĻĻā§āĻŦāĻžāĻ°āĻž āĻŦāĻžāĻŽā§ āĻ¸ā§āĻĨāĻžāĻ¨āĻžāĻ¨ā§āĻ¤āĻ°āĻŋāĻ¤ āĻšāĻāĨ¤ āĻ¯āĻāĻ¨
L
āĻŽāĻžāĻ°ā§āĻāĻžāĻ°āĻāĻŋ āĻŽāĻžāĻ°ā§āĻāĻžāĻ°ā§āĻ° āĻŦāĻžāĻāĻ°ā§ āĻāĻ˛ā§ āĻ¯āĻžāĻ¯āĻŧ
R
, āĻ¤āĻāĻ¨ āĻāĻ° āĻ
āĻ°ā§āĻĨ āĻšāĻ˛ āĻ
āĻĻāĻ˛āĻŦāĻĻāĻ˛ āĻ¸āĻŽā§āĻĒā§āĻ°ā§āĻŖ āĻšāĻ¯āĻŧā§āĻā§: āĻā§āĻ āĻŽāĻžāĻ¨āĻā§āĻ˛āĻŋ āĻāĻ° āĻŦāĻžāĻŽ āĻĻāĻŋāĻā§
pivot
, āĻŦāĻĄāĻŧ āĻŽāĻžāĻ¨āĻā§āĻ˛āĻŋ āĻĄāĻžāĻ¨āĻĻāĻŋāĻā§ āĻ°āĻ¯āĻŧā§āĻā§
pivot
. āĻāĻ° āĻĒāĻ°ā§, āĻāĻŽāĻ°āĻž āĻāĻāĻ āĻ¸āĻžāĻāĻžāĻ¨ā§āĻ° āĻĒāĻĻā§āĻ§āĻ¤āĻŋāĻā§ āĻ¸āĻžāĻŦāĻ
ā§āĻ¯āĻžāĻ°ā§āĻ¤ā§ āĻĒā§āĻ¨āĻ°āĻžāĻŦā§āĻ¤ā§āĻ¤āĻŋāĻŽā§āĻ˛āĻāĻāĻžāĻŦā§ āĻŦāĻ˛āĻŋ â āĻ¸ā§āĻāĻļāĻ¨ā§āĻ° āĻļā§āĻ°ā§ āĻĨā§āĻā§ āĻĄāĻžāĻ¨ āĻŽāĻžāĻ°ā§āĻāĻžāĻ°ā§ āĻ¸āĻžāĻāĻžāĻ¨ā§ āĻšāĻŦā§ āĻāĻŦāĻ āĻŦāĻžāĻŽ āĻŽāĻžāĻ°ā§āĻāĻžāĻ° āĻĨā§āĻā§ āĻ¸ā§āĻāĻļāĻ¨ā§āĻ° āĻļā§āĻˇ āĻĒāĻ°ā§āĻ¯āĻ¨ā§āĻ¤ āĻ¸āĻžāĻāĻžāĻ¨ā§ āĻšāĻŦā§āĨ¤ āĻā§āĻ¨ āĻļā§āĻ°ā§ āĻĨā§āĻā§ āĻĄāĻžāĻ¨ āĻŽāĻžāĻ°ā§āĻāĻžāĻ°? āĻāĻžāĻ°āĻŖ āĻāĻāĻāĻŋ āĻĒā§āĻ¨āĻ°āĻžāĻŦā§āĻ¤ā§āĻ¤āĻŋāĻ° āĻļā§āĻˇā§, āĻāĻāĻŋ āĻĻā§āĻāĻž āĻ¯āĻžāĻā§āĻā§ āĻ¯ā§ āĻĄāĻžāĻ¨ āĻŽāĻžāĻ°ā§āĻāĻžāĻ°āĻāĻŋ āĻŦāĻžāĻŽ āĻ
āĻāĻļā§āĻ° āĻ¸ā§āĻŽāĻžāĻ¨āĻž āĻšāĻāĻ¯āĻŧāĻžāĻ° āĻāĻ¨ā§āĻ¯ āĻ¯āĻĨā§āĻˇā§āĻ āĻ¸āĻ°ā§ āĻ¯āĻžāĻ¯āĻŧāĨ¤ āĻāĻ āĻ
ā§āĻ¯āĻžāĻ˛āĻāĻ°āĻŋāĻĻāĻŽāĻāĻŋ āĻ¸āĻšāĻ āĻŦāĻžāĻāĻžāĻāĻ¯āĻŧā§āĻ° āĻā§āĻ¯āĻŧā§ āĻāĻ°āĻ āĻāĻāĻŋāĻ˛, āĻ¤āĻžāĻ āĻāĻāĻŋ āĻ¸ā§āĻā§āĻ āĻāĻ°āĻž āĻāĻžāĻ˛āĨ¤ āĻāĻāĻāĻŋ āĻ¸āĻžāĻĻāĻž āĻāĻžāĻāĻ āĻ¨āĻŋāĻ¨ āĻāĻŦāĻ āĻ˛āĻŋāĻā§āĻ¨: 4 2 6 7 3āĨ¤ āĻ¤āĻžāĻ°āĻĒāĻ°
pivot
āĻŽāĻžāĻāĻāĻžāĻ¨ā§ āĻ˛āĻŋāĻā§āĻ¨, āĻ
āĻ°ā§āĻĨāĻžā§ 6 āĻ¨āĻŽā§āĻŦāĻ°ā§āĻ° āĻ¨āĻŋāĻā§āĨ¤ āĻāĻāĻŋāĻā§ āĻŦā§āĻ¤ā§āĻ¤ āĻāĻ°ā§āĻ¨āĨ¤ 4 āĻāĻ° āĻ¨āĻŋāĻā§ āĻ˛āĻŋāĻā§āĻ¨
L
āĻāĻŦāĻ 3 āĻāĻ° āĻ¨āĻŋāĻā§ āĻ˛āĻŋāĻā§āĻ¨
R
āĨ¤
L
6 āĻĨā§āĻā§ 4 āĻāĻŽ, 6 āĻĨā§āĻā§ 2 āĻāĻŽāĨ¤ āĻāĻŽāĻ°āĻž āĻĒāĻāĻŋāĻļāĻ¨ā§ āĻāĻ˛ā§ āĻ¯āĻžāĻ
pivot
, āĻāĻžāĻ°āĻŖ
L
āĻ
āĻ¤ā§āĻ¤ā§ āĻ¯ā§āĻ¤ā§ āĻĒāĻžāĻ°āĻŋ āĻ¨āĻž
pivot
, āĻļāĻ°ā§āĻ¤ āĻ
āĻ¨ā§āĻ¯āĻžāĻ¯āĻŧā§āĨ¤ āĻāĻŦāĻžāĻ° āĻ˛āĻŋāĻā§āĻ¨ 4 2 6 7 3. āĻŦā§āĻ¤ā§āĻ¤ 6 (
pivot
) āĻāĻŦāĻ
L
āĻāĻāĻŋāĻ° āĻ¨ā§āĻā§ āĻ°āĻžāĻā§āĻ¨āĨ¤ āĻāĻāĻ¨ āĻŽāĻžāĻ°ā§āĻāĻžāĻ° āĻ¸āĻ°āĻžāĻ¨
R
āĨ¤ 3 6 āĻāĻ° āĻĨā§āĻā§ āĻāĻŽ, āĻ¤āĻžāĻ
R
3 āĻāĻ° āĻāĻĒāĻ° āĻŽāĻžāĻ°ā§āĻāĻžāĻ° āĻ°āĻžāĻā§āĻ¨āĨ¤ āĻ¯ā§āĻšā§āĻ¤ā§ 3 6 āĻāĻ° āĻĨā§āĻā§ āĻāĻŽ (
pivot
), āĻāĻŽāĻ°āĻž āĻāĻāĻāĻŋ āĻ¸āĻŽā§āĻĒāĻžāĻĻāĻ¨ āĻāĻ°āĻŋ
swap
āĨ¤ āĻĢāĻ˛āĻžāĻĢāĻ˛ āĻ˛āĻŋāĻā§āĻ¨: 4 2 3 7 6. āĻ¸āĻžāĻ°ā§āĻā§āĻ˛ 6, āĻāĻžāĻ°āĻŖ āĻāĻāĻŋ āĻāĻāĻ¨āĻ
pivot
. āĻŽāĻžāĻ°ā§āĻāĻžāĻ°āĻāĻŋ
L
3-āĻ āĻ°āĻ¯āĻŧā§āĻā§ā§ˇ
R
āĻŽāĻžāĻ°ā§āĻāĻžāĻ°āĻāĻŋ 6-
L
āĻ
R
ā§ˇ
L
āĻĒāĻ°āĻŦāĻ°ā§āĻ¤ā§ āĻ¨āĻŽā§āĻŦāĻ°ā§ āĻ¯āĻžāĻ¨ āĨ¤ āĻāĻāĻžāĻ¨ā§ āĻāĻŽāĻŋ āĻĻā§āĻāĻŋ āĻ¸āĻŽā§āĻāĻžāĻŦāĻ¨āĻž āĻ
āĻ¨ā§āĻŦā§āĻˇāĻŖ āĻāĻ°āĻ¤ā§ āĻāĻžāĻ: 1) āĻ¯ā§āĻāĻžāĻ¨ā§ āĻāĻĒāĻžāĻ¨ā§āĻ¤āĻ° āĻ¸āĻāĻā§āĻ¯āĻž 7 āĻāĻŦāĻ 2) āĻā§āĻˇā§āĻ¤ā§āĻ°ā§ āĻ¯ā§āĻāĻžāĻ¨ā§ āĻāĻāĻŋ 1, 7 āĻ¨āĻ¯āĻŧāĨ¤
āĻ¯āĻĻāĻŋ āĻāĻĒāĻžāĻ¨ā§āĻ¤āĻ° āĻ¸āĻāĻā§āĻ¯āĻž 1 āĻšāĻ¯āĻŧ: āĻŽāĻžāĻ°ā§āĻāĻžāĻ°āĻāĻŋāĻā§ 1 āĻ āĻ¸āĻ°āĻžāĻ¨
L
, āĻāĻžāĻ°āĻŖ āĻāĻŽāĻ°āĻž āĻ¸āĻ°āĻžāĻ¤ā§ āĻĒāĻžāĻ°āĻŋ
L
āĻ¯āĻ¤āĻā§āĻˇāĻŖ āĻĒāĻ°ā§āĻ¯āĻ¨ā§āĻ¤
L
āĻŽāĻžāĻ°ā§āĻāĻžāĻ° āĻāĻ° āĻĨā§āĻā§ āĻā§āĻ āĻāĻāĻāĻŋ āĻ¸āĻāĻā§āĻ¯āĻžāĻā§ āĻ¨āĻŋāĻ°ā§āĻĻā§āĻļ āĻāĻ°ā§
pivot
āĨ¤ āĻāĻŋāĻ¨ā§āĻ¤ā§ āĻāĻŽāĻ°āĻž 6 āĻĨā§āĻā§ āĻ¸āĻ°ā§ āĻ¯ā§āĻ¤ā§ āĻĒāĻžāĻ°āĻŋ āĻ¨āĻž
R
, āĻāĻžāĻ°āĻŖ āĻāĻŽāĻ°āĻž āĻā§āĻŦāĻ˛ āĻ¤āĻāĻ¨āĻ R āĻ¸āĻ°āĻžāĻ¤ā§ āĻĒāĻžāĻ°āĻŋ āĻ¯āĻĻāĻŋ
R
āĻŽāĻžāĻ°ā§āĻāĻžāĻ° āĻāĻāĻāĻŋ āĻ¸āĻāĻā§āĻ¯āĻžāĻā§ āĻ¨āĻŋāĻ°ā§āĻĻā§āĻļ āĻāĻ°ā§ āĻ¯āĻž āĻāĻ° āĻĨā§āĻā§ āĻŦāĻĄāĻŧ
pivot
āĨ¤ āĻāĻŽāĻ°āĻž āĻāĻāĻāĻŋ āĻ¸āĻŽā§āĻĒāĻžāĻĻāĻ¨ āĻāĻ°āĻŋ āĻ¨āĻž
swap
, āĻāĻžāĻ°āĻŖ 1āĻāĻŋ 6-āĻāĻ° āĻā§āĻ¯āĻŧā§ āĻāĻŽāĨ¤ āĻŦāĻ°ā§āĻ¤āĻŽāĻžāĻ¨ āĻĒāĻ°āĻŋāĻ¸ā§āĻĨāĻŋāĻ¤āĻŋ āĻ˛āĻŋāĻā§āĻ¨: 4 2 3 1 6āĨ¤ āĻŦā§āĻ¤ā§āĻ¤ 6 (
pivot
)āĨ¤
L
āĻ¸ā§āĻĨāĻžāĻ¨āĻžāĻ¨ā§āĻ¤āĻ°āĻŋāĻ¤ āĻšāĻ¯āĻŧ
pivot
āĻāĻŦāĻ āĻ¨āĻĄāĻŧāĻžāĻāĻĄāĻŧāĻž āĻŦāĻ¨ā§āĻ§ āĻāĻ°ā§āĨ¤
R
āĻ¨āĻĄāĻŧāĻžāĻāĻĄāĻŧāĻž āĻāĻ°ā§ āĻ¨āĻž āĻāĻŽāĻ°āĻž āĻāĻāĻāĻŋ āĻ
āĻĻāĻ˛āĻŦāĻĻāĻ˛ āĻ¸āĻā§āĻāĻžāĻ˛āĻ¨ āĻ¨āĻž. āĻļāĻŋāĻĢāĻ
L
āĻāĻŦāĻ
R
āĻāĻāĻāĻŋ āĻ
āĻŦāĻ¸ā§āĻĨāĻžāĻ¨ āĻĻā§āĻŦāĻžāĻ°āĻž.
R
1 āĻāĻ° āĻ¨āĻŋāĻā§ āĻŽāĻžāĻ°ā§āĻāĻžāĻ° āĻ˛āĻŋāĻā§āĻ¨āĨ¤
L
āĻŽāĻžāĻ°ā§āĻāĻžāĻ°āĻāĻŋ āĻ¸ā§āĻŽāĻžāĻ° āĻŦāĻžāĻāĻ°ā§āĨ¤ āĻāĻžāĻ°āĻŖ
L
āĻ¸ā§āĻŽāĻžāĻ° āĻŦāĻžāĻāĻ°ā§, āĻāĻŽāĻ°āĻž āĻāĻŋāĻā§āĻ āĻāĻ°āĻŋ āĻ¨āĻžāĨ¤ āĻāĻŋāĻ¨ā§āĻ¤ā§, āĻāĻŽāĻ°āĻž āĻāĻŦāĻžāĻ° 4 2 3 1 āĻ˛āĻŋāĻāĻŋ, āĻāĻžāĻ°āĻŖ āĻāĻāĻŋ āĻāĻŽāĻžāĻĻā§āĻ° āĻŦāĻžāĻŽ āĻĻāĻŋāĻ, āĻ¯āĻž
pivot
(6) āĻāĻ° āĻā§āĻ¯āĻŧā§ āĻāĻŽāĨ¤ āĻ¨āĻ¤ā§āĻ¨ āĻ¨āĻŋāĻ°ā§āĻŦāĻžāĻāĻ¨ āĻāĻ°ā§āĻ¨
pivot
āĻāĻŦāĻ āĻ¸āĻŦāĻāĻŋāĻā§ āĻāĻŦāĻžāĻ° āĻļā§āĻ°ā§ āĻāĻ°ā§āĻ¨ :)
āĻ¯āĻĻāĻŋ āĻļā§āĻˇ āĻ¸āĻāĻā§āĻ¯āĻž 7 āĻšāĻ¯āĻŧ:āĻŽāĻžāĻ°ā§āĻāĻžāĻ°āĻāĻŋāĻā§ 7 āĻ āĻ¸āĻ°āĻžāĻ¨āĨ¤
L
āĻāĻŽāĻ°āĻž āĻ¸āĻ āĻŋāĻ āĻŽāĻžāĻ°ā§āĻāĻžāĻ°āĻāĻŋ āĻ¸āĻ°āĻžāĻ¤ā§ āĻĒāĻžāĻ°āĻāĻŋ āĻ¨āĻž, āĻāĻžāĻ°āĻŖ āĻāĻāĻŋ āĻāĻ¤āĻŋāĻŽāĻ§ā§āĻ¯ā§āĻ āĻĒāĻŋāĻāĻā§āĻ° āĻĻāĻŋāĻā§ āĻ¨āĻŋāĻ°ā§āĻĻā§āĻļ āĻāĻ°āĻā§āĨ¤ 7 āĻāĻ° āĻĨā§āĻā§ āĻŦāĻĄāĻŧ
pivot
, āĻ¤āĻžāĻ āĻāĻŽāĻ°āĻž āĻāĻāĻāĻŋ āĻ¸āĻŽā§āĻĒāĻžāĻĻāĻ¨ āĻāĻ°āĻŋ
swap
āĨ¤ āĻĢāĻ˛āĻžāĻĢāĻ˛ āĻ˛āĻŋāĻā§āĻ¨: 4 2 3 6 7. āĻŦā§āĻ¤ā§āĻ¤ 6, āĻāĻžāĻ°āĻŖ āĻāĻāĻŋ āĻšāĻ˛
pivot
. āĻŽāĻžāĻ°ā§āĻāĻžāĻ°āĻāĻŋ
L
āĻāĻāĻ¨ 7-āĻ āĻ¸ā§āĻĨāĻžāĻ¨āĻžāĻ¨ā§āĻ¤āĻ°āĻŋāĻ¤ āĻšāĻ¯āĻŧā§āĻā§, āĻāĻŦāĻ āĻŽāĻžāĻ°ā§āĻāĻžāĻ°āĻāĻŋ 3-āĻ āĻ¸ā§āĻĨāĻžāĻ¨āĻžāĻ¨ā§āĻ¤āĻ°āĻŋāĻ¤ āĻšāĻ¯āĻŧā§āĻā§āĨ¤ āĻ
āĻāĻļ āĻĨā§āĻā§ āĻļā§āĻˇ āĻĒāĻ°ā§āĻ¯āĻ¨ā§āĻ¤
R
āĻ¸āĻžāĻāĻžāĻ¨ā§āĻ° āĻā§āĻ¨ā§ āĻŽāĻžāĻ¨ā§ āĻšāĻ¯āĻŧ āĻ¨āĻž , āĻāĻžāĻ°āĻŖ āĻāĻāĻžāĻ¨ā§ āĻļā§āĻ§ā§āĻŽāĻžāĻ¤ā§āĻ° 1āĻāĻŋ āĻāĻĒāĻžāĻĻāĻžāĻ¨ āĻ°āĻ¯āĻŧā§āĻā§āĨ¤ āĻ¯āĻžāĻāĻšā§āĻ, āĻāĻŽāĻ°āĻž āĻ¸āĻžāĻāĻžāĻ¨ā§āĻ° āĻāĻ¨ā§āĻ¯
L
4 āĻĨā§āĻā§ āĻ
āĻāĻļāĻāĻŋ āĻŽāĻžāĻ°ā§āĻāĻžāĻ°ā§ āĻĒāĻžāĻ āĻžāĻ āĨ¤
R
āĻāĻŽāĻ°āĻž āĻāĻāĻāĻŋ āĻ¨āĻŋāĻ°ā§āĻŦāĻžāĻāĻ¨ āĻāĻ°āĻŋ
pivot
āĻāĻŦāĻ āĻāĻŦāĻžāĻ° āĻļā§āĻ°ā§ āĻāĻ°āĻŋ :) āĻĒā§āĻ°āĻĨāĻŽ āĻ¨āĻāĻ°ā§, āĻŽāĻ¨ā§ āĻšāĻ¤ā§ āĻĒāĻžāĻ°ā§ āĻ¯āĻĻāĻŋ āĻāĻĒāĻ¨āĻŋ āĻāĻ° āĻ¸āĻŽāĻžāĻ¨ āĻ
āĻ¨ā§āĻ āĻŽāĻžāĻ¨ āĻ¯ā§āĻ āĻāĻ°ā§āĻ¨
pivot
, āĻ¤āĻžāĻšāĻ˛ā§ āĻāĻĒāĻ¨āĻŋ āĻ
ā§āĻ¯āĻžāĻ˛āĻāĻ°āĻŋāĻĻāĻŽ āĻāĻā§āĻ āĻāĻ°āĻŦā§āĻ¨āĨ¤ āĻāĻŋāĻ¨ā§āĻ¤ā§ āĻāĻ āĻāĻāĻ¨āĻž āĻ¨āĻ¯āĻŧ. āĻāĻĒāĻ¨āĻŋ āĻāĻ¤ā§āĻ° āĻ¸āĻāĻŽāĻŋāĻļā§āĻ°āĻŖ āĻ¸āĻŽā§āĻĒāĻ°ā§āĻā§ āĻāĻŋāĻ¨ā§āĻ¤āĻž āĻāĻ°āĻ¤ā§ āĻĒāĻžāĻ°ā§āĻ¨ āĻāĻŦāĻ āĻāĻžāĻāĻā§ āĻ¨āĻŋāĻā§āĻā§ āĻŦā§āĻāĻžāĻ¤ā§ āĻĒāĻžāĻ°ā§āĻ¨ āĻ¯ā§ āĻ¸āĻŦāĻāĻŋāĻā§āĻ āĻ¸āĻ āĻŋāĻ āĻāĻŦāĻ āĻāĻļā§āĻāĻ°ā§āĻ¯āĻāĻ¨āĻ āĻ¯ā§ āĻāĻ āĻ§āĻ°āĻ¨ā§āĻ° āĻ¸āĻšāĻ āĻā§āĻ°āĻŋāĻ¯āĻŧāĻžāĻā§āĻ˛āĻŋ āĻāĻŽāĻ¨ āĻāĻāĻāĻŋ āĻ¨āĻŋāĻ°ā§āĻāĻ°āĻ¯ā§āĻā§āĻ¯ āĻŦāĻžāĻāĻžāĻ āĻĒā§āĻ°āĻā§āĻ°āĻŋāĻ¯āĻŧāĻž āĻŦāĻžāĻ¸ā§āĻ¤āĻŦāĻžāĻ¯āĻŧāĻ¨ āĻāĻ°ā§āĨ¤ āĻāĻāĻŽāĻžāĻ¤ā§āĻ° āĻ¨ā§āĻ¤āĻŋāĻŦāĻžāĻāĻ āĻĻāĻŋāĻ āĻšāĻ˛ āĻāĻ āĻ¸āĻžāĻāĻžāĻ¨ā§āĻ° āĻ
ā§āĻ¯āĻžāĻ˛āĻāĻ°āĻŋāĻĻāĻŽ āĻ¸ā§āĻĨāĻŋāĻ¤āĻŋāĻļā§āĻ˛ āĻ¨āĻ¯āĻŧāĨ¤ āĻāĻžāĻ°āĻŖ āĻāĻāĻāĻŋ āĻ
āĻĻāĻ˛āĻŦāĻĻāĻ˛ āĻ
āĻāĻŋāĻ¨ā§āĻ¨ āĻāĻĒāĻžāĻĻāĻžāĻ¨āĻā§āĻ˛āĻŋāĻ° āĻāĻĒā§āĻā§āĻˇāĻŋāĻ āĻā§āĻ°āĻŽ āĻĒāĻ°āĻŋāĻŦāĻ°ā§āĻ¤āĻ¨ āĻāĻ°āĻ¤ā§ āĻĒāĻžāĻ°ā§ āĻ¯āĻĻāĻŋ āĻ¤āĻžāĻĻā§āĻ° āĻāĻāĻāĻŋāĻ° āĻāĻā§
pivot
āĻ
āĻ¨ā§āĻ¯ āĻāĻĒāĻžāĻĻāĻžāĻ¨āĻāĻŋ āĻāĻā§ āĻ
āĻāĻļā§ āĻ
āĻĻāĻ˛āĻŦāĻĻāĻ˛ āĻāĻ°āĻžāĻ° āĻāĻā§ āĻ¸āĻŽā§āĻŽā§āĻā§āĻ¨ āĻšāĻ¯āĻŧ
pivot
āĨ¤