ຈັດແຈງ Array ເຊັ່ນວ່າ arr [i]> = arr [j] ຖ້າຂ້ອຍແມ່ນແລະຮອດ [i] <= arr [j] ຖ້າຂ້ອຍຄີກແລະ j <i


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ Accenture Adobe Amazon ປັດໃຈ Zoho
Array

ສົມມຸດວ່າທ່ານມີເລກເຕັມ array. ຄຳ ຖະແຫຼງກ່ຽວກັບບັນຫາຮຽກຮ້ອງໃຫ້ຈັດແຈງການຈັດລຽງ ໃໝ່ ໃນລັກສະນະດັ່ງກ່າວເຊິ່ງອົງປະກອບຕ່າງໆທີ່ຢູ່ໃນ ຕຳ ແໜ່ງ ໃນອາເລ ໜຶ່ງ ຄວນຈະໃຫຍ່ກ່ວາທຸກໆອົງປະກອບກ່ອນມັນແລະອົງປະກອບທີ່ຢູ່ ຕຳ ແໜ່ງ ຄີກຄວນຈະ ໜ້ອຍ ກວ່າອົງປະກອບກ່ອນມັນ.

ຍົກຕົວຢ່າງ

ການປ້ອນຂໍ້ມູນ

arr [] = {1, 4, 6, 2, 4, 8, 9}

ຜົນຜະລິດ

4 6 4 8 2 9 1

ຄໍາອະທິບາຍ

ທຸກໆອົງປະກອບໃນ ຕຳ ແໜ່ງ ທີ່ສູງກວ່າອົງປະກອບທັງ ໝົດ ກ່ອນມັນແລະອົງປະກອບທີ່ຢູ່ ຕຳ ແໜ່ງ ຄີກົ້ແມ່ນມີ ໜ້ອຍ ກ່ວາອົງປະກອບກ່ອນ ໜ້າ ນີ້.

ລະບົບວິເຄາະ

  1. ຕັ້ງຄ່າ evenPosition ໃຫ້ n / 2.
  2. ຕັ້ງ oddPosition ໃຫ້ n - evenPosition.
  3. ສ້າງຂບວນ (ຊົ່ວຄາວ).
  4. ເກັບມ້ຽນສ່ວນປະກອບທັງ ໝົດ ຂອງອາເລທີ່ໃຫ້ໄວ້ໃນແຖວຊົ່ວຄາວນີ້.
  5. ຮຽງແຖວຊົ່ວຄາວ.
  6. ຕັ້ງ j ເທົ່າກັບ oddPosition -1.
  7. ຄັດລອກຊົ່ວຄາວໄປຫາຂບວນຕົ້ນສະບັບ [j] ຢູ່ທີ່ ຕຳ ແໜ່ງ (ດັດສະນີອີງຕາມ) ຂອງອາເລທີ່ໃຫ້ແລະຫຼຸດຄ່າຂອງ j ລົງ 1.
  8. ຕັ້ງ j ໃຫ້ oddPosition.
  9. ສຳ ເນົາຊົ່ວຄາວໄປທີ່ແຖວຕົ້ນໆ [j] ທີ່ ຕຳ ແໜ່ງ ຄີກ (ອີງຕາມການດັດສະນີ) ຂອງຂບວນທີ່ໃຫ້ແລະເພີ່ມຄ່າ j ໂດຍ 1.
  10. ພິມຂບວນຕົ້ນສະບັບຕັ້ງແຕ່ການປັບປຸງຖືກສ້າງຂື້ນໃນແຖວເດີມ.

ຄໍາອະທິບາຍ

ໃນການປະສົມປະສານເຂົ້າກັນ, ວຽກງານຂອງພວກເຮົາແມ່ນການຈັດແຈງອາຄານໃນແບບທີ່ອົງປະກອບໃນ ຈຳ ນວນ ຕຳ ແໜ່ງ ເຖິງແມ່ນວ່າຄວນຈະສູງກວ່າທຸກໆສ່ວນຂອງສ່ວນປະກອບກ່ອນມັນ. ແລະສ່ວນປະກອບທີ່ຢູ່ໃນ ຈຳ ນວນ ຕຳ ແໜ່ງ ທີ່ບໍ່ ເໝາະ ສົມຄວນຈະ ໜ້ອຍ ກວ່າ ຈຳ ນວນ ຕຳ ແໜ່ງ ທີ່ມີຢູ່ກ່ອນມັນ. ພວກເຮົາສາມາດເຫັນໄດ້ໃນຕົວຢ່າງເຊັ່ນວ່າອົງປະກອບຕ່າງໆທີ່ຢູ່ໃນ ຕຳ ແໜ່ງ ເຖິງແມ່ນໃຫຍ່ກວ່າຕົວເລກທັງ ໝົດ ກ່ອນມັນ. ໃນທີ່ນີ້ພວກເຮົາບໍ່ໄດ້ເອົາມັນເປັນ ໝາຍ ເລກອີງໃສ່ດັດສະນີ. ສ່ວນປະກອບທີ່ 0 ຕຳ ແໜ່ງ ຄວນໄດ້ຮັບການຮັກສາເປັນ 1 ຕຳ ແໜ່ງ ທີ່ຄີກ. .st ຕຳ ແໜ່ງ ຂອງອາເລແມ່ນ 2 ຕຳ ແໜ່ງ ທີ່ແມ່ນແຕ່, ໃນທີ່ນີ້ພວກເຮົາບໍ່ໄດ້ພິຈາລະນາດັດສະນີທີ່ອີງໃສ່ອາເລໃນຜົນຂອງພວກເຮົາ, ພວກເຮົາເລີ່ມຈາກ 1 ເປັນເລກຄີກເຖິງເລກ ໝາຍ ເລກ n.

ເຮັດ ສຳ ເນົາຂວດຕົ້ນສະບັບເຂົ້າໃນແຖວຊົ່ວຄາວ, ນັບວ່າມີ ຕຳ ແໜ່ງ ທີ່ແປກແລະ ຕຳ ແໜ່ງ ຫຼາຍປານໃດທີ່ສາມາດຢູ່ໃນແຖວ. ຈາກນັ້ນ, ພວກເຮົາ ກຳ ລັງຈະຈັດຮຽງແຖວໃຫ້ເປັນລະບຽບຕາມ ລຳ ດັບ. ຕອນນີ້ປັບປຸງອົງປະກອບຂອງອາເລຢູ່ ຕຳ ແໜ່ງ ທີ່ຄີກ (ດັດສະນີທີ່ບໍ່ແມ່ນອາເລ), ຈາກຂບວນຊົ່ວຄາວເປັນຄ່າທີ່ຫຼຸດລົງຂອງ oddPosition - 1 ເຖິງ 0.

ສ່ວນປະກອບທັງ ໝົດ ຈາກເຄິ່ງ ໜຶ່ງ ຂອງຂບວນຊົ່ວຄາວຈະຖືກເກັບຢູ່ບ່ອນ ຕຳ ແໜ່ງ ຂອງແຖວເດີມ. ເຊັ່ນດຽວກັນ, ພວກເຮົາຈະເກັບຮັກສາສ່ວນທີ່ເຫຼືອຂອງຄ່າຂອງເຄິ່ງທີສອງຂອງຂບວນຊົ່ວຄາວຈະຖືກເກັບຢູ່ໃນ ຕຳ ແໜ່ງ ຂອງຂບວນເດີມ, ໃນລັກສະນະນີ້, ພວກເຮົາສາມາດຈັດແຈງອາຄານຄືນ ໃໝ່ ເພື່ອໃຫ້ອົງປະກອບຕ່າງໆຢູ່ໃນ ຕຳ ແໜ່ງ ທີ່ໃຫຍ່ກວ່າແລະອົງປະກອບຕ່າງໆຢູ່ຄີກ ຕຳ ແໜ່ງ ທີ່ອົງປະກອບຄີກຈະມີຂະ ໜາດ ນ້ອຍກ່ວາທຸກໆສ່ວນຂອງສ່ວນປະກອບກ່ອນທີ່ມັນຈະຕາມ ລຳ ດັບ.

ຈັດແຈງ Array ເຊັ່ນວ່າ arr [i]> = arr [j] ຖ້າຂ້ອຍແມ່ນແລະຮອດ [i] <= arr [j] ຖ້າຂ້ອຍຄີກແລະ j <i

ການປະຕິບັດ

ໂປຣແກຣມ C ++

#include<iostream>
#include<algorithm>

using namespace std;

void rearrangeArrayEvenOdd(int arr[], int n)
{
    int evenPosition = n / 2;

    int oddPosition = n - evenPosition;

    int temporaryArray[n];

    for (int i = 0; i < n; i++)
        temporaryArray[i] = arr[i];

    sort(temporaryArray, temporaryArray + n);

    int j = oddPosition - 1;

    for (int i = 0; i < n; i += 2)
    {
        arr[i] = temporaryArray[j];
        j--;
    }

    j = oddPosition;

    for (int i = 1; i < n; i += 2)
    {
        arr[i] = temporaryArray[j];
        j++;
    }
}
void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}
int main()
{
    int arr[] = { 1,4,6,2,4,8,9};
    int n = sizeof(arr) / sizeof(arr[0]);
    rearrangeArrayEvenOdd(arr, n);
    printArray(arr,n);
    return 0;
}
4 6 4 8 2 9 1

ໂຄງການ Java

import java.util.*;

class rearrangeArray
{
    public static void rearrangeArrayEvenOdd (int arr[], int n)
    {
        int evenPosition = n / 2;

        int oddPosition = n - evenPosition;

        int[] temporaryArray = new int [n];

        for (int i = 0; i < n; i++)
            temporaryArray[i] = arr[i];

        Arrays.sort(temporaryArray);
        int j = oddPosition - 1;

        for (int i = 0; i < n; i += 2)
        {
            arr[i] = temporaryArray[j];
            j--;
        }

        j = oddPosition;

        for (int i = 1; i < n; i += 2)
        {
            arr[i] = temporaryArray[j];
            j++;
        }
    }
    public static void printArray(int arr[], int n)
    {

        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
    }
    public static void main(String argc[])
    {
        int[] arr = { 1,4,6,2,4,8,9};
        int size =arr.length;
        rearrangeArrayEvenOdd (arr, size);
        printArray(arr, size);

    }
}
4 6 4 8 2 9 1

ການວິເຄາະຄວາມສັບສົນ

ຄວາມສັບສົນເວລາ

O (n log n) ບ່ອນທີ່ "n" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ.

ຄວາມສັບສົນໃນອະວະກາດ

O (n)  ບ່ອນທີ່ "n"  ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ.