Ang pag-uuri ay isa sa pinakakaraniwan at kinakailangang operasyon sa programming. Kinakatawan nito ang pagkakasunud-sunod ng ilang hanay ng mga elemento sa isang partikular na pagkakasunud-sunod. Ang artikulong ito ay tungkol sa mga karaniwang pamamaraan para sa pag-uuri ng mga array sa Java.
Maikling tungkol sa pag-uuri
Kaya, ang pag-uuri ay ang pag-order ng isang set ng data. Sa aming kaso, arrays. Ang layunin ng pag-uuri ng mga array o iba pang istruktura ng data ay upang gawing mas madaling mahanap, manipulahin, o i-parse ang data sa koleksyon. Kailangan ng mga programmer ang pag-uuri nang madalas na ang anumang wika ng programming ay may kasamang mga built-in na pamamaraan para sa pag-uuri ng mga array, listahan, at iba pang nakaayos na istruktura ng data. Upang magamit ang mga ganitong pamamaraan, tawagan sila. Ang operasyon ay pinasimple hangga't maaari. Karaniwan, ang mga built-in na pamamaraan ay na-optimize nang husto; sa karamihan ng mga kaso, ang paggamit sa mga ito para sa iyong trabaho o mga proyekto ay isang magandang ideya. Gayunpaman, halos bawat programmer, sa panahon ng kanilang pag-aaral, ay kailangang magpatupad ng mga algorithm ng pag-uuri sa kanilang sarili. Samakatuwid, ang mga perpektong pagsasanay na ito ay nagtuturo sa iyo na maunawaan ang pinakadiwa ng programming. Bilang karagdagan, kung minsan kailangan mo ng hindi karaniwang mga paraan ng pag-uuri sa trabaho. Mayroong maraming mga algorithm ng pag-uuri. Mayroon silang mga kalakasan at kahinaan depende sa uri o laki ng mga set ng data. Kasama sa mga karaniwang algorithm sa pag-uuri ang bubble sort, selection sort, insertion sort, merge sort, at quicksort.
Built-in na paraan para sa pag-uuri ng mga array sa Java: Arrays.sort
Magsimula tayo sa pinakasimpleng. May nakapagsulat na ng paraan para sa pag-uuri ng mga array sa Java para sa amin. Ang pamamaraang ito ay nasa klase ng Arrays , mas partikular na java.util.Arrays . Naglalaman ang klase na ito ng iba't ibang pamamaraan para sa pagtatrabaho sa mga array, tulad ng pag-uuri at paghahanap. Ang Arrays.sort method ay nagbibigay ng isang maginhawang paraan upang pagbukud-bukurin ang array sa Java, kung naglalaman ang mga ito ng mga string, integer, o iba pang elemento. Mayroong ilang mga variation ng Arrays.sort method sa Java. Narito ang ilang karaniwang ginagamit na paraan ng pag-uuri mula sa klase ng Arrays :
Arrays.sort(Array) : gamitin ito upang pagbukud-bukurin ang mga arrays ng mga primitive na uri o bagay sa pataas na pagkakasunud-sunod. Ginagamit nito ang natural na pagkakasunud-sunod ng mga elemento.
Arrays.sort(Array, fromIndex, toIndex) : Ang overloaded na paraan ng pag-uuri ay nagbibigay-daan sa iyong pag-uri-uriin lamang ang isang bahagi ng Array na tinukoy ng fromIndex at toIndex na mga parameter.
Arrays.sort(Array, comparator) : ang isang ito ay para sa pag-uuri ng mga arrays ng mga bagay gamit ang custom na comparator. Tinutukoy ng comparator ang pagkakasunud-sunod ng mga elemento.
Arrays.parallelSort(Array) : Ang bersyon ng pamamaraang ito ay nag-uuri ng Array nang magkatulad, na gumagamit ng maraming mga thread para sa pinahusay na pagganap. Ito ay kapaki-pakinabang para sa pag-uuri ng malalaking array.
Arrays.parallelSort(Array, fromIndex, toIndex) : Ang overloaded na bersyon na ito ng parallelSort method ay nagbibigay-daan sa pag-uuri ng isang partikular na hanay ng mga elemento sa Array .
Pinapayagan ka nitong mabilis na ayusin ang mga elemento batay sa kanilang natural na pagkakasunud-sunod o paggamit ng isang custom na comparator. Tuklasin natin ang paraang ito na may dalawang halimbawa, ang isa ay may kinalaman sa mga string.
Halimbawa 1: Pag-uuri ng mga String
Ipagpalagay na mayroon tayong hanay ng mga string na instrumentong pangmusika: "violin", "viola", "cello", at "double bass". Magagamit natin ang Array.sort method para ayusin ang mga ito ayon sa alpabeto.
Mga Inayos na Instrumento: cello double bass viola violin
Sa program na ito, una, ini-import namin ang klase ng java.util.Arrays upang makakuha ng access sa paraan ng Array.sort . Pagkatapos ay gumawa kami ng string array na tinatawag na mga instrumento na naglalaman ng mga pangalan ng instrumentong pangmusika. Pagkatapos nito, tinatawagan namin ang Arrays.sort(instruments) . Kaya ang pamamaraang ito ay nakakakuha ng array, nag-uuri ng mga elemento sa pataas na pagkakasunud-sunod batay sa kanilang natural na pagkakasunud-sunod (alphabetical). Sa wakas, umiikot kami sa pinagsunod-sunod na Array at i-print ang bawat instrumento.
Halimbawa 2: Pag-uuri ng mga Integer
Isaalang-alang natin ang isa pang halimbawa kung saan nag-uuri tayo ng hanay ng mga integer sa pataas na pagkakasunud-sunod.
importjava.util.Arrays;publicclassIntegerSortExample{publicstaticvoidmain(String[] args){int[] numbers ={8,2,7,3,1,5};//sort an array using Arrays.sortArrays.sort(numbers);System.out.println("Sorted Numbers:");for(int number : numbers){System.out.println(number);}}}
Output:
Pinagsunod-sunod na Mga Numero: 1 2 3 5 7 8
Dito, lumikha kami ng isang integer array na tinatawag na mga numero na may ilang mga unsorted na elemento. Susunod, tinatawagan namin ang Arrays.sort(numbers) upang pagbukud-bukurin ang isang array sa pataas na pagkakasunud-sunod. Tandaan na binabago ng Array.sort method ang orihinal na array in-place. Kaya para mapanatili ang orihinal na Array , gumawa ng kopya bago pag-uri-uriin.
Halimbawa 3: pababang ayos
Paano ang tungkol sa pababang uri? Madali din ito sa Arrays.sort . Gumamit lang ng custom comparator. Narito ang isang halimbawa:
importjava.util.Arrays;importjava.util.Comparator;//Arrays.sort with custom comparator examplepublicclassDescendingSortExample{publicstaticvoidmain(String[] args){Integer[] numbers ={8,2,7,3,1,5};//sort an Array using Arrays.sortArrays.sort(numbers,Comparator.reverseOrder());System.out.println("Sorted Numbers (Descending):");for(int number : numbers){System.out.println(number);}}}
Ang output ay susunod:
Pinagsunod-sunod na Mga Numero (Pababa): 8 7 5 3 2 1
Narito mayroon kaming isang hanay ng mga integer na pinangalanang mga numero. Sa pamamagitan ng pagpasa ng Comparator.reverseOrder() bilang pangalawang argumento sa Arrays.sort method, tinutukoy namin ang isang custom na comparator na nag-uuri ng mga elemento sa pababang pagkakasunud-sunod. Ang paraan ng Comparator.reverseOrder() ay nagbabalik ng isang comparator na binabaligtad ang natural na pagkakasunud-sunod ng mga elemento. Tandaan na dito, ginagamit namin ang Integer wrapper class sa halip na ang primitive int type dahil ang Comparator.reverseOrder() method ay nangangailangan ng mga object. Kung mayroon kang isang hanay ng mga primitive na halaga ng int, kakailanganin mo ring i-convert ang mga ito sa mga bagay na Integer bago gamitin ang diskarteng ito. Gamit ang isang custom na comparator, madali mong maiayos ang array sa pababang pagkakasunud-sunod gamit ang Arrays.sort method sa Java.
Mga self-written na classical sorting algorithm sa Java
Nakita mo na ang Array na nag-uuri ng mga takdang-aralin kung nag-aaral ka ng Computer Science nang nakapag-iisa o sa unibersidad. Mayroong maraming iba't ibang mga algorithm sa pag-uuri, at ipapatupad namin ang ilan sa mga ito sa artikulong ito. Sa pangkalahatan, kung mas madaling ipatupad ang isang algorithm, hindi gaanong mahusay ito. Sinusukat ng mga programmer ang kahusayan ng mga algorithm ay sinusukat ng oras ng operasyon nito at ang memorya na ginugol sa mga mapagkukunan. Hindi iyon ang paksa ng aming artikulo, ngunit binanggit namin na ang Arrays.sort sa Java ay isang epektibong algorithm.
Bubble Sort
Magsimula tayo sa pinakasikat na algorithm sa mga mag-aaral: Bubble sort. Ito ay diretso: ang algorithm ay naghahambing ng dalawang elemento at pagkatapos ay pinapalitan ang mga ito kung sila ay nasa maling pagkakasunud-sunod, at iba pa hanggang sa katapusan ng array. Lumalabas na ang mas maliliit na elemento ay "lumulutang" hanggang sa dulo ng Array , tulad ng mga bula sa soda na lumutang sa itaas.
publicclassBubbleSort{publicstaticvoidbubbleSort(int[] myArray){int n = myArray.length;for(int i =0; i < n -1; i++){for(int j =0; j < n - i -1; j++){if(myArray[j]> myArray[j +1]){// Swap myArray[j] and myArray[j+1]int temp = myArray[j];
myArray[j]= myArray[j +1];
myArray[j +1]= temp;}}}}publicstaticvoidmain(String[] args){int[] arr ={18,28,2,7,90,45};System.out.println("Array before sorting:");for(int num : arr){System.out.print(num +" ");}bubbleSort(arr);System.out.println("\nArray after sorting:");for(int num : arr){System.out.print(num +" ");}}}
Narito ang pamamaraan ay tumatagal ng isang hanay ng mga integer bilang input. Ang panlabas na loop ay mula 0 hanggang n-1. Narito n ang laki ng array. Inihahambing ng panloob na loop ang mga katabing elemento. Kung mali ang pagkakasunud-sunod, pinapalitan sila ng pamamaraan. Ang pamamaraang ito ay paulit-ulit hanggang sa ang buong array ay naayos. Narito ang isang output ng aming programa:
Ang algorithm ng pagpili ay nag-uuri ng array sa pamamagitan ng paulit-ulit na paghahanap ng pinakamaliit na elemento mula sa hindi naayos na bahagi at paglalagay nito sa simula. Isulat natin ito sa Java:
publicclassSelectionSort{publicstaticvoidselectionSort(int[] myArray){int n = myArray.length;for(int i =0; i < n -1; i++){int minIndex = i;// Find the index of the minimum element in the unsorted part of the arrayfor(int j = i +1; j < n; j++){if(myArray[j]< myArray[minIndex]){
minIndex = j;}}// Swap the minimum element with the first element of the unsorted partint temp = myArray[minIndex];
myArray[minIndex]= myArray[i];
myArray[i]= temp;}}publicstaticvoidmain(String[] args){int[] arr ={18,28,45,2,90,7};System.out.println("Array before sorting:");for(int num : arr){System.out.print(num +" ");}selectionSort(arr);System.out.println("\nArray after sorting:");for(int num : arr){System.out.print(num +" ");}}}
Narito ang isang output ng programa:
Array bago pagbukud-bukurin: 18 28 45 2 90 7 Array pagkatapos ng pag-uuri: 2 7 18 28 45 90
Ipaliwanag natin ito nang sunud-sunod. Ang panlabas na loop ay umuulit mula sa simula ng Array hanggang sa pangalawa hanggang sa huling elemento (hanggang sa n-1). Pinipili ng loop na ito ang bawat elemento nang paisa-isa bilang panimulang punto ng hindi naayos na bahagi ng Array . Sa loob ng panlabas na loop, sinisimulan namin ang minIndex sa kasalukuyang index i , sa pag-aakalang ito ang index ng pinakamaliit na item sa unsorted na bahagi ng Array . Ang panloob na loop ay nagsisimula mula sa i+1 at umaakyat sa huling elemento ng Array . Hinahanap nito ang index ng pinakamaliit na item sa unsorted na bahagi ng Array sa pamamagitan ng paghahambing ng bawat elemento sa kasalukuyang minimum na elemento ( arr[minIndex] ). Kung makakita kami ng elementong mas maliit kaysa sa kasalukuyang minimum na elemento, ina-update namin ang minIndex sa index ng bagong minimum na elemento. Matapos makumpleto ang panloob na loop, nakita namin ang index ng pinakamababang elemento sa hindi naayos na bahagi ng Array . Pagkatapos ay pinapalitan namin ang pinakamababang elemento sa unang elemento ng hindi naayos na bahagi sa pamamagitan ng paggamit ng pansamantalang variable na temp. Ang panlabas na loop ay nagpapatuloy hanggang ang lahat ng mga elemento ay pinagbukud-bukod, unti-unting pinalawak ang pinagsunod-sunod na bahagi ng Array . Sa wakas, ang pinagsunod-sunod na Array ay naka-print sa pangunahing pamamaraan bago at pagkatapos ng pagtawag sa selectionSort na paraan.
Sumanib-uuri
Ang Merge Sort ay isang divide-and-conquer algorithm na paulit-ulit na hinahati ang Array sa mas maliliit na subarray, pinagbubukod-bukod ang mga ito, at pagkatapos ay pinagsasama-sama ang mga ito upang makakuha ng pinagsunod-sunod na array. Ang Merge Sort ay stable at malawakang ginagamit, lalo na kapag kailangan ang stability at isang garantisadong worst-case time complexity.
publicclassMergeSort{//Merge Sort arraypublicstaticvoidmergeSort(int[] myArray){if(myArray.length <=1){return;}int mid = myArray.length /2;int[] left =newint[mid];int[] right =newint[myArray.length - mid];System.arraycopy(myArray,0, left,0, mid);System.arraycopy(myArray, mid, right,0, myArray.length - mid);mergeSort(left);mergeSort(right);merge(myArray, left, right);}publicstaticvoidmerge(int[] arr,int[] left,int[] right){int i =0;// index for left subarrayint j =0;// index for right subarrayint k =0;// index for merged arraywhile(i < left.length && j < right.length){if(left[i]<= right[j]){
arr[k++]= left[i++];}else{
arr[k++]= right[j++];}}while(i < left.length){
arr[k++]= left[i++];}while(j < right.length){
arr[k++]= right[j++];}}publicstaticvoidmain(String[] args){int[] arr ={18,2,28,7,90,45};System.out.println("Array before sorting:");for(int num : arr){System.out.print(num +" ");}mergeSort(arr);System.out.println("\nArray after sorting:");for(int num : arr){System.out.print(num +" ");}}}
Ang output dito ay:
Array bago pag-uri-uriin: 18 2 28 7 90 45 Array pagkatapos ng pag-uuri: 2 7 18 28 45 90
Ipaliwanag natin nang mas tumpak kung paano ito gumagana. Hinahati ng algorithm ang Array sa dalawang bahagi nang recursively hanggang sa maabot ang base case (kapag ang Array ay may isa o zero na elemento). Pagkatapos ay pinagsasama nito ang pinagsunod-sunod na mga halves gamit ang paraan ng pagsasama. Ang paraan ng pagsasama ay tumatagal ng tatlong array bilang input: ang orihinal na Array at ang kaliwa at kanang subarray (kaliwa at kanan). Inihahambing nito ang mga elemento mula sa kaliwa at kanang subarray at pinagsasama ang mga ito sa orihinal na Array sa pinagsunod-sunod na pagkakasunud-sunod.
Pag-uuri ng pagpapasok
Gumagana ang Insertion Sort sa pamamagitan ng paulit-ulit na pagpasok ng elemento mula sa hindi naayos na bahagi sa tamang posisyon nito sa pinagsunod-sunod na bahagi. Mahusay itong gumaganap para sa maliliit na set ng data o halos pinagsunod-sunod na data.
publicclassInsertionSort{publicstaticvoidinsertionSort(int[] myArray){int n = myArray.length;for(int i =1; i < n; i++){int key = myArray[i];int j = i -1;while(j >=0&& myArray[j]> key){
myArray[j +1]= myArray[j];
j--;}
myArray[j +1]= key;}}publicstaticvoidmain(String[] args){int[] arr ={18,90,7,28,45,2};System.out.println("Array before sorting:");for(int num : arr){System.out.print(num +" ");}insertionSort(arr);System.out.println("\nArray after sorting:");for(int num : arr){System.out.print(num +" ");}}}
Ang output ng programa ay tulad ng dati:
Array bago pag-uri-uriin: 18 90 7 28 45 2 Array pagkatapos ng pag-uuri: 2 7 18 28 45 90
Dito ipinapatupad ng insertionSort method ang Insertion Sort algorithm. Ito ay umuulit sa pamamagitan ng Array at isinasaalang-alang ang bawat elemento bilang isang susi. Inihahambing nito ang susi sa mga elementong nauna rito at iniuuna ang mga ito ng isang posisyon kung mas malaki ang mga ito, na epektibong inililipat ang mga elemento upang bigyang puwang ang susi sa tamang posisyon.
Ang panlabas na loop ay umuulit mula sa pangalawang elemento ( i = 1 ) hanggang sa huling elemento ng Array. Ang panloob na loop ay nagsisimula mula sa kasalukuyang elemento ( arr[i] ) at paatras ( j = i - 1 ) hanggang sa mahanap nito ang tamang posisyon para sa susi o umabot sa simula ng Array . Sa loob ng inner loop, kung ang isang elemento ( arr[j] ) ay mas malaki kaysa sa susi, inililipat ito ng isang posisyon sa unahan ( arr[j + 1] = arr[j] ) upang bigyang puwang ang susi. Nagpapatuloy ang prosesong ito hanggang sa matagpuan ang tamang posisyon para sa susi. Matapos makumpleto ang panloob na loop, ang susi ay inilalagay sa tamang posisyon ( arr[j + 1] = key ). Sa pangunahing pamamaraan, ang isang halimbawang array ay nilikha at nai-print bago at pagkatapos ng pag-uuri gamit ang insertionSort method.
Mabilis na pag-uuri
Ang Quick Sort ay isang divide-and-conquer algorithm na pumipili ng elemento ng pivot at hinahati ang Array sa paligid ng pivot. Bilang isang panuntunan, ang Mabilis na Pag-uuri ay mas mabilis kaysa sa Pagsamahin ang Pag-uuri para sa maliliit at katamtamang laki ng mga set ng data dahil sa mababang mga salik nito.
publicclassQuickSort{publicstaticvoidquickSort(int[] myArray,int low,int high){if(low < high){int pivotIndex =partition(myArray, low, high);quickSort(myArray, low, pivotIndex -1);quickSort(myArray, pivotIndex +1, high);}}publicstaticintpartition(int[] arr,int low,int high){int pivot = arr[high];int i = low -1;for(int j = low; j < high; j++){if(arr[j]<= pivot){
i++;swap(arr, i, j);}}swap(arr, i +1, high);return i +1;}publicstaticvoidswap(int[] arr,int i,int j){int temp = arr[i];
arr[i]= arr[j];
arr[j]= temp;}publicstaticvoidmain(String[] args){int[] arr ={18,28,2,90,7,45};System.out.println("Array before sorting:");for(int num : arr){System.out.print(num +" ");}quickSort(arr,0, arr.length -1);System.out.println("\nArray after sorting:");for(int num : arr){System.out.print(num +" ");}}}
Kaya narito mayroon kaming tatlong paraan upang ipatupad ang mabilisang pag-uuri. Ang quickSort method ay tumatagal ng tatlong parameter: ang Array na pagbukud-bukurin, ang mababang index ng subarray, at ang mataas na index ng subarray. Sa una, sinusuri nito kung ang subarray ay may higit sa isang elemento. Kung gayon, pipili ito ng pivot gamit ang partition method, recursively sorting the subarray before the pivot, and recursively sorts the subarray after the pivot. Pinipili ng paraan ng partition ang pivot bilang huling elemento ng subarray ( arr[high] ). Itinatakda nito ang partition index (i) sa mababang index minus 1. Ito ay umuulit mula sa mababang index hanggang sa mataas na index - 1 at sinusuri kung ang bawat elemento ay mas mababa o katumbas ng pivot. Kung gayon, pinapalitan nito ang elemento ng elemento sa index ng partition (i) at dinadagdagan ang index ng partition. Sa wakas, pinapalitan nito ang elemento ng pivot sa elemento sa index ng partition + 1 at ibinabalik ang index ng partition. Pinipili ng paraan ng partition ang pivot bilang huling elemento ng subarray ( arr[high] ). Itinatakda nito ang partition index (i) sa mababang index minus 1. Pagkatapos ay umuulit ito mula sa mababang index hanggang sa mataas na index - 1 at sinusuri kung ang bawat item ay mas maliit o katumbas ng pivot. Kung gayon, pinapalitan nito ang elemento ng elemento sa index ng partition (i) at dinadagdagan ang index ng partition. Sa wakas, pinapalitan nito ang elemento ng pivot sa elemento sa index ng partition + 1 at ibinabalik ang index ng partition. Ang swap method ay isang utility method na ginagamit upang magpalit ng dalawang elemento sa Array . Sa pangunahing pamamaraan, ang isang halimbawang array ay nilikha at nai-print bago at pagkatapos ng pag-uuri gamit ang quickSort na paraan.
Mga konklusyon
Mula sa artikulong ito nalaman mo kung paano pag-uri-uriin ang isang array sa wikang Java. Maaari kang gumamit ng built-in na paraan ng Arrays.sort o magsulat ng sarili mong mga pagpapatupad ng mga sikat na paraan ng pag-uuri gaya ng bubble sort, merge sort at iba pa. Maaari mo ring subukang salakayin ang iyong sariling paraan ng pag-uuri. Depende ito sa iyong gawain. Kung kailangan mong lutasin ang isang problema sa pag-uuri nang mabilis, gumamit lamang ng isang paunang nakasulat na paraan. Kung natututo ka ng programming at susubukan mong maging mas mahusay dito, talagang magandang ideya na magsulat ng ilang paraan ng pag-uuri nang mag-isa.
