ບົດທີ 7 Sorting Algorithms

1. ຄວາມຮູ້ພື້ນຖານກ່ຽວກັບ Sorting Algorithms

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

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

ຂັ້ນຕອນການຈັດຮຽງທີ່ອີງໃສ່ການປຽບທຽບປຽບທຽບລາຍການທີ່ຖືກຈັດຮຽງໂດຍໃຊ້ຕົວປະຕິບັດການປຽບທຽບເຊັ່ນ: ໃຫຍ່ກວ່າ ຫຼືໜ້ອຍກວ່າ. ໂດຍປົກກະຕິແລ້ວ algorithms ເຫຼົ່ານີ້ມີຄວາມຊັບຊ້ອນເວລາທີ່ຮ້າຍແຮງທີ່ສຸດຂອງ O(n log n), ບ່ອນທີ່ n ແມ່ນຈໍານວນລາຍການທີ່ຖືກຈັດຮຽງ. ຕົວ​ຢ່າງ​ຂອງ​ການ​ຈັດ​ລຽງ​ຕາມ​ການ​ປຽບ​ທຽບ​ປະ​ກອບ​ມີ​ການ​ຈັດ​ລຽງ​ຟອງ​, ການ​ຈັດ​ລຽງ​ການ​ແຊກ​, ການ​ຄັດ​ເລືອກ​, ການ​ຈັດ​ລຽງ​ລວມ​, ການ​ຈັດ​ລຽງ​ໄວ​, ແລະ​ການ​ຈັດ​ລຽງ heap​.

ຂັ້ນຕອນການຈັດຮຽງທີ່ບໍ່ອີງໃສ່ການປຽບທຽບບໍ່ໄດ້ໃຊ້ການປຽບທຽບເພື່ອຈັດຮຽງລາຍການ. ແທນທີ່ຈະ, ປົກກະຕິແລ້ວພວກເຂົາອີງໃສ່ຊັບສິນອື່ນໆຂອງລາຍການ, ເຊັ່ນ: ມູນຄ່າ hash ຫຼືຕົວເລກຂອງພວກເຂົາ. ຂັ້ນຕອນການຈັດຮຽງທີ່ບໍ່ອີງໃສ່ການປຽບທຽບສາມາດມີຄວາມຊັບຊ້ອນເວລາທີ່ຮ້າຍແຮງທີ່ສຸດແມ່ນດີກ່ວາ O(n log n), ແຕ່ພວກມັນອາດຈະຕ້ອງການຄວາມຊົງຈໍາເພີ່ມເຕີມເພື່ອເກັບຂໍ້ມູນເສີມ. ຕົວ​ຢ່າງ​ຂອງ​ສູດ​ການ​ຈັດ​ລຽງ​ໂດຍ​ບໍ່​ແມ່ນ​ການ​ປຽບ​ທຽບ​ລວມ​ທັງ​ການ​ຈັດ​ລຽງ​ການ​ນັບ​ແລະ​ການ​ຈັດ​ລຽງ radix​.

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

2. ປະເພດຂອງ Sorting Algorithams

ມີຫຼາຍປະເພດຂອງສູດການຄິດໄລ່, ແຕ່ລະມີຄຸນສົມບັດເປັນເອກະລັກຂອງຕົນເອງແລະລັກສະນະປະສິດທິພາບ. ນີ້ແມ່ນບາງປະເພດທົ່ວໄປທີ່ສຸດຂອງ algorithms ການຈັດລຽງ:

1. ຂັ້ນຕອນການຈັດຮຽງຕາມການປຽບທຽບ:

   1. • Bubble Sort: ສູດການຮຽງລຳດັບແບບງ່າຍໆທີ່ເຮັດຊ້ຳໆຜ່ານລາຍການ, ປຽບທຽບອົງປະກອບທີ່ຢູ່ຕິດກັນ ແລະແລກປ່ຽນກັນຖ້າພວກມັນຢູ່ໃນລຳດັບທີ່ຜິດ.

• Insertion Sort: ສູດການຮຽງລຳດັບແບບງ່າຍໆທີ່ສ້າງ array ທີ່ຈັດຮຽງສຸດທ້າຍເທື່ອລະອັນໂດຍການປຽບທຽບແຕ່ລະລາຍການກັບ predecessor ຂອງມັນ ແລະໃສ່ມັນໃສ່ໃນຕຳແໜ່ງທີ່ຖືກຕ້ອງ.

• ການຈັດຮຽງການເລືອກ: ຂັ້ນຕອນການຈັດຮຽງແບບງ່າຍດາຍທີ່ເລືອກອົງປະກອບທີ່ນ້ອຍທີ່ສຸດຈາກພາກສ່ວນທີ່ບໍ່ໄດ້ຈັດຮຽງຂອງອາເຣ ແລະແລກປ່ຽນມັນກັບອົງປະກອບທໍາອິດ.

• Merge Sort: ສູດການຮຽງລຳດັບທີ່ແບ່ງລາຍຊື່ທີ່ບໍ່ໄດ້ຈັດຮຽງອອກເປັນ n sublists, ແຕ່ລະອັນມີອົງປະກອບໜຶ່ງ, ແລະຫຼັງຈາກນັ້ນຈະຮວມລາຍຊື່ຍ່ອຍຊ້ຳໆເພື່ອສ້າງລາຍຊື່ຍ່ອຍທີ່ຈັດຮຽງໃໝ່ ຈົນກວ່າຈະເຫຼືອພຽງໜຶ່ງລາຍການຍ່ອຍ.

• ການຈັດຮຽງດ່ວນ: ສູດການຮຽງລຳດັບທີ່ແບ່ງອາເຣເປັນສອງແຖວຍ່ອຍ, ອັນໜຶ່ງມີອົງປະກອບນ້ອຍກວ່າອົງປະກອບ pivot, ແລະອີກອັນໜຶ່ງມີອົງປະກອບໃຫຍ່ກວ່າອົງປະກອບ pivot. ຫຼັງຈາກນັ້ນ, ມັນຈັດຮຽງແຖວຍ່ອຍແບບ recursively.

• Heap Sort: ສູດການຮຽງລຳດັບທີ່ສ້າງ heap binary ຈາກ array ແລະ ຊ້ຳໆແລ້ວແຍກອົງປະກອບສູງສຸດອອກຈາກ heap ແລະວາງມັນໄວ້ທີ່ທ້າຍຂອງ array.

2. ສູດການຮຽງລຳດັບທີ່ບໍ່ແມ່ນການປຽບທຽບ:

• • Counting Sort: ສູດການຮຽງລຳດັບທີ່ນຳໃຊ້ array auxiliary ເພື່ອນັບຈຳນວນການປະກົດຕົວຂອງແຕ່ລະອົງປະກອບ, ແລະຫຼັງຈາກນັ້ນນຳໃຊ້ຂໍ້ມູນນີ້ເພື່ອຈັດວາງແຕ່ລະອົງປະກອບໃນຕຳແໜ່ງທີ່ຖືກຕ້ອງ.

  • Radix Sort: ສູດການຮຽງລຳດັບທີ່ຈັດຮຽງອົງປະກອບຕາມຕົວເລກ ຫຼືຕົວອັກສອນ, ເລີ່ມຕົ້ນດ້ວຍຕົວເລກ ຫຼືຕົວອັກສອນທີ່ມີຄວາມໝາຍໜ້ອຍທີ່ສຸດ ແລະຍ້າຍໄປຕົວເລກ ຫຼືຕົວລະຄອນທີ່ສຳຄັນທີ່ສຸດ.

3. ຂັ້ນຕອນການຈັດຮຽງແບບປະສົມ:

• • Timsort: ສູດການຮຽງລຳດັບທີ່ລວມການຈັດຮຽງ ແລະການຈັດຮຽງ. ມັນປະຕິບັດໄດ້ດີໃນຫຼາຍປະເພດຂອງຂໍ້ມູນໃນໂລກທີ່ແທ້ຈິງ.

  • IntroSort: ສູດການຮຽງລຳດັບທີ່ໃຊ້ທັງການຈັດຮຽງໄວ ແລະການຈັດລຽງລຳດັບ. ມັນເລີ່ມຕົ້ນດ້ວຍການຈັດຮຽງແບບໄວ, ແຕ່ປ່ຽນເປັນ heapsort ຖ້າຄວາມເລິກຂອງ recursion ເກີນຂອບເຂດທີ່ແນ່ນອນ.

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