Програмчлалын арга гэж Quicksort

1960 онд К. A. Hoar, мэдээллийг хурдан ялгах аргыг боловсруулсан хамгийн алдартай болжээ. Өнөөдөр энэ нь өргөн, програмчлалд хэрэглэгддэг бөгөөд энэ нь эерэг шинж чанар нь маш их байдаг нь: энэ нь ерөнхий тохиолдолд хэрэглэж болно, энэ жагсаалт өөр өөр төрлийн нийцтэй, хэрэгжүүлэхэд хялбар нэмэлт санах ой нь жижиг нэмэгдсэн шаарддаг. ашиглан ажлын алдаа маш их зөвшөөрдөг бөгөөд энэ нь зарим талаар тогтворгүй байна: Гэвч Quicksort байдаг бөгөөд энэ нь сул тал юм.

Гэсэн хэдий ч, энэ нь хамгийн их судлагдсан хувилбар юм. Эхний төлбөрийн Hoare дараа олон түүний нягт судалгаа хийж байна. том суурь цаг ажил, эмпирик нотолгоо тулгуурлаж байна зарцуулсан олох онолын асуудлаар байгуулагдсан. үндсэн алгоритм болон нэмэгдсэн хурдыг сайжруулах бодит санал байсан.

Quicksort энэ нь хаа сайгүй харж болно, маш элбэг байдаг. түүний үндсэн дээр арга TList.Sort, бүх хувилбаруудад Delphi, энэ ++ C-д qsort дуусгах, авсан цаг хугацаа номын сангийн үйл ажиллагаа (1 бусад) одоогийн хэрэгжүүлж байна.

үйл ажиллагааны үндсэн зарчим нь "хуваагдал ба давах" гэж томъёолж болно. Энэ нь хоёр бүлэг болгон жагсаалтыг зөрчсөн тохиолдох ба өөрөө хэсэг тус бүрээр ангилсан байна. суурь элемент тодорхойлсон бөгөөд харьцангуй түүний бүрэн жагсаалтыг өөрчлөлт орууллаа байна: энэ нь илүү анхаарал тусгаарлах үйл явц дараах тохиолддог бөгөөд энэ үед төлсөн гэж ёстой дагадаг. нэр дэвшигчдийн бүлгийн зүүн талд барьсан, үнэ цэнэ нь бусад бүх шилжүүлэх дүрэм-ээс бага байна. Энэ нь ангилж жагсаалтад гол элемент нь хууль ёсны газар байна гэж болж байна. Дараагийн үе шат - үндсэн харьцангуй элементүүдийн аль аль талд нь асуудал рекурсив ангилан ялгах үйл ажиллагаа. Энэ үйл явц нь жагсаалт нь зөвхөн нэг элементийг агуулсан зөвхөн ажил дуусна гэж ангилж болох юм. Тиймээс хурдан төрлийн зэрэг програмчлалын функц эзэн тулд шаардлагатай доод түвшний алгоритм ажлыг мэдэх нь байна: а) үндсэн гишүүн сонгох; б) жижиг, том үнэт зүйлс нь хоёр багцаар үйлдвэрлэх хамгийн үр дүнтэй permutation жагсаалт.

Эхний зарчим танилцах. үндсэн гишүүн сонгох үед хамгийн тохиромжтой дундаж жагсаалтаас сонгох хэрэгтэй. Дараа нь завсарлагааны хоёр тэнцүү тэнцүү хагаст хуваагдана. Зүгээр л тооцоход дундаж утга нь жагсаалтанд нь маш хэцүү байдаг, тиймээс тэр ч байтугай хамгийн хурдан ангилан ялгах энэ тооцооллоор талд алгасан. Харин хамгийн их буюу хамгийн бага утга нь үндсэн элемент сонголт - Мөн хамгийн тохиромжтой сонголт. тохиолдолд нэг нь ийм шийдвэр хоосон жагсаалт баталгаатай болно, харин хоёр дахь нь бүрэн бий болгож байна. Тиймээс үндсэн гишүүнээр дундажтай ойролцоо байна нэгийг нь сонгох ёстой, гэхдээ хамгийн их ба хамгийн бага дээр дүгнэлт.

Нэгэнт сонголт тодорхойлно, та задрал алгоритм гүйцэтгэж болно. Энэ нь хурдан төрөл гэж нэрлэгдэх дотоод гарахгүй. Бүх зүйл хоёр Шуурхай Access индекс дээр баригдсан байна: зүүн баруун хойш, эсрэгээр, баруун, хоёр дахь тийш элемент дээр анх удаа явж байна. Эхэлдэг үйл ажиллагаа гүйцэтгэх эрх: индекс жагсаалтад байгаа бөгөөд гол нь бүх утгыг харьцуулах хэрэгтэй. элемент суурь бага буюу тэнцүү байх үед мөчлөг дууссан байна. Энэ бол харьцуулалт байдаг бөгөөд индексийн утга буурч байна. зүүн талаас ажил илүү буюу тэнцүү утга нь их дууссаны дараа байна. Энд харьцуулалт үнэ цэнэ нэмэгдэнэ.

хуваалт нь алгоритм quicksort бүрдэнэ энэ шатанд хоёр нөхцөл байдал үүсч болно. Эхний зүүн талд индекс баруун бага байдаг юм. Энэ нь алдаа зааж, дараа нь энэ жагсаалтад заасан байсан нь дээр элементүүд нь буруу дарааллаар байдаг байна. Гаралтын - байраа өөрчлөх. баганын аль алинд нь тэнцүү буюу гаталж байх үед хоёр дахь нөхцөл байдал юм. Энэ жагсаалт нь амжилттай тусгаарлах харуулж Өөрөөр хэлбэл, ажил одоо дууссан байна.