Бързо сортиране в Java Обяснено

Наполовина конвенция

Когато броят на елементите в списък е четен, наполовина списъка означава, че буквалната първа половина на списъка е първата половина, а буквалната втора половина на списъка е втората половина. Средният (среден) елемент от целия списък е последният елемент от първия списък. Това означава, че средният индекс е дължина / 2 - 1, тъй като броенето на индекса започва от нула. Дължината е броят на елементите в списъка. Например, ако броят на елементите е 8, тогава първата половина на списъка има 4 елемента, а втората половина на списъка също има 4 елемента. Това е добре. Тъй като броенето на индекси започва от 0, средният индекс е 3 = 8 /2 - 1.

Какво ще кажете за случая, когато броят на елементите в списъка или под-списъка е нечетен? В началото дължината все още е разделена на 2. По условство броят на елементите в първата половина на това разделение е дължина / 2 + 1/2. Преброяването на индекса започва от нула. Средният индекс се определя от дължина / 2 - 1/2. По конвенция това се счита за среден срок. Например, ако броят на елементите в списък е 5, тогава средният индекс е 2 = 5/2 - 1/2. И има три елемента в първата половина на списъка и два елемента във втората половина. Средният елемент от целия списък е третият елемент от индекс 2, който е средният индекс, тъй като броенето на индекса започва от 0.

Делението по този начин е пример за целочислена аритметика.

Медиана на три стойности

Въпрос: Каква е медианата на последователността:

C B A

Решение:
Подредете списъка във възходящ ред:

A B C

Средният термин, B, е медианата. Това е величината, която се намира между другите две величини.

Търсенето на медиана в списък не е такъв вид. Например в списък от 19 елемента без сортиране може да се наложи медианата за първия елемент, средния елемент и последния елемент. Тези три стойности може да не са във възходящ ред; и така, техните индекси трябва да бъдат взети под внимание.

С Бързо сортиране са необходими медианата за целия списък и под-списъците. Псевдокодът за търсене на медианата на три стойности, разположени в списък (масив) е:

Терминът arr означава масив. Този кодов сегмент търси медианата и също така извършва известно сортиране. Този кодов сегмент изглежда прост, но може да бъде доста объркващ. Така че, обърнете внимание на следното обяснение:

Сортирането в този урок ще създаде списък, където първата стойност е най -малката стойност, а последната стойност е най -голямата стойност. С азбуката A е по -малко от Z.

Тук опората е получената медиана. Low е най-ниският индекс на списъка или под-списъка (не е задължително за най-ниската стойност); high е най-високият индекс на списъка или под-списъка (не е задължително за най-високата стойност), а middle е конвенционалният среден индекс (не е задължително за средната стойност на целия списък).

Така че средната стойност, която трябва да се получи, е между стойността на най -ниския индекс, стойността на средния индекс и стойността на най -високия индекс.

В кода първо се получава конвенционалният среден индекс. При това стартиране списъкът е несортиран. Сравнението и известно пренареждане във възходящ ред на трите стойности трябва да се извършат едновременно. Първият оператор if сравнява стойността за най-ниския индекс и тази на средния индекс. Ако този на средния индекс е по -малък от този на най -ниския индекс, тогава двете стойности сменят позициите. Това започва сортирането и променя подредбата на стойностите в списъка или под-списъка. Вторият оператор if сравнява стойността за най-високия индекс и тази на най-ниския индекс. Ако този на най -високия индекс е по -малък от този на най -ниския индекс, двете стойности сменят позициите. Това продължава известно сортиране и промяна на подреждането на стойностите в списъка или под-списъка. Третият оператор if сравнява стойността за средния индекс и тази на най-високия индекс. Ако този на най -високия индекс е по -малък от средния индекс, двете стойности сменят позициите. Тук може да възникне и известно сортиране или пренареждане. Това трето if-условие не е като предишните две.

В края на тези три размяни средната стойност на въпросните три стойности би била A [висока], чието първоначално съдържание може да е било променено в сегмента на кода. Например, помислете за несортираната последователност:

C B A

Вече знаем, че медианата е В. Това обаче трябва да се докаже. Целта тук е да се получи медианата на тези три стойности с помощта на горния кодов сегмент. Първият оператор if сравнява B и C. Ако B е по-малко от C, тогава позициите на B и C трябва да бъдат разменени. B е по -малко от C, така че новото подреждане става:

B C A

Забележете, стойностите за най -ниския индекс и средния индекс са се променили. Вторият оператор if сравнява A и B. Ако A е по-малко от B, тогава позициите на A и B трябва да бъдат разменени. A е по -малко от B, така че новото подреждане става:

A C B

Забележете, стойностите за най -високия и най -ниския индекс са се променили. Третият оператор if сравнява C и B. Ако C е по-малко от B, тогава позициите на C и B трябва да бъдат разменени. C не е по -малко от B, така че не се извършва размяна. Новото подреждане остава като предишното, а именно:

A C B

B е медианата, която е, A [висока], и това е опората. И така, пивотът се ражда в крайния край на списъка или под-списъка.

Функцията за смяна

Друга функция, необходима на Quick Sort, е функцията за смяна. Функцията за размяна обменя стойностите на две променливи. Псевдокодът за функцията за смяна е:

Тук x и y се отнасят за действителните стойности, а не за копията.

Сортирането в тази статия ще доведе до списък, където първата стойност е най -малката стойност, а последната стойност е най -голямата стойност.

Съдържание на статията

• Алгоритъм за бързо сортиране
• Псевдокод на дял
• Илюстрация за бързо сортиране
• Java кодиране
• Заключение

Алгоритъм за бързо сортиране

Нормалният начин за сортиране на несортиран списък е да се вземат предвид първите две стойности. Ако не са в ред, подреди ги. След това помислете за първите три стойности. Сканирайте първите две, за да видите къде се вписва третата стойност и я поставете по подходящ начин. След това помислете за първите четири стойности. Сканирайте първите три стойности, за да видите къде се вписва четвъртата стойност и да я поставите по подходящ начин. Продължете с тази процедура, докато целият списък не бъде сортиран.

Тази процедура, известна още като сортиране на грубата сила, в езика на компютърното програмиране, е твърде бавна. Алгоритъмът за бързо сортиране идва с много по -бърза процедура.

Стъпките за алгоритъма за бързо сортиране са както следва:

1. Уверете се, че има поне 2 числа за сортиране в несортирания списък.
2. Вземете приблизителна централна стойност за списъка, наречена пивот. Медианата, както е описано по -горе, е един от начините за получаване на опората. Различните начини идват със своите предимства и недостатъци. - Вижте по -късно.
3. Разделете списъка. Това означава, поставете пивота в списъка. По този начин всички елементи вляво са по -малки от стойността на завъртане, а всички елементи вдясно са по -големи или равни на стойността на завъртане. Има различни начини за разделяне. Всеки метод на разделяне има своите предимства и недостатъци. Разделянето е разделяне в парадигмата „разделяй и владей“.
4. Повторете стъпки 1, 2 и 3 рекурсивно за новите двойки подсписки, които се появяват, докато целият списък не бъде сортиран. Това е завладяващо в парадигмата „разделяй и владей“.

Псевдокодът за бързо сортиране е:

Псевдокод на дял

Псевдокодът на дяловете, използван в този урок, е:

В илюстрацията за бързо сортиране по -долу се използва този код:

Илюстрация за бързо сортиране

Помислете за следния несортиран списък (масив) от азбучни букви:

Q W E R T Y U I O P

При проверка сортираният списък е:

E I O P Q R T U W Y

Сортираният списък сега ще бъде доказан, като се използва горният алгоритъм и сегментите на псевдокода, от несортирания списък:

Q W E R T Y U I O P

Първият пивот се определя от arr [0] = Q, arr [4] = T и arr [9] = P и се идентифицира като Q и се поставя в крайния десен ъгъл на списъка. Така че списъкът с всяко сортиране на въртяща се функция става:

P W E R T Y U I O Q

Текущият пивот е Q. Процедурата за завъртане направи малко сортиране и постави P на първа позиция. Полученият списък трябва да бъде пренареден (разделен), така че всички елементи вляво да са с по -малка стойност, след това пивотът и всички елементи вдясно от шарнира са равни или по -големи от опората. Компютърът не може да направи разделяне чрез проверка. Така че, това става с помощта на индексите и горния алгоритъм на дяловете.

Ниските и високите индекси вече са 0 и 9. И така, компютърът ще започне със сканиране от индекса 0, докато достигне индекс, чиято стойност е равна или по -голяма от пивота и временно спира там. Той също така ще сканира от горния (десния) край, индекс 9, слизащ надолу, докато достигне индекс, чиято стойност е по -малка или равна на пивота и временно спира там. Това означава две позиции на стоп. Ако i, променливата на нарастващия индекс от ниско все още не е равна или по -голяма от намаляващата индексна променлива, j от висока, тогава тези две стойности се разменят. В настоящата ситуация сканирането от двата края спира на W и O. Така списъкът става:

P O E R T Y U I W Q

Оборотът все още е Q. Сканирането в противоположни посоки продължава и спира съответно. Ако i все още не е равно или по -голямо от j, тогава двете стойности, при които сканирането от двата края е спряно, се разменят. Този път сканирането от двата края спря на R и I. Така че подреждането на списъка става:

P O E I T Y U R W Q

Оборотът все още е Q. Сканирането в противоположни посоки продължава и спира съответно. Ако i все още не е равно или по -голямо от j, тогава двете стойности, при които сканирането е спряло, се разменят. Този път сканирането от двата края спря в T за i и I за j. i и j са се срещнали или пресекли. Така че не може да има замяна. Списъкът остава същият като:

P O E I T Y U R W Q

В този момент опората Q трябва да бъде поставена в крайното си положение при сортирането. Това става чрез замяна на arr [i] с arr [високо], размяна на Т и Q. Списъкът става:

P O E I Q Y U R W T

На този етап разделянето на целия списък приключи. Pivot = Q е изиграл своята роля. Сега има три под-списъка, които са:

P O E I Q Y U R W T

Разделението е разделяне и завладяване (сортиране) в парадигмата. Q е в правилната си позиция за сортиране. Всеки елемент вляво от Q е по -малък от Q и всеки елемент вдясно от Q е по -голям от Q. Въпреки това, левият списък все още не е сортиран; и десният списък все още не е сортиран. Цялата функция за бързо сортиране трябва да бъде извикана рекурсивно, за да сортира левия под-списък и десния под-списък. Това изземване на Quick Sort трябва да продължи; нови под-списъци ще се развиват, докато целият оригинален списък не бъде напълно сортиран. За всяко извикване на функцията за бързо сортиране, левият подсписък се проверява първо преди съответния десен подсписък. Трябва да се получи нов пивот за всеки под-списък.

За под-списъка:

P O E I

Определя се опората (медиана) за P, O и I. Оборотът ще бъде O. За този под-списък и във връзка с пълния списък новият arr [нисък] е arr [0], а новият arr [висок] е последният arr [i-1] = arr [ 4-1] = arr [3], където i е крайният пивотен индекс от предишния дял. След извикване на функцията pivot (), новата стойност на въртене, pivot = O. Не бъркайте между функцията за завъртане и стойността на въртене. Функцията за завъртане може да извърши малко сортиране и да постави свода в крайния десен ъгъл на под-списъка. Този под-списък става,

I P E O

При тази схема завъртането винаги завършва в десния край на под-списъка или списъка след извикването на неговата функция. Сканирането от двата края започва от arr [0] и arr [3], докато i и j се срещнат или пресекат. Сравнението се прави с pivot = O. Първите спирки са в P и E. Те се разменят и новият под-списък става:

I E P O

Сканирането от двата края продължава, а новите спирки са в P за i и в E за j. Сега аз и j се срещнахме или кръстосахме. Така че под-списъкът остава същият като:

I E P O

Разделянето на под-списък или списък приключва, когато опората е поставена в крайната си позиция. Така че новите стойности за arr [i] и arr [high] се разменят. Тоест, P и O се разменят. Новият под-списък става:

I E O P

O сега е в крайната си позиция за целия списък. Ролята му на опора приключи. Понастоящем под-списъкът е разделен на още три списъка, които са:

I E O P

В този момент трябва да се извика Бързо сортиране на първия десен подспис. Тя обаче няма да бъде извикана. Вместо това тя ще бъде отбелязана и запазена, за да бъде наречена по -късно. Тъй като операторите на функцията за разделяне се изпълняват, от горната част на функцията, бързото сортиране за левия под-списък трябва да бъде извикано сега (след като е извикан pivot ()). Той ще бъде извикан за списъка:

I E

Ще започне с търсене на медианата на I и E. Тук, arr [ниска] = I, arr [средна] = I и arr [висока] = E. Така че медианата, pivot, трябва да се определи от алгоритъма за завъртане като , I. Обаче горният псевдокод на завъртане ще определи шарнира като Е. Тази грешка възниква тук, защото горният псевдокод е предназначен за три елемента, а не за два. В изпълнението по -долу има известна корекция на кода. Под-списъкът става,

E I

Оборотът винаги завършва в десния край на под-списъка или списъка след извикването на неговата функция. Сканирането от двата края започва от arr [0] и arr [1] изключително, докато i и j се срещнат или пресекат. Сравнението се прави с пивот = I. Първите и единствени спирки са в I и E: при I за i и при E за j. Сега i и j са се срещнали или пресекли. Така че под-списъкът остава същият като:

E I

Разделянето на под-списък или списък приключва, когато опората е поставена в крайната си позиция. Така че новите стойности за arr [i] и arr [high] се разменят. Тук се случва, че arr [i] = I и arr [високо] = I. Така че същата стойност се заменя със себе си. Новият под-списък става:

E I

Сега съм на последната позиция за целия списък. Ролята му на опора приключи. Под-списъкът вече е разделен на още два списъка, които са,

E I

Сега шарнирите досега бяха Q, O и I. Пивотите завършват на крайните си позиции. Под-списък на един елемент, като P по-горе, също завършва на крайната си позиция.

В този момент първият ляв под-списък е напълно сортиран. Процедурата за сортиране сега е на адрес:

E I O P Q Y U R W T

Първият десен подспис:

Y U R W T

все още трябва да се сортира.

Завладяване на първия десен под-списък
Не забравяйте, че повикването за бързо сортиране за първия десен под-списък е отбелязано и запазено, вместо да бъде изпълнено. В този момент тя ще бъде изпълнена. И така, новият arr [нисък] = arr [5] = arr [QPivotIndex+1], а новият arr [висок] остава arr [9]. Подобен набор от дейности, които се случиха за първия ляв под-списък, ще се случи тук. И този първи десен под-списък е сортиран по:

R T U W Y

Оригиналният несортиран списък е сортиран на:

E I O P Q R T U W Y

Java кодиране

Поставянето на алгоритъма в Java е просто да поставите всички горепосочени сегменти на псевдокод в Java методи в един клас. Не забравяйте, че в класа трябва да има метод main (), който да извиква функцията quicksort () с несортирания масив.

Методът pivot ()

Методът Java pivot (), който връща стойността, pivot, трябва да бъде:

Методът swap ()

Методът swap () трябва да бъде:

Методът quicksort ()

Методът quicksort () трябва да бъде:

Методът partition ()

Методът partition () трябва да бъде:

Методът main ()

Методът main () може да бъде:

Всички горепосочени методи могат да бъдат поставени в един клас.

Заключение

Бързото сортиране е алгоритъм за сортиране, който използва парадигмата разделяй и владей. Той започва с разделяне на несортиран списък на два или три под-списъка. В този урок Quick Sort е разделил списък на три под-списъка: ляв под-списък, среден списък на един елемент и десен под-списък. Завладяването в Бързо сортиране е разделяне на списък или под-списък, докато го сортирате, като използвате обобщена стойност. Този урок обяснява една реализация на Quick Sort на компютърния език на Java.

За автора

Хризантус Форча

Откривател на математическата интеграция от Първи принципи и свързани серии. Магистърска степен по техническо образование, специализирана в електроника и компютърен софтуер. Бакалавърска електроника. Също така имам знания и опит на ниво магистър по компютърни технологии и телекомуникации. От 20 000 писатели бях 37 -ият най -добър писател на devarticles.com. Работя в тези области повече от 10 години.

СВЪРЗАНИ ПОСТАВКИ НА ЛИНУКС

• Сравняване на низове в Java
• Как да използвате HashMap в Java
• Бързо сортиране в Java Обяснено
• Обхождане на предварително поръчване на двоично дърво в Java
• Обяснено обединяване на сортиране в Java
• Как да използвате скенера в Java
• Java запис във файл