Хөөсөөр эрэмбэлэх ба Сонголтоор эрэмбэлэх
Хөөсөөр эрэмбэлэх нь зэргэлдээ орших элементүүдийн хосыг харьцуулах явцад дахин дахин эрэмбэлэх жагсаалтын дагуу ажилладаг эрэмбэлэх алгоритм юм. Хэрэв хос элементүүд буруу дарааллаар байвал тэдгээрийг зөв дарааллаар нь солино. Цаашид своп хийх шаардлагагүй болтол энэ эргэлтийг давтана. Сонголтыг эрэмбэлэх нь мөн жагсаалтаас хамгийн бага элементийг олж, эхний элементээр солих замаар эхэлдэг эрэмбэлэх алгоритм юм. Энэ үйл явц нь солигдсон элементүүдийг дарааллаар нь байрлуулах замаар жагсаалтын үлдсэн хэсэгт давтагдана.
Bubble Sort гэж юу вэ?
Хөөсөөр эрэмбэлэх нь зэргэлдээ орших элементүүдийн хосыг харьцуулах явцад дахин дахин эрэмбэлэх жагсаалтын дагуу ажилладаг эрэмбэлэх алгоритм юм. Хэрэв хос элементүүд буруу дарааллаар байвал тэдгээрийг зөв дарааллаар нь солино. Цаашид своп хийх шаардлагагүй болтол энэ эргэлт давтагдана (энэ нь жагсаалт эрэмблэгдсэн гэсэн үг). Жагсаалтын жижиг элементүүд нь бөмбөлөг гадаргуу дээр гарч ирэхэд дээд талд гарч ирдэг тул үүнийг хөөс сорт гэж нэрлэдэг. Бөмбөлөгөөр эрэмбэлэх нь маш энгийн эрэмбэлэх алгоритм боловч n элементтэй жагсаалтыг эрэмбэлэх үед O(n2)-ийн дундаж тохиолдлын нарийн төвөгтэй байдалтай байдаг. Үүнээс шалтгаалан хөөсөөр эрэмбэлэх нь олон тооны элемент бүхий жагсаалтыг эрэмбэлэхэд тохиромжгүй. Гэхдээ энгийн учраас хөөсөөр ангилах аргыг алгоритмын танилцуулгад заадаг.
Сонголтын эрэмбэ гэж юу вэ?
Сонголтоор эрэмбэлэх нь жагсаалтаас хамгийн бага элементийг олж эхний элементээр солих замаар эхэлдэг өөр нэг эрэмбэлэх алгоритм юм. Дараа нь хамгийн бага элементийг жагсаалтын үлдсэн хэсгээс (хоёр дахь элементээс жагсаалтын сүүлчийн элемент хүртэл) олж, хоёр дахь элементтэй солино. Энэ үйл явц нь солигдсон элементүүдийг дарааллаар нь байрлуулах замаар жагсаалтын үлдсэн хэсэгт давтагдана. Сонголтыг эрэмбэлэхдээ алгоритмын аль ч алхамд жагсаалтыг хоёр хэсэгт хуваадаг бөгөөд нэг хэсэг нь эрэмбэлэгдсэн элементүүдийг, нөгөө хэсэг нь эрэмбэлэгдээгүй элементүүдийг агуулна. Алгоритм үргэлжлэх тусам эрэмбэлэгдсэн жагсаалт зүүнээс баруун тийш өснө. Сонголтын эрэмбэ нь мөн O(n2) дундаж тохиолдлын хугацааны нарийн төвөгтэй байдалтай байна. Тиймээс энэ нь том жагсаалтыг эрэмбэлэхэд тохиромжгүй.
Хөөсөөр эрэмбэлэх болон сонгох эрэмбэ хоёрын ялгаа юу вэ?
Хөөсөөр эрэмбэлэх болон сонгон эрэмбэлэх алгоритмууд нь O(n2)-ын дундаж тохиолдлын хугацааны нарийн төвөгтэй байдаг хэдий ч хөөсөөр эрэмбэлэх нь сонголтын ангиллаар бараг бүх цаг үеийнхээс илүү байдаг. Энэ нь хоёр алгоритмд шаардлагатай свопуудын тоотой холбоотой юм (хөөсний сортуудад илүү их своп хэрэгтэй). Гэхдээ хөөс ялгах энгийн байдлаас шалтгаалан кодын хэмжээ нь маш бага юм. Тогтвортой байдал нь эдгээр хоёр алгоритмын өөр нэг ялгаа юм. Тогтвортой эрэмбэлэх алгоритм нь жагсаалтад тэнцүү утгатай элементүүд орсон тохиолдолд бичлэгийн дарааллыг хадгалдаг эрэмбэлэх алгоритм юм. Энэ утгаараа сонгон эрэмбэлэх нь тогтвортой алгоритм биш харин хөөсөөр эрэмбэлэх нь тогтвортой алгоритм юм.
