Ang pag-uuri ng mga array ay isa sa mga pinakakaraniwang operasyon na dapat malaman ng isang nagsisimula sa Java kung paano gawin. Bagama't ang mga array ay hindi palaging ang pinaka-maginhawang paraan upang ayusin ang data at ito ay kadalasang nalalapat sa maliliit na numero, ang konsepto sa likod ng pag-uuri ng array ay may maraming mga application sa kumplikadong software at data science. Sa post na ito, titingnan natin nang mas malapit kung ano ang insertion sort. Nagsama kami ng ilang halimbawa at mga problema sa pagsasanay upang matulungan kang ganap na maunawaan ang konseptong ito.
Ano ang Insertion Sort?
Karaniwan, ang insertion sort ay isang algorithm na ginagamit ng mga developer upang ayusin ang mga string ng maliliit na numero. Hinahati nito ang lahat ng mga halaga sa dalawang stack - isang pinagsunod-sunod at isang hindi pinagsunod-sunod. Isa-isa, ang mga numero sa "unsorted" stack ay pinipili at inilalagay sa tamang pagkakasunod-sunod. Tingnan natin ang input at ang output ng insertion sort:
Input: isang array A na may mga unsorted na numeric na elemento: A[0,1, n, n-2...].
Output: isang array na naglalaman ng parehong mga numero ngunit ganap na pinagsunod-sunod. Ang isang ito ay karaniwang tinutukoy bilang B: B[0]B[1]...B[n-1].
Mayroong ilang mga paraan upang gamitin ang insertion sorting - narito ang pinakasikat:
Pag-uuri ng numero (tumataas na pagkakasunud-sunod): [1, 2, 3, 4, 5]
Tandaan: kung mayroon kang isang walang laman na array o isang singleton, ang mga ito ay itinuturing na pinagsunod-sunod bilang default.
Pag-unawa sa Teorya ng Insertion Sort
Bago i-explore ang code sa likod ng insertion sort, hatiin natin ang algorithm gamit ang hindi teknikal na wika. Dahil ipapakita namin ang code para sa pag-uuri sa pataas na pagkakasunud-sunod, makatuwirang ipaliwanag ang algorithm nang sunud-sunod sa post na ito. Hakbang 1. Ang pag-ulit sa pagitan arr[1]at arr[n]kung saan nang isang numerical na halaga ay karaniwang mas mababa sa 10. Hakbang 2. Ihambing ang elementong pinili mo (kilala bilang ang key) sa nakaraang numero sa pagkakasunud-sunod gamit ang sort()pamamaraan. Hakbang 3. Kung ang lahat ng mga elemento ay mas maliit kaysa sa kanilang mga kahalili, ulitin ang paghahambing hanggang sa makakita ka ng mas malaking halaga. Hakbang 4. Magpalit ng mas malaking halaga sa isang posisyon na lampas sa mas maliit upang lumikha ng nakaayos na pagkakasunud-sunod. Hakbang 5. Ulitin ang proseso hanggang sa makakuha ka ng pinagsunod-sunod na string ng mga character
Pag-uuri ng mga primitive na array
Dahil ang algorithm ay isa sa mga pinakasimpleng pagpapatakbo ng Java, kahit na ang mga kumpletong nagsisimula ay hindi dapat magkaroon ng maraming problema sa pagpapatupad nito. Narito ang isang hakbang-hakbang na gabay sa pag-uuri ng isang array
1. Magdeklara ng array para sa pag-uuri
Upang magsimula sa, gumawa tayo ng isang string ng mga halaga na ipapakita natin sa ibang pagkakataon gamit ang Java. Para gumamit ng insertion sort, kailangan mong gumawa ng array. Para diyan, gamitinint[]
int[] arrayA = {10, 14, 20, 30};
2. Gumamit ng sort_arr upang ipatupad ang algorithm
Ang sort_arr method ay isa sa mga pinakakaraniwang paraan para ipatupad ang insertion sort. Sa pagsasagawa, ganito ang hitsura:
for(int i=0; i< sort_arr.length; ++i){
int j = i;
3. Lumikha ng isang loop at isang iterator
Sa pamamagitan ng paggamit ng loop sa insertion sort algorithm, hindi kailangang ulitin ng mga developer ang logic para sa bawat elemento. Kahit na ang paglikha ng mga loop ay tila kumplikado, ito ay medyo simple - narito ang isang halimbawa:
for(int i=0; i< sort_arr.length; ++i){
Ngayon na mayroon kang isang gumaganang loop, oras na upang lumikha ng isang iterator na mag-uuri ng lahat ng mga elemento sa nais na pagkakasunud-sunod. Mula ngayon, tatawagin natin ang iterator bilang " j".
int j = i;
4. Paglikha ng "while loop"
Pagdating sa insertion sort, ang "while" loop ay mahalaga para sa isang bago, pinagsunod-sunod na array. Para i-set up ito para sa isang pataas na pagkakasunod-sunod na insertion sort, kailangang sumunod ang isang developer sa dalawang kundisyon:
Ang halagang itinalaga sa j ay dapat na mas malaki sa 0
Ang halagang itinalaga ay j-1kailangang mas malaki kaysa sa jindex
Sa sandaling totoo ang parehong kundisyon sa while loop, ang key value ng array ay magiging katumbas ng jindex.
5. Pag-uuri ng array
Pagkatapos mong i-set up ang while loop, ang jat j-1value ay papalitan hanggang sa mabigo ang isa o pareho sa mga kundisyon sa while loop. Katulad nito, uulitin ang pag-uuri para sa bawat halaga sa for loop hanggang sa mabigo rin ang mga kundisyon ng for-loop. Narito kung paano gumagana ang proseso ng insertion sort sa pagsasanay:
Bagama't mahalaga ang pag-unawa sa matematika sa likod ng insertion sort, pagdating sa real-life software development, mas marami kang pag-uuri-uriin ang ArrayLists kaysa sa mga sequence sa primitive arrays. Narito ang isang hakbang-hakbang na gabay sa pag-uuri ng isang ArrayList:
Gumawa ng bagong Elementklase para sa mga item na kabilang sa koleksyon.
public class Element {
private int id;
public Element(int id) {
this.id = id;
}
Sa loob ng isang koleksyon, mayroong isang compareTo()paraan - gagamitin namin ito upang ihambing ang mga id ng dalawang elemento.
public int compareTo(Element element) {
int res = 0;
if (this.id < element.getId()) {
res = -1;
}
if (this.id > element.getId()) {
res = 1;
}
return res;
}
}
Ilapat ang algorithm at lumikha ng ilang mga loop upang pagbukud-bukurin ang mga bagay ArrayListsa halip na ihambing ang mga ito.
public static void insertionSortArrayList(List<element> list) {
for (int j = 1; j < list.size(); j++) {
Element current = list.get(j);
int i = j-1;
while ((i > -1) && ((list.get(i).compareTo(current)) == 1)) {
list.set(i+1, list.get(i));
i--;
}
list.set(i+1, current);
}
}
Maaari kang magdagdag ng higit pang mga elemento sa ArrayListpati na rin, tulad ng ipinapakita sa ibaba:
List<element> list = new ArrayList<>();
// Create elements w/ IDs 0-24
for (int i = 0; i < 25; i++) {
list.add(new Element(i));
}
// To use insertion sort, shuffle the values
Collections.shuffle(list);
Ngayon ay oras na para sa pag-uuri:
// This helps print values before sorting
list.forEach(e -> System.out.print(e.getId() + ", "));
// Sort the list
insertionSortArrayList(list);
System.out.println();
// Display a sorted array
list.forEach(e -> System.out.print(e.getId() + ", "));
Ngayon, ihambing natin ang input at output para matiyak na wala tayong pagkakamali. Narito ang paghahambing ng string na ginamit namin bilang isang halimbawa.
Mga Problema sa Pagsasanay sa Pag-uuri ng Insertion
Ngayong alam mo na ang algorithm sa pag-uuri na ito, oras na upang subukan ang iyong teoretikal at praktikal na mga kasanayan. Theory quiz #1 Bibigyan ka ng array [1, 4, 6, 8] at nagdaragdag ka ng bagong elemento n = 7 dito. Ano ang bilang ng mga paghahambing na kailangan mong gawin upang makakuha ng pinagsunod-sunod na pagkakasunud-sunod ng mga numero? Ipahiwatig ang huling halaga ng index n sa array. Pagsusulit sa teorya #2 Sa isang panayam sa trabaho, hihilingin sa iyo ng pinuno ng pangkat na patunayan na ang paglalagay ng pag-uuri ay isang hindi mahusay na pamamaraan. Dahil sa numeral string ng [0, 3, 6, 8, 9], ano ang dapat na pagkakasunud-sunod ng iyong input sequence para ma-maximize ang oras ng pagpapatakbo na kinakailangan para sa pag-uuri? Problema sa pagsasanay Pagbukud-bukurin ang hanay ng [0, 1, 4, 5, 2, 3, 7, 9, 8] sa pataas nitong pagkakasunud-sunod gamit ang insertion sort para sa Java.
Konklusyon
Ang pinakamalaking hamon sa pag-unawa sa insertion sort ay ang pag-unawa kung paano gumagana ang proseso. Kapag nasanay ka na, ang paggawa ng template sa code ay isang piraso ng cake. Hangga't nagsasanay ka at muling binibisita ang mga nauugnay na problema sa pagsasanay sa paglipas ng panahon, mabilis mong mapapabuti ang iyong bilis ng pag-uuri ng pagpapasok.
Tingnan natin ang input at ang output ng insertion sort:
GO TO FULL VERSION