Sut mae chwilio deuaidd a threfnu cyduniad yn gweithio ar gyfer TGAU?

Os ydych chi'n adolygu algorithmau ar gyfer TGAU Gwyddoniaeth Gyfrifiadurol, mae pedwar enw'n dod i fyny dro ar ôl tro: chwilio llinol, chwilio deuaidd, trefnu swigod, a threfnu cyduniad. Mae byrddau arholiad yn caru gofyn i chi ddilyn y rhain â llaw, nodi'r rhedeg-amser, neu lenwi llinellau cod ffug coll. Dyma beth sy'n wirioneddol bwysig ar gyfer yr arholiad ac ymhellach.

Chwilio llinol: y llinell sylfaen

Mae chwilio llinol yn gwirio pob eitem mewn rhestr, un ar y tro, nes iddo ddod o hyd i'r targed neu gyrraedd y diwedd. Dyna i gyd.

for i = 0 to length(list) - 1
    if list[i] == target then
        return i
return -1

Yn y trydydd achos, rydych chi'n gwirio pob elfen sengl, felly mae'n O(n). Yn y gorau, mae'r targed yn gyntaf, felly O(1). Mae arholwyr yn hoffi gofyn i chi nodi'r ddau. Mae chwilio llinol yn gweithio ar ddata heb ei datrys, sef ei un fantais wirioneddol dros chwilio deuaidd.

Chwilio deuaidd: yr un sy'n twyllo pobl

Mae chwilio deuaidd yn gweithio dim ond ar restr datrys. Rydych chi'n cymharu'r targed â'r eitem ganol. Os yw'r targed yn llai, rydych chi'n taflu'r hanner uchaf; os yn fwy, taflu'r hanner isaf. Ailadrodd nes i chi ddod o hyd iddo neu redeg allan o eitemau.

low = 0
high = length(list) - 1
while low <= high
    mid = (low + high) / 2
    if list[mid] == target then
        return mid
    else if list[mid] < target then
        low = mid + 1
    else
        high = mid - 1
return -1

Mae hyn yn O(log n), a dyna pam mae'n llawer cyflymach ar setiau data mawr. Chwilio rhestr datrys o filiwn eitem a gall chwilio llinol angen hyd at filiwn o gymhariaethau; mae chwilio deuaidd angen tua 20. Mae arholwyr yn rhoi i chi rhestr gyffredin o, dweud, 16 rhif ac yn gofyn i chi ddilyn pa indecs sy'n cael eu gwirio — ymarferwch hyn â llaw gyda phensel a phapur, dim ond yn eich pen.

Trefnu swigod: syml ond araf

Mae trefnu swigod yn cerdded trwy'r rhestr dro ar ôl tro, gan newid eitemau cyfagos os ydynt yn nhrefn anghywir. Mae pob pas llawn yn gwthio'r eitem heb ei datrys fwyaf i'w lleoliad cywir ar y diwedd.

for i = 0 to length(list) - 1
    for j = 0 to length(list) - 2 - i
        if list[j] > list[j+1] then
            swap(list[j], list[j+1])

Yr achos gwaethaf yw O(n²) — ar gyfer pob elfen, efallai y byddwch chi'n sganio bron yr holl restr eto. Ychydig iawn yn defnyddio mewn meddalwedd wirioneddol oherwydd ei fod yn araf ar ddata mawr, ond mae arholwyr yn ei hoffi oherwydd bod dilyn trywydd â llaw yn rheolaidd ac mae'n dangos yn glir y syniad o basiau ailadroddol a newidiadau. Gwybod sut i gyfri nifer y cymhariaethau a'r newidiadau mewn tabl olrhain; dyna eitem cynllun marciau cyffredin.

Trefnu cyduniad: rhannu a goresgyn

Mae trefnu cyduniad yn rhannu'r rhestr yn ei hanner dro ar ôl tro nes bod gan bob is-restr un eitem, yna'n cyd-uno'r is-restrau hynny yn ôl at ei gilydd mewn trefn datrys.

function mergeSort(list)
    if length(list) <= 1 then
        return list
    mid = length(list) / 2
    left = mergeSort(list[0:mid])
    right = mergeSort(list[mid:])
    return merge(left, right)

Mae'r cam cyd-uno yn cymharu eitemau blaen pob hanner ac yn dewis yr un llai, gan ailadrodd nes bod y ddau hanner wedi'u defnyddio. Mae hyn yn rhoi O(n log n), sy'n curo trefnu swigod yn esmwyth ar unrhyw beth ond rhestrau bychain. Mae cwestiynau TGAU weithiau'n gofyn i chi dynnu'r diagram rhannu-a-chyd-uno — siap coeden yn dangos y rhestr yn rhannu i lawr ac yna'n ail-uno. Ymarferwch dynnu hyn ar gyfer rhestr o 8 rhif fel y byddwch chi'n gyflym arno dan amodau arholiad.

Beth mae arholwyr yn gwirioneddol ei brofi

Mae mwyafrif cynlluniau marciau am i chi allu:

• Dilyn algorithm cam wrth gam ac ysgrifennu i lawr cyflwr y rhestr ar ôl pob pas neu gymhariaeth.
• Nodi cymhlethdod amser yn nhermau Big O, neu o leiaf ei ddisgrifio mewn geiriau (