Ang pag-uuri ay isa sa mga pangunahing operasyon na ginagawa namin sa mga bagay. Kahit na sa pagkabata, ang mga bata ay tinuturuan na mag-uri-uriin habang pinaunlad nila ang kanilang mga kasanayan sa pag-iisip. Ang mga computer at software ay walang pagbubukod. Mayroong isang malaking iba't ibang mga algorithm ng pag-uuri sa Java . Iminumungkahi ko na tingnan mo kung ano ang mga ito at kung paano gumagana ang mga ito. Paano kung tatanungin ka tungkol sa isa sa kanila sa isang panayam balang araw?
Ang L ay nagiging katumbas ng
Panimula
Ang pag-uuri ng mga elemento ay isa sa mga kategorya ng mga algorithm na dapat malaman ng isang developer. Kung minsan ay hindi sineseryoso ang computer science noong ako ay nasa paaralan, ang mga mag-aaral ngayon ay dapat na maipatupad at maunawaan ang mga algorithm ng pag-uuri. Ang mga pangunahing algorithm, ang pinakasimple, ay ipinatupad gamit ang isang for loop. Naturally, upang pag-uri-uriin ang isang koleksyon ng mga elemento, tulad ng isang array, kailangan mong dumaan sa koleksyon. Halimbawa:
int[] array = {10, 2, 10, 3, 1, 2, 5};
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
int i) mula 0 hanggang sa huling elemento sa array. Sa katunayan, kinukuha lang namin ang bawat elemento sa array at ini-print ang mga nilalaman nito. Ang mas maraming mga elemento sa array, mas matagal ang code ay aabutin upang matapos. Iyon ay, kung nang bilang ng mga elemento, kapag n = 10ang programa ay tatagal ng dalawang beses na mas mahaba upang tumakbo kaysa kapag n = 5. Kung ang aming programa ay may isang solong loop, ang oras ng pagpapatupad ay lumalaki nang linearly: mas maraming elemento ang mayroon, mas mahaba ang oras ng pagpapatupad. Lumalabas na ang algorithm sa itaas ay gumagana sa linear time (isang linear function ng n). Sa ganitong mga kaso, sinasabi namin na ang pagiging kumplikado ng algorithm ay "O(n)". Ang notasyong ito ay tinatawag ding "big O" o "asymptotic behavior". Pero tandaan mo lang"
Ang pinakasimpleng algorithm ng pag-uuri (bubble sort)
Ipagpalagay na mayroon kaming isang array at maaari naming ulitin ito. Malaki. Ngayon, subukan nating ayusin ito sa pataas na pagkakasunud-sunod. Ano ang ibig sabihin nito? Nangangahulugan ito na binigyan ng dalawang elemento (halimbawa,a = 6, b = 5), kailangan nating muling ayusin aat bkung amas malaki kaysa sa b(kung a > b). Ano ang ibig sabihin nito kapag gumagamit kami ng isang index upang gumana sa isang koleksyon (tulad ng kaso sa isang array)? Nangangahulugan ito na kung ang elementong may index a ay mas malaki kaysa sa elementong may index b( array[a] > array[b]), kung gayon ang mga elemento ay dapat na palitan. Mayroong iba't ibang mga paraan upang baguhin ang mga lugar. Ngunit gagamit kami ng pamamaraan na simple, naiintindihan at madaling tandaan:
private void swap(int[] array, int ind1, int ind2) {
int tmp = array[ind1];
array[ind1] = array[ind2];
array[ind2] = tmp;
}
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i-1);
}
}
System.out.println(Arrays.toString(array));
array[i] < array[i-1]ay hindi wasto para sa index 0. Ang paggawa nito ay pinoprotektahan din tayo mula sa mga kaso kung saan ang array ay walang mga elemento o isang elemento lamang, at ginagawa nitong mas maganda ang code. Ngunit ang resultang array ay hindi pa rin pinagsunod-sunod, dahil ang isang pass ay hindi sapat upang gawin ang pag-uuri. Kakailanganin nating magdagdag ng isa pang loop kung saan magsasagawa tayo ng mga pass nang paulit-ulit hanggang sa makakuha tayo ng pinagsunod-sunod na array:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
boolean needIteration = true;
while (needIteration) {
needIteration = false;
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i-1);
needIteration = true;
}
}
}
System.out.println(Arrays.toString(array));
while) hanggang sa mapagpasyahan namin na wala nang mga pag-ulit ang kailangan. Bilang default, bago ang bawat bagong pag-ulit, ipinapalagay namin na ang aming array ay pinagsunod-sunod at hindi na namin kailangang mag-loop. Alinsunod dito, gumagalaw kami nang sunud-sunod sa mga elemento at sinusuri ang pagpapalagay na ito. Ngunit kung ang mga elemento ay hindi maayos, pagkatapos ay nagpapalitan kami ng mga elemento at nauunawaan na wala kaming garantiya na ang mga elemento ay nasa tamang pagkakasunud-sunod. Nangangahulugan ito na kailangan nating magsagawa ng isa pang pag-ulit. Halimbawa, ipagpalagay na mayroon tayong [3, 5, 2]. 5ay higit pa sa 3— lahat ay maayos. Ngunit 2mas mababa sa 5. Gayunpaman, [3, 2, 5]nangangailangan ng isa pang pass, dahil3 > 2at kailangan nilang palitan. Dahil gumagamit kami ng loop sa loob ng loop, tumataas ang pagiging kumplikado ng aming algorithm. Dahil sa nmga elemento, ito ay nagiging n * n, iyon ay, O(n^2). Ito ay tinatawag na quadratic complexity. Sa pangkalahatan, hindi namin alam kung gaano karaming mga pag-ulit ang kakailanganin. Ang pagpapahayag ng pagiging kumplikado ng isang algorithm ay nagpapakita kung paano tumataas ang pagiging kumplikado sa pinakamasamang kaso. Ibig sabihin, ipinapahiwatig nito kung gaano kalaki ang oras ng pagpapatupad habang nagbabago ang bilang ng mga elemento n. Ang bubble sort ay isa sa pinakasimple at hindi mahusay na mga algorithm sa pag-uuri. Tinatawag din itong "stupid sort". Materyal sa paksang ito:
Pag-uuri ng pagpili
Ang isa pang algorithm ng pag-uuri ay ang pag-uuri ng pagpili. Mayroon din itong quadratic complexity, ngunit higit pa doon sa ibang pagkakataon. Kaya ang ideya ay simple. Sa bawat pass, pipiliin namin ang pinakamaliit na elemento at ilipat ito sa simula. Bilang karagdagan, ang bawat pass ay nagsisimula ng isang hakbang sa kanan. Sa madaling salita, ang unang pass ay nagsisimula sa zeroth element, ang pangalawang pass mula sa una, atbp. Ito ay magiging ganito:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
int minInd = left;
for (int i = left; i < array.length; i++) {
if (array[i] < array[minInd]) {
minInd = i;
}
}
swap(array, left, minInd);
}
System.out.println(Arrays.toString(array));
Pag-uuri ng pagpapasok
Ang insertion sort ay mayroon ding quadratic complexity, dahil muli tayong may loop sa loob ng loop. Ano ang pinagkaiba ng insertion sort? Ang algorithm ng pag-uuri na ito ay "matatag." Nangangahulugan ito na ang magkatulad na mga elemento ay hindi magbabago sa kanilang kamag-anak na pagkakasunud-sunod. Muli, ang ibig naming sabihin ay magkapareho sa mga tuntunin ng mga katangian na pinag-uuri-uri namin.
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
// Get an element
int value = array[left];
// Iterate through the elements that are in front of this element
int i = left - 1;
for (; i >= 0; i--) {
// If the current element is smaller, then move the larger element to the right.
if (value < array[i]) {
array[i + 1] = array[i];
} else {
// If the current element is larger, we stop
break;
}
}
// Insert the current value in the empty space
array[i + 1] = value;
}
System.out.println(Arrays.toString(array));
Pag-uuri ng shuttle
May isa pang simpleng algorithm ng pag-uuri: shuttle sort. Ito ay kilala rin bilang isang bidirectional bubble sort o cocktail shaker sort. Ang mga kahaliling pangalan na ito ay nagsasabi sa amin na ang shuttle sort ay hindi tungkol sa space shuttle. Ito ay tungkol sa isang bagay na gumagalaw pabalik-balik. Ngayon ay maaari mong isipin iyon kapag naisip mo ang algorithm na ito. Ano ang kakanyahan ng algorithm? Ang kakanyahan ng algorithm ay umulit tayo mula kaliwa hanggang kanan, nagpapalit ng mga elemento at tinitingnan kung ang alinman sa mga elementong natitira sa kabilang direksyon ay kailangang palitan.
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i - 1);
for (int z = i - 1; (z - 1) >= 0; z--) {
if (array[z] < array[z - 1]) {
swap(array, z, z - 1);
} else {
break;
}
}
}
}
System.out.println(Arrays.toString(array));
Pag-uuri ng shell
Ang isa pang simpleng algorithm ng pag-uuri ay shell sort. Ang diwa nito ay katulad ng bubble sort, ngunit sa bawat pag-ulit mayroon kaming ibang agwat sa pagitan ng mga pinaghahambing na elemento. Ito ay pinutol sa kalahati sa bawat pag-ulit. Narito ang isang pagpapatupad:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
// Calculate the gap between the checked elements
int gap = array.length / 2;
// As long as there is a gap between the elements
while (gap >= 1) {
for (int right = 0; right < array.length; right++) {
// Shift the right index until we find one for which
// there is the necessary gap between it and the element before it
for (int c = right - gap; c >= 0; c -= gap) {
if (array[c] > array[c + gap]) {
swap(array, c, c + gap);
}
}
}
// Recalculate the gap
gap = gap / 2;
}
System.out.println(Arrays.toString(array));
Sumanib-uuri
Bilang karagdagan sa mga simpleng algorithm ng pag-uuri na ito, mayroon ding mas kumplikadong mga algorithm ng pag-uuri. Halimbawa, pagsamahin ang pag-uuri. Mayroong dalawang bagay na dapat tandaan. Una, ang recursion ay dumating upang iligtas tayo dito. Pangalawa, ang pagiging kumplikado ng algorithm ay hindi na quadratic, gaya ng nakasanayan na natin. Ang pagiging kumplikado ng algorithm na ito ay logarithmic. Ito ay nakasulat bilangO(n log n). Kaya ipatupad natin ito. Una, magsusulat kami ng recursive na tawag sa paraan ng pag-uuri:
public static void mergeSort(int[] source, int left, int right) {
// Select the delimiter, i.e. split the input array in half
int delimiter = left + ((right - left) / 2) + 1;
// Recursively execute this function on the two halves (if we can split the input array)
if (delimiter > 0 && right > (left + 1)) {
mergeSort(source, left, delimiter - 1);
mergeSort(source, delimiter, right);
}
}
public static void mergeSort(int[] source, int left, int right) {
// Select the delimiter, i.e. split the input array in half
int delimiter = left + ((right - left) / 2) + 1;
// Recursively execute this function on the two halves (if we can split the input array)
if (delimiter > 0 && right > (left + 1)) {
mergeSort(source, left, delimiter - 1);
mergeSort(source, delimiter, right);
}
// Create a temporary array with the required size
int[] buffer = new int[right - left + 1];
// Starting from the specified left index, go through each element.
int cursor = left;
for (int i = 0; i < buffer.length; i++) {
// We use delimeter to point to the element on the right half
// If delimeter> right, then the right half has no elements that haven't been added
if (delimiter > right || source[cursor] > source[delimiter]) {
buffer[i] = source[cursor];
cursor++;
} else {
buffer[i] = source[delimiter];
delimiter++;
}
}
System.arraycopy(buffer, 0, source, left, buffer.length);
}
mergeSort(array, 0, array.length-1). Tulad ng nakikita mo, ang proseso ay bumababa sa pagtanggap ng input array kasama ang mga indikasyon ng simula at pagtatapos ng seksyon na kailangang ayusin. Kapag nagsimula ang pag-uuri, ito ang simula at pagtatapos ng array. Pagkatapos ay kalkulahin namin ang delimiter, na siyang index kung saan hahatiin namin ang array. Kung ang array ay maaaring hatiin sa 2 bahagi, pagkatapos ay tinatawag naming recursively ang paraan ng pag-uuri para sa dalawang halves ng array. Naghahanda kami ng auxiliary buffer kung saan ilalagay namin ang pinagsunod-sunod na seksyon. Susunod, itakda ang index sa simula ng seksyon upang ayusin at simulan ang paglalakad sa bawat elemento ng walang laman na buffer, pinupunan ito ng pinakamaliit na elemento. Kung ang elementong itinuturo ng index ay mas mababa kaysa sa elementong itinuturo ng delimiter, inilalagay namin ang elemento sa buffer at inililipat ang index. Kung hindi, inilalagay namin ang elementong itinuro ng delimiter sa buffer at inilipat ang delimiter. Sa sandaling lumampas na ang delimiter sa mga hangganan ng seksyong pinagbubukod-bukod o napuno namin ang buong hanay, ang tinukoy na hanay ay ituturing na pinagsunod-sunod.Materyal sa paksang ito:
Pagbibilang ng sort at radix sort
Ang isa pang kawili-wiling algorithm ng pag-uuri ay ang pagbibilang ng pag-uuri. Ang algorithmic complexity dito ayO(n+k), kung saan nang bilang ng mga elemento at kang pinakamataas na halaga ng isang elemento. Ang algorithm na ito ay may isang pagkukulang: kailangan nating malaman ang minimum at maximum na mga halaga sa array. Narito ang isang halimbawa ng uri ng pagbibilang:
public static int[] countingSort(int[] theArray, int maxValue) {
// An array of "counters", ranging from 0 to the maximum value
int numCounts[] = new int[maxValue + 1];
// We increase the counter in the corresponding cell (index = value)
for (int num : theArray) {
numCounts[num]++;
}
// Create an array to hold the sorted result
int[] sortedArray = new int[theArray.length];
int currentSortedIndex = 0;
// Run through the array of "counters"
for (int n = 0; n < numCounts.length; n++) {
int count = numCounts[n];
// Run through the number of values
for (int k = 0; k < count; k++) {
sortedArray[currentSortedIndex] = n;
currentSortedIndex++;
}
}
return sortedArray;
}
Mabilis na pag-uuri
Well, oras na para sa dessert — mabilis na pag-uuri, isa sa pinakasikat na algorithm ng pag-uuri. Mayroon itong logarithmic complexity:O(n log n). Ang algorithm ng pag-uuri na ito ay binuo ni Tony Hoare. Kapansin-pansin, naimbento niya ito habang naninirahan sa Unyong Sobyet, kung saan nag-aral siya ng machine translation sa Moscow University at bumuo ng isang Russian-English na phrase book. Higit pa, gumagamit ang Java ng mas kumplikadong bersyon ng algorithm na ito sa Arrays.sort. Paano naman Collections.sort? Bakit hindi tingnan kung paano pinagsunod-sunod ang mga bagay "sa ilalim ng talukbong"? Narito ang code:
public static void quickSort(int[] source, int leftBorder, int rightBorder) {
int leftMarker = leftBorder;
int rightMarker = rightBorder;
int pivot = source[(leftMarker + rightMarker) / 2];
do {
// Move the left marker from left to right as long as the element is less than pivot
while (source[leftMarker] < pivot) {
leftMarker++;
}
// Move the right marker as long as the element is greater than pivot
while (source[rightMarker] > pivot) {
rightMarker--;
}
// Check whether we need to swap the elements pointed to by the markers
if (leftMarker <= rightMarker) {
// The left marker will be less than the right one only if we need to do a swap
if (leftMarker < rightMarker) {
int tmp = source[leftMarker];
source[leftMarker] = source[rightMarker];
source[rightMarker] = tmp;
}
// Shift the markers to get new borders
leftMarker++;
rightMarker--;
}
} while (leftMarker <= rightMarker);
// Execute recursively on the parts
if (leftMarker < rightBorder) {
quickSort(source, leftMarker, rightBorder);
}
if (leftBorder < rightMarker) {
quickSort(source, leftBorder, rightMarker);
}
}
int[]source), gumawa kami ng dalawang marker: kaliwa ( L) at kanan ( R). Sa unang paraan ng tawag, tumutugma sila sa simula at dulo ng array. Pagkatapos ay tinutukoy namin ang elemento ng pivot, na angkop na pinangalanan pivot. Pagkatapos nito, ang aming gawain ay ilipat ang mga halaga na mas maliit kaysa pivotsa kaliwa ng pivot, at mas malaki - sa kanan. Para magawa ito, ililipat muna namin ang Lmarker hanggang sa makakita kami ng value na mas malaki sa pivot. Kung walang makikitang mas maliit na halaga, kung gayonpivot. Pagkatapos ay ililipat namin ang
Rmarker hanggang sa makakita kami ng value na mas maliit sa
pivot. Kung walang nakitang mas malaking halaga,
Rmagiging katumbas ng
pivot. Susunod, kung ang
Lmarker ay bago ang
Rmarker o nag-tutugma dito, pagkatapos ay susubukan naming palitan ang mga elemento kung ang
Lelemento ay mas mababa sa
Relemento. Pagkatapos ay lumipat kami
Lsa kanan ng 1, at lumipat kami
Rsa kaliwa ng 1. Kapag ang
Lmarker ay gumagalaw lampas sa
Rmarker, nangangahulugan ito na kumpleto na ang pagpapalit: ang mas maliliit na value ay nasa kaliwa ng
pivot, ang mas malalaking value ay nasa kanan ng
pivot. Pagkatapos nito, tinatawag namin ang parehong paraan ng pag-uuri nang paulit-ulit sa mga subarray — mula sa simula ng seksyon na pagbukud-bukurin hanggang sa kanang marker, at mula sa kaliwang marker hanggang sa dulo ng seksyon na pagbukud-bukurin. Bakit mula sa simula hanggang sa tamang marker? Dahil sa pagtatapos ng isang pag-ulit, lumalabas na ang kanang marker ay gumagalaw nang sapat upang maging hangganan ng kaliwang bahagi. Ang algorithm na ito ay mas kumplikado kaysa sa simpleng pag-uuri, kaya pinakamahusay na i-sketch ito. Kumuha ng puting papel at isulat ang: 4 2 6 7 3. Pagkatapos ay isulat
pivotsa gitna, ie sa ilalim ng numero 6. Bilugan ito. Sa ilalim ng 4, magsulat
L, at sa ilalim ng 3, magsulat
R. 4 mas mababa sa 6, 2 mas mababa sa 6. Tayo ay lumipat
Lsa
pivotposisyon, dahil
Lhindi makagalaw
pivot, ayon sa kondisyon. Isulat muli ang 4 2 6 7 3. Bilugan ang 6 (
pivot) at ilagay
Lsa ilalim nito. Ngayon ilipat ang
Rmarker. Ang 3 ay mas mababa sa 6, kaya ilagay ang
Rmarker sa 3. Dahil ang 3 ay mas mababa sa 6 (
pivot), nagsasagawa kami ng isang
swap. Isulat ang resulta: 4 2 3 7 6. Bilugan 6, dahil ito pa rin ang
pivot. Ang
Lmarker ay nasa 3. Ang
Rmarker ay nasa 6. Tandaan na ginagalaw namin ang mga marker hanggang sa
Llumampas sa
R. Ilipat
Lsa susunod na numero. Dito gusto kong tuklasin ang dalawang posibilidad: 1) ang kaso kung saan ang penultimate number ay 7 at 2) ang kaso kung saan ito ay 1, hindi 7.
Kung ang penultimate number ay 1: Ilipat ang
Lmarker sa 1, dahil maaari tayong lumipat
Lbasta ang
Lang marker ay tumuturo sa isang numerong mas maliit sa
pivot. Ngunit hindi tayo makakaalis
Rsa 6, dahil maaari lamang nating ilipat ang R kung ang
Rmarker ay tumuturo sa isang numero na mas malaki kaysa sa
pivot. Hindi kami nagsasagawa ng
swap, dahil ang 1 ay mas mababa sa 6. Isulat ang kasalukuyang sitwasyon: 4 2 3 1 6. Bilugan 6 (
pivot).
Llumilipat
pivotat huminto sa paggalaw.
Rhindi gumagalaw. Hindi kami nagsasagawa ng swap. Shift
Lat
Rsa pamamagitan ng isang posisyon. Isulat ang
Rpananda sa ilalim ng 1. Ang
Lpananda ay wala sa hangganan. Dahil
Lout of bounds, wala tayong ginagawa. Ngunit, isinusulat namin muli ang 4 2 3 1, dahil ito ang aming kaliwang bahagi, na mas mababa sa
pivot(6). Piliin ang bago
pivotat simulan muli ang lahat :)
Kung ang penultimate number ay 7:Ilipat ang
Lmarker sa 7. Hindi namin maigalaw ang tamang marker, dahil nakaturo na ito sa pivot. 7 ay mas malaki kaysa sa
pivot, kaya nagsasagawa kami ng isang
swap. Isulat ang resulta: 4 2 3 6 7. Bilugan 6, dahil ito ang
pivot. Ang
Lmarker ay inilipat na ngayon sa 7, at ang
Rmarker ay inilipat sa 3. Hindi makatuwirang pag-uri-uriin ang bahagi mula
Lsa dulo, dahil mayroon lamang 1 elemento. Gayunpaman, ipinapadala namin ang bahagi mula 4 hanggang sa
Rmarker para sa pag-uuri. Pumili kami ng isang
pivotat magsimulang muli :) Sa unang tingin, maaaring mukhang kung magdagdag ka ng maraming halaga na katumbas ng
pivot, pagkatapos ay sisirain mo ang algorithm. Ngunit hindi ito ang kaso. Maaari kang mag-isip ng mga nakakalito na kumbinasyon at sa papel ay kumbinsihin ang iyong sarili na ang lahat ay tama at mamangha na ang gayong mga simpleng aksyon ay nagpapatupad ng isang maaasahang mekanismo ng pag-uuri. Ang downside lang ay hindi stable ang sorting algorithm na ito. Dahil ang isang swap ay maaaring magbago ng relatibong pagkakasunud-sunod ng magkatulad na mga elemento kung ang isa sa mga ito ay nakatagpo bago
pivotbago ang isa pang elemento ay napalitan sa bahaging nauna
pivot.
GO TO FULL VERSION