Quicksort како метод на програмирање

Во 1960 година, К. А. Hoar развиле метод за брзо сортирање на информации, стана најпознат. Денес тоа е широко се користат во програмирање, како што има многу позитивни особини: тоа може да се користи за општи случаи, тоа бара мало зголемување на дополнителна меморија, компатибилен со различни видови на листи и лесно да се спроведе. Но, постојат недостатоци, која има Quicksort: користење на работа е дозволено многу грешки, и тоа е малку нестабилна.

Сепак, тоа е од најпознатите студирал верзија. По првата уплата Hoare, многу си ја работи својата густа студија. голема база е основана на теоретски прашања за наоѓање на времето поминато на работа, која е дополнета со емпириски докази. Имаше реални предлози за подобрување на основни алгоритам и зголемување на брзината.

Quicksort е многу честа појава, тоа може да се најде насекаде. Врз основа на него методот се спроведува TList.Sort, присутен во сите верзии (освен 1) Делфи, функција библиотеката на времето потребно да се заврши, qsort во C ++.

Основниот принцип на работа може да биде формулирана како "Раздели, па владеј". Тоа се случува да се прекрши на листата во две групи и се подредени за секој дел од себе. Следи дека треба да се посвети поголемо внимание на процесот на поделба, при што се случува следново: се определува со основниот елемент и релативно средена целата своја листа. Изградена од лево на група на кандидати, чија вредност е помала од сите други правила за пренос. Излегува дека главен елемент во сортирана листа е во своето место. Во следната фаза - предизвик рекурзивен функција за сортирање на двете страни на елементите во однос на базата. Тој завршува процесот работи само ако на листата содржи само еден елемент, кој треба да се подредени. Така, со цел да се справат со функција програмирање како брз вид, е неопходно да се знае за работата на алгоритми на пониско ниво: а) избор на член база; б) листа од најефикасните пермутација да се произведе два сета со помали и поголеми вредности.

Се запознаат со основните начела. При изборот на член база, идеално треба да бидат избрани од листата на просекот. Потоа на пауза е поделена во две еднакви половини. Само се пресмета просечната вредност во листата е многу тешко, па дури и на најбрз сортирање заобиколува оваа анализа страна. Но, изборот на основен елемент со максимум или минимум вредност - исто така не е најдобра опција. Во случај на таква решителност што се создава празен листи ќе се гарантира и втората полна. Оттука и заклучокот дека како основа член треба да биде избран оној кој е поблиску до просекот, но на максимум и минимум.

Откако избор се утврдува, може да продолжи да алгоритам распаѓање. Оваа т.н. внатрешна јамки брзо вид. Сè што е изграден на две Рапид индекси Пристап: прво одиме во текот на елементи од лево кон десно, втората, напротив, од десно кон лево. Започнува токму извршување на работа: индексот е на листата и да се споредат сите вредности на главниот. На циклус е завршен кога елементот е помала од или еднаква на основната линија. Тоа е, постои споредба и ја намалува вредноста на индексот. На левата страна, кога работата е завршена поголема или еднаква вредност. Тука, се зголемува вредност споредба.

Во оваа фаза на поделба алгоритам кој што се состои од quicksort, може да се појават две ситуации. Првата е дека индексот на левата страна е помалку од десната страна. Ова укажува на грешка, тогаш постојат елементи на кои што беше наведено во списокот се во погрешна цел. Излез - промени на своите места. Втората ситуација е кога и на колоната е еднаква или раце. Ова укажува на успешна одделување на листа, тоа е, работата е завршена.