Хөөсөөр эрэмбэлэх ба Оруулах эрэмбэ
Хөөсөөр эрэмбэлэх нь зэргэлдээ орших элементүүдийн хосыг харьцуулах явцад дахин дахин эрэмбэлэх жагсаалтын дагуу ажилладаг эрэмбэлэх алгоритм юм. Хэрэв хос элементүүд буруу дарааллаар байвал тэдгээрийг зөв дарааллаар нь солино. Цаашид своп хийх шаардлагагүй болтол энэ эргэлтийг давтана. Оруулах эрэмбэлэх нь мөн эрэмбэлэх алгоритм бөгөөд оролтын жагсаалтад аль хэдийн эрэмблэгдсэн жагсаалтын зөв байрлалд элемент оруулах замаар ажилладаг. Жагсаалтыг эрэмбэлэх хүртэл энэ процессыг давтан хийнэ.
Bubble Sort гэж юу вэ?
Хөөсөөр эрэмбэлэх нь зэргэлдээх элементүүдийн хосыг харьцуулах явцад дахин дахин эрэмбэлэх жагсаалтын дагуу ажилладаг эрэмбэлэх алгоритм юм. Хэрэв хос элементүүд буруу дарааллаар байвал тэдгээрийг зөв дарааллаар нь солино. Цаашид своп хийх шаардлагагүй болтол энэ эргэлт давтагдана (энэ нь жагсаалт эрэмблэгдсэн гэсэн үг). Жагсаалтын жижиг элементүүд нь бөмбөлөг гадаргуу дээр гарч ирэхэд дээд талд гарч ирдэг тул үүнийг хөөс сорт гэж нэрлэдэг. Бөмбөлөгөөр эрэмбэлэх нь маш энгийн эрэмбэлэх алгоритм боловч n элементтэй жагсаалтыг эрэмбэлэх үед O(n2)-ийн дундаж тохиолдлын нарийн төвөгтэй байдалтай байдаг. Үүнээс шалтгаалан хөөсөөр эрэмбэлэх нь олон тооны элемент бүхий жагсаалтыг эрэмбэлэхэд тохиромжгүй. Гэхдээ энгийн учраас хөөсөөр ангилах аргыг алгоритмын танилцуулгад заадаг.
Оруулах эрэмбэ гэж юу вэ?
Оруулах эрэмбэлэх нь өөр нэг эрэмбэлэх алгоритм бөгөөд оролтын жагсаалтын элементийг жагсаалтын зөв байрлалд оруулах замаар ажилладаг (энэ нь аль хэдийн эрэмблэгдсэн). Жагсаалтыг эрэмбэлэх хүртэл энэ процессыг давтан хийнэ. Оруулах төрөлд ангилах ажлыг газар дээр нь хийдэг. Иймд алгоритмын 1-р давталтын дараа жагсаалтын эхний i+1 оруулгуудыг эрэмбэлэх ба бусад жагсаалтуудыг эрэмбэлэхгүй. Давталт бүрт жагсаалтын эрэмблэгдээгүй хэсгийн эхний элементийг авч, жагсаалтын эрэмбэлэгдсэн хэсгийн зөв газарт оруулна. Оруулсан эрэмбэ нь O(n2)-ийн дундаж тохиолдлын цагийн нарийн төвөгтэй байдалтай байна. Үүнээс шалтгаалан оруулах эрэмбэ нь том жагсаалтыг эрэмбэлэхэд тохиромжгүй.
Хөөсөөр эрэмбэлэх болон оруулах эрэмбэ хоёрын ялгаа юу вэ?
Хөөсөөр эрэмбэлэх болон оруулах эрэмбэлэх алгоритмууд нь O(n2)-ийн дундаж тохиолдлын хугацааны нарийн төвөгтэй байдаг хэдий ч хөөсөөр эрэмбэлэх нь оруулах эрэмбэлэлтээс бараг үргэлж илүү байдаг. Энэ нь хоёр алгоритмд шаардлагатай свопуудын тоотой холбоотой юм (хөөсний сортуудад илүү их своп хэрэгтэй). Гэхдээ хөөс ялгах энгийн байдлаас шалтгаалан кодын хэмжээ нь маш бага юм. Мөн O(n3/2) цаг хугацааны нарийн төвөгтэй, практикт ашиглах боломжийг олгодог бүрхүүлийн сорт гэж нэрлэгддэг оруулах сортын хувилбар байдаг. Цаашилбал, оруулах эрэмбэ нь хөөстэй эрэмбэлэхтэй харьцуулахад "бараг эрэмбэлсэн" жагсаалтыг эрэмбэлэхэд маш үр дүнтэй байдаг.
