ເຕັກນິກໃນການຂຽນໂປຣແກຣມການຮຽງລໍາດັບ: ຮຽງລໍາດັບ "ຟອງ"

ຄັດຟອງບໍ່ໄດ້ພິຈາລະນາພຽງແຕ່ເປັນວິທີການໄວທີ່ສຸດ, ຍິ່ງໄປກວ່ານັ້ນ, ມັນປິດບັນຊີລາຍຊື່ຂອງວິທີການຊ້າທີ່ສຸດທີ່ໃນການຈັດຕັ້ງ. ຢ່າງໃດກໍຕາມ, ມັນມີຄວາມໄດ້ປຽບຂອງຕົນ. ດັ່ງນັ້ນ, ວິທີການຂອງການຄັດເລືອກຟອງ - ທີ່ສຸດທີ່ neither ແມ່ນເປັນການແກ້ໄຂທໍາມະຊາດແລະມີເຫດຜົນທີ່ຈະມີບັນຫາ, ຖ້າຫາກວ່າທ່ານຕ້ອງການທີ່ຈະຈັດແຈງຊະນິດຢູ່ໃນຄໍາສັ່ງສະເພາະໃດຫນຶ່ງໄດ້. ເປັນບຸກຄົນທີ່ທໍາມະດາດ້ວຍຕົນເອງ, ສໍາລັບການຍົກຕົວຢ່າງ, ມັນຈະນໍາໃຊ້ໃຫ້ເຂົາເຈົ້າ - ພຽງແຕ່ໂດຍ intuition.

ບ່ອນໃດທີ່ບໍ່ດັ່ງກ່າວຊື່ຜິດປົກກະຕິ?

ຊື່ວິທີການຂຶ້ນມາ, ການນໍາໃຊ້ການປຽບທຽບຂອງຟອງອາກາດໃນນ້ໍາໄດ້. ມັນເປັນການປຽບທຽບໄດ້. ພຽງແຕ່ເປັນຟອງອາກາດນ້ອຍລຸກຂຶ້ນ - ເນື່ອງຈາກວ່າຄວາມຫນາແຫນ້ນຂອງຂອງເຂົາເຈົ້າແມ່ນຫຼາຍກ່ວານ້ໍາ (ໃນກໍລະນີນີ້ - ນ້ໍາ), ແລະໃນແຕ່ລະອົງປະກອບ array, ຂະຫນາດນ້ອຍກວ່າມັນເປັນມູນຄ່າການ, ວິທີຄ່ອຍເປັນຄ່ອຍໄປຫຼາຍດ້ານເທິງຂອງຈໍານວນບັນຊີລາຍຊື່ດັ່ງກ່າວ.

ລາຍລະອຽດຂອງຂັ້ນຕອນວິທີ

ຄັດຟອງແມ່ນປະຕິບັດດັ່ງຕໍ່ໄປນີ້:

• ຜ່ານທໍາອິດ: ອົງປະກອບຂອງຈໍານວນອາເລໄດ້ຖືກປະຕິບັດໂດຍທັງສອງຄູ່ແລະຍັງປຽບທຽບ. ຖ້າຫາກວ່າອົງປະກອບບາງສ່ວນຂອງທັງສອງຜູ້ຊາຍທີມງານມູນຄ່າທໍາອິດແມ່ນຫຼາຍກ່ວາວິນາທີ, ໂຄງການໄດ້ເຮັດໃຫ້ພວກເຂົາສະຖານທີ່ແລກປ່ຽນ;
• ຜົນສະທ້ອນ, ໃນຈໍານວນຫຼາຍທີ່ສຸດຂອງ ພະລາດທ່າໃນຕອນທ້າຍຂອງອາເລ. ໃນຂະນະທີ່ທັງຫມົດອົງປະກອບອື່ນໆຍັງຄົງຍ້ອນວ່າເຂົາເຈົ້າໄດ້, ໃນລັກສະນະ chaotic, ແລະຮຽກຮ້ອງໃຫ້ມີຫຼາຍການຮຽງລໍາດັບ;
• ແລະເພາະສະນັ້ນຈຶ່ງຮຽກຮ້ອງໃຫ້ມີການຜ່ານທີ່ສອງ: ມັນແມ່ນເຮັດໄດ້ໂດຍການປຽບທຽບກັບທີ່ຜ່ານມາ (ອະທິບາຍແລ້ວ) ແລະມີຈໍານວນຂອງການປຽບທຽບ - ລົບຫນຶ່ງ;
• ທີ່ບ້ານເລກທີ່ passage ສາມປຽບທຽບ, ຫນຶ່ງໃນສອງຫນ້ອຍກວ່າສອງ, ແລະທັງສອງ, ກ່ວາຄັ້ງທໍາອິດ. ແລະອື່ນໆ;
• ສະຫຼຸບວ່າໃນແຕ່ລະ passage ມີ (ຄ່າທັງຫມົດໃນອາເລ, ຈໍານວນສະເພາະໃດຫນຶ່ງ) ລົບປຽບທຽບ (ຈໍານວນ passage).

ຂັ້ນຕອນວິທີສັ້ນຂອງໂຄງການສາມາດໄດ້ຮັບການລາຍລັກອັກສອນວ່າ:

• ເປັນ array ຂອງຈໍານວນໄດ້ຖືກກວດກາຄືນຊຶ່ງເປັນສອງຈໍານວນໄດ້ຖືກພົບເຫັນ, ສອງຂອງເຂົາເຈົ້າໄດ້ຖືກຜູກເພື່ອຈະຫຼາຍກ່ວາຄັ້ງທໍາອິດ;
• ຕໍາແຫນ່ງຢ່າງບໍ່ຖືກຕ້ອງໃນທີ່ກ່ຽວຂ້ອງກັບແຕ່ລະອົງປະກອບອື່ນໆຂອງແລກປ່ຽນປະສົບຊອຟແວອາເລ.

pseudocode ອີງໃສ່ຂັ້ນຕອນວິທີການອະທິບາຍ

ການປະຕິບັດທີ່ງ່າຍທີ່ຈະດໍາເນີນການດັ່ງຕໍ່ໄປນີ້:

ຂັ້ນຕອນ Sortirovka_Puzirkom;

ເລີ່ມຕົ້ນ

ວົງຈອນສໍາລັບ j ຈາກ nachalnii_index ກັບ konechii_index;

ວົງຈອນສໍາລັບຂ້າພະເຈົ້າຈາກ nachalnii_index ກັບ konechii_index -1;

ຖ້າຫາກວ່າຄວາມຫນາແຫນ້ນ [i]> ຄວາມຫນາແຫນ້ນ [i + 1] (ອົງປະກອບທໍາອິດຫຼາຍກ່ວາວິນາທີ), ຫຼັງຈາກນັ້ນ:

(ການປ່ຽນແປງສະຖານທີ່ຄ່າ);

ໃນຕອນທ້າຍ

ແນ່ນອນວ່າ, ລະນານີ້ເທົ່ານັ້ນ aggravates ສະຖານະການນີ້: ຂັ້ນຕອນວິທີການງ່າຍ, ຫຼາຍມັນ manifests ເມີດວິໄນທັງຫມົດ. ອັດຕາສ່ວນການລົງທຶນຂອງທີ່ໃຊ້ເວລາທີ່ຍິ່ງໃຫຍ່ກວ່າເຖິງແມ່ນວ່າສໍາລັບການຂະຫນາດນ້ອຍ array (ທີ່ນີ້ມາໃນສໍາພັດທະພາບ: ຈໍານວນຂອງທີ່ໃຊ້ເວລາສໍາລັບຄົນທໍາມະດາອາດເບິ່ງຄືວ່າຂະຫນາດນ້ອຍ, ແຕ່ໃນຄວາມເປັນຈິງເປັນ programmer ທຸກໆການນັບສອງຫຼືແມ້ກະທັ້ງ millisecond).

ມັນໄດ້ເອົາການປະຕິບັດດີກວ່າ. ສໍາລັບຕົວຢ່າງ, ການຄໍານຶງເຖິງການແລກປ່ຽນຂອງຄ່າໃນສະຖານທີ່ອາເລ:

ຂັ້ນຕອນ Sortirovka_Puzirkom;

ເລີ່ມຕົ້ນ

sortirovka = true

ວົງຈອນຈົນກ່ວາ sortirovka = ຄວາມຈິງ;

sortirovka = false

ວົງຈອນສໍາລັບຂ້າພະເຈົ້າຈາກ nachalnii_index ກັບ konechii_index -1;

ຖ້າຫາກວ່າຄວາມຫນາແຫນ້ນ [i]> ຄວາມຫນາແຫນ້ນ [i + 1] (ອົງປະກອບທໍາອິດຫຼາຍກ່ວາວິນາທີ), ຫຼັງຈາກນັ້ນ:

(ມີການປ່ຽນແປງອົງປະກອບສະຖານທີ່);

sortirovka = true (ລະບຸວ່າອັດຕາແລກປ່ຽນໄດ້ຮັບການເຮັດ).

ສຸດທ້າຍ.

ຂໍ້ຈໍາກັດ

ການເສຍປຽບຕົ້ນຕໍ - ໄລຍະເວລາຂອງຂະບວນການດັ່ງກ່າວ. ວິທີທີ່ໃຊ້ເວລາຫຼາຍປານໃດແມ່ນປະຕິບັດ ການຮຽງລໍາດັບຂັ້ນຕອນວິທີ ຟອງ?

ໄລຍະເວລາຄໍານວນຈາກຈໍານວນຂອງຕາລາງຈໍານວນທີ່ຢູ່ໃນອາເລ - ຜົນໄດ້ຮັບໃນຕອນທ້າຍຂອງມັນເປັນສັດສ່ວນ.

ຖ້າຫາກວ່າກໍລະນີຮ້າຍແຮງທີ່ສຸດຂອງ array ແມ່ນຜ່ານການເປັນເວລາຫຼາຍຍ້ອນວ່າມັນມີອົງປະກອບລົບມູນຄ່າຫນຶ່ງ. ນີ້ເກີດຂຶ້ນເພາະວ່າໃນທີ່ສຸດມີພຽງແຕ່ອົງປະກອບຫນຶ່ງ, ຊຶ່ງມີບໍ່ມີຫຍັງທີ່ຈະສົມທຽບ, ແລະຜ່ານທີ່ຜ່ານມາໂດຍຜ່ານອາເລຈະກາຍເປັນການປະຕິບັດ useless.

ໃນນອກຈາກນັ້ນ, ວິທີການປະສິດທິພາບຂອງການຮຽງລໍາດັບເປັນການແລກປ່ຽນທີ່ງ່າຍດາຍ, ເປັນມັນຖືກເອີ້ນວ່າ, ພຽງແຕ່ສໍາລັບການອາເລຂອງຂະຫນາດຂະຫນາດນ້ອຍ. ປະລິມານຂະຫນາດໃຫຍ່ຂອງຂໍ້ມູນທີ່ມີການຊ່ວຍເຫຼືອຂອງຂະບວນການຈະບໍ່ໄດ້ເຮັດວຽກ: ຜົນໄດ້ຮັບຈະບໍ່ວ່າຈະເປັນຄວາມຜິດພາດຫຼືຄວາມລົ້ມເຫຼວຂອງໂຄງການ.

ກຽດສັກສີ

ຄັດຟອງແມ່ນງ່າຍທີ່ຈະເຂົ້າໃຈ. ຫຼັກສູດຂອງມະດ້ານວິຊາການໃນການສຶກສາຂອງອົງປະກອບການກໍາລັງສັ່ງຂອງ array ຂອງຕົນບັງເກີດຂຶ້ນໃນສະຖານທີ່ທໍາອິດ. ວິທີການແມ່ນງ່າຍທີ່ຈະປະຕິບັດທັງສອງດໍາເນີນໂຄງການພາສາ Delphi (L (Delphi), ແລະ C / C ++ (C / C ບວກບວກ), ເປັນຄ່າງ່າຍດາຍ incredibly ຂອງສູດສະຖານທີ່ຢູ່ໃນຄໍາສັ່ງສິດທິໃນການແລະໃນ Pascal (Pascal). ຟອງຄັດແມ່ນເຫມາະສົມສໍາລັບຜູ້ເລີ່ມ.

ເນື່ອງຈາກຈຸດອ່ອນຂອງຂັ້ນຕອນວິທີການທີ່ບໍ່ໄດ້ຖືກນໍາໃຊ້ໃນຈຸດປະສົງນອກຫລັກສູດ.

ຫຼັກການຮຽງລໍາດັບພາບແລະ

ເບິ່ງໃນເບື້ອງຕົ້ນຂອງ array 8 22 4 74 44 37 1 7

ຂັ້ນຕອນທີ 1 8 22 4 74 44 37 1 7

8 22 4 74 44 1 37 7

8 22 4 74 1 44 37 7

8 22 4 1 74 44 37 7

8 22 1 4 74 44 37 7

8 1 22 4 74 44 37 7

1 8 22 4 74 44 37 7

ຂັ້ນຕອນທີ 2 1 8 22 4 74 44 7 37

1 8 22 4 74 7 44 37

1 8 22 4 7 74 44 37

1 8 22 4 7 74 44 37

1 8 4 22 7 74 44 37

1 4 8 22 7 74 44 37

ຂັ້ນຕອນທີ 3 1 4 8 22 7 74 37 44

1 4 8 22 7 37 74 44

1 4 8 22 7 37 74 44

1 4 8 7 22 37 74 44

1 4 7 8 22 37 74 44

ຂັ້ນຕອນທີ 4 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

ຂັ້ນຕອນທີ 5 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

ຂັ້ນຕອນທີ 6 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

ຂັ້ນຕອນທີ 7 1 4 7 8 22 37 44 74

ຕົວຢ່າງການຈັດລຽງຟອງໃນ Pascal

ຕົວຢ່າງເຊັ່ນ:

kol_mas const = 10;

var Massive: array [1..kol_mas] ຂອງ ຈໍານວນເຕັມ;

a, b, k: integer;

ເລີ່ມຕົ້ນ

writeln ( 'ການປ້ອນຂໍ້ມູນ ", kol_mas, ' ອົງປະກອບຂອງ array ');

ສໍາລັບການ: = 1 ກັບ kol_mas ເຮັດຮູບທີ່ (ຂະຫນາດໃຫຍ່ [a ]);

ສໍາລັບການ: = 1 ກັບ kol_mas-1 ເຮັດເລີ່ມຕົ້ນ

ສໍາລັບ b: = a + 1 ກັບ kol_mas ເຮັດເລີ່ມຕົ້ນ

ຖ້າຫາກວ່າຄວາມຫນາແຫນ້ນ [a]> ຄວາມຫນາແຫນ້ນ [ b] ຫຼັງຈາກນັ້ນເລີ່ມຕົ້ນ

k: = ຄວາມຫນາແຫນ້ນ [a]; ຄວາມຫນາແຫນ້ນ [a]: = ຄວາມຫນາແຫນ້ນ [ b]; ຄວາມຫນາແຫນ້ນ [b]: = k;

ສິ້ນສຸດ;

ສິ້ນສຸດ;

ສິ້ນສຸດ;

writeln ( 'ຫຼັງຈາກຄັດ');

ສໍາລັບການ: = 1 ກັບ kol_mas ເຮັດ writeln (ຄວາມຫນາແຫນ້ນ [a ]);

ໃນຕອນທ້າຍ.

ຟອງຕົວຢ່າງການຮຽງລໍາດັບໃນພາສາ C (C)

ຕົວຢ່າງເຊັ່ນ:

#include

#include

int main (int argc, char * argv [])

{

int massive [8] = {36, 697, 73, 82, 68, 12, 183, 88}, ຂ້າພະເຈົ້າ, ff;

ສໍາລັບ (;;) {

ff = 0;

for (i = 7; i> 0; ຂ້າພະເຈົ້າ -) {

ຖ້າຫາກວ່າ (ຄວາມຫນາແຫນ້ນ [i] [i- 1]) {

ແລກປ່ຽນປະສົບ (ຄວາມຫນາແຫນ້ນ [i], ຄວາມຫນາແຫນ້ນ [i- 1]);

ff ++;

}

}

ຖ້າຫາກວ່າ (ff == 0) ແບ່ງ

}

getch (); // ຊັກຊ້າສະແດງ

ກັບຄືນ 0;

}.