Arrays

I ældre programmeringssprog blev arraybegrebet ofte implementeret forskelligt altefter hvormange dimensioner arrays skulle have.
fx i Pascal:
var
    Olsen : array[1..9,3..8] of integer;

Det går man mere og mere bort fra, og laver istedet flere dimensioner ved at lave et array hvor cellerne i det array igen indeholder arrays. Forskellen er nogenlunde ens, hvor man i Pascal skrev
    Olsen[3,6];
skriver man nu
    Olsen[3][6];

den nye måde er lidt dyrere i ram (som er billigt idag) og giver noget større frihed. de arrays der ligger 'på tværs behøver fx ikke at være lige lange, sådan som de skulle være i Pascal.

Mht sorteringsmetoder, tænker du så på sådan noget som bubblesort, quicksort, heapsort osv? Det er næsten nemmere at låne en grundlæggende datalogibog om algoritmer og så lige læse et enkelt kapitel om sortering...

Der findes ikke nogen sorteringsmetode der er "bedst", det afhænger af en bunke andre faktorer.
  Hvor store datamængeder der skal sorteres.
  Om data ankommer i separate blokke eller om dataelementer ankommer enkeltvis og skal passes ind i en eksisterende sortering.
  Hvad der skal gøres med data bagefter.
...

Jeg mener Heap Sort og Merge Sort er de hurtigste sortering metoder til arrays.

Her er informationer om sortering:

Bubble Sort:
Insertion Sort:
Selection Sort:
http://www.cs.hope.edu/csci120/topics/sorting.html

en masse demoer af sortering metoder, nogle med kode:
http://www.scs.carleton.ca/~morin/misc/sortalg/
http://math.baruch.cuny.edu/~bshaw/index-8.html
http://www.inf.ethz.ch/~staerk/algorithms/SortAnimation.html

flere sortings metoder, listet efter hvad der skal sorteres:
http://www-lsi.upc.es/~rbaeza/handbook/sort_a.html

Heap Sort er garanteret n log n

Det er den ja, og mergesort kan gøres noget nær lineær med N. så til rigtig masser af data er den suveræn. til 10-20 små elementer er bubbelsort bedre selvom den er N*N.

Det hurtigste er at bruge en hashtabel, hvis der er mulighed for det.

Insertion sort er klart det bedste når noget løbende skal holdes sorteret når der kommer et eller få elementer ind.

Merge sort er god når en stor mængde af uordnet data skal sorteres, men er quick sort ikke statistisk set bedre end merge sort?

For at nævne arrays, så var de engang næsten den eneste måde der blev anvendt til at lagre "store" mængder data af samme type inde i ens program.

Med OOP er arrays i dag, næsten afløst af container klasser. Specielt multidimensionelle arrays er sjældne i OO programmer.

Er bubblesort ikke bare et godt akademisk eksempel på, hvordan man ikke skal sortere? (Specielt brugt fordi metoden er så logisk og oplagt!)

Tak for alle jeres svar indtil nu ... det har sat det lidt mere på plads for mig (med hensyn til sortering)

Men jeg er også stødt ind i udtryk som 2-Dimensional, 3-Dimensional og 4-Dimensional .... Hvad er forskellen på dem ?

Tag nogen terninger (sånd nogen man spiller ludo med) og læg dem i en række.

T T T T T T T T T T

det er så et een dimensionalt array der indexeres på een led:
T T T T T T T T T T
0 1 2 3 4 5 6 7 8 9 

saml terningene sammen og løg den på dordet igen, men denne gang så de danner en firkant. det giver et to-dimensionalt array:

T T T 0   
T T T 1
T T T 2
0 1 2

Og hvis du lægger nogen lag af ligesådanne firkanter ovenpå kan du lavet en 'kasse' af terninger der er 3-dimensionalt array.

i det en-dimensionale array skal du kun bruge een indexværdi for at udpege en bestemt terning. [5] for "den femte henad"

i det 2-dimentsionale array skal der bruges 2 indexer  [1,1] "nr 1 henad og nr 1 nedad"

en dimension, indexeres med en værdi, eks [3] = r
0 1 2 3 4 5 6 = element nr
z x f r e d s = data

to dimensioner, indexeres med to værdier, eks [1][5] = c
0 1 2 3 4 5
0q w e r t y
1q r f d s c
2v . . .
3. .
4
5

tre dimensioner indexeres med tre værdier (svært at tegne en 3D cube med elementer) :-)

id det 3-dimensionale skal der bruges 3. [2,1,2] for "nr 2 henad, nr 1 nedad, nr 2 lag"

efter 3 dimensioner er der inge bekvem måde at illustrer det, men ideen kan nemt fortsættes til 4, 5, ... dimensionelle arrays

Undskyld jeg blander mig... men jeg har svært ved at forstå arrays. Hvad kan det kort fortalt bruges til?

at skabe en datastruktur der i en vis grad saver til virkeligheden.

jeg bor fx i en større etageejendom, i opgang 2, på 3die sal i lejlighed 2.

så hele den bologblok jeg bor i kan ret nemt betragtes som et 3-dimensionalt array. hvo man med indexværdiene: opgang, etage og lejlighedsnr kan udpege min eller enhver anden lejlighed i den blok.

Computerspil har typisk et spilområde der er et 2-dimensionalt array. hvis ikke mine projektiler når position x henad og y opad på samme tidspunkt som der er en space-invader i den position vil space-invaderen fortsætte med at dale nedad og hvis den kommer helt ned til position [x,0] dør jeg.

mvh JakobA

jakoba >> Mange tak for illustrationen med terningerne :-) Dén satte det med dimensionale arrays på plads for mig !!!

chries >> Også tak til dig :-)

codemon >> Hvad er en hashtabel ?

tipsen >> Hvilken grundlæggende datalogibog om algoritmer kan du anbefalde ?

Jeg er meget glad for alle de svar jeg har fået og håber at I vil hjælpe mig med at få svar på ovenstående spørgsmål. Jeg giver også gerne flere point ...

torben: Har ikke det store overblik over datalogibøger, men har selv haft "Kingston: Algorithms and Data Structures" - ved ikke om den er specielt god...

Men hvis du vil overveje at købe sådan en, synes jeg næsten du skal poste et særskilt spørgsmål - for der vil sikkert være mange meninger og gode forslag! Du skal dog være opmærksom på, at det ikke nødvendigvis er et konkret programmeringssprog du lærer, men nok mere generel programmeringsteknik og tænkemåde.

Har lige kigget lidt nærmere på de links i kom med til information om sortering af data.

Men jeg forstår dem ikke helt

Jeg skal lave en sortering af et 2-dimensionalt array. Jeg skal have mulighed for at sortere asc og desc. Indholdet af arrays'ne kan variere mellem 1-100 (normalt), men det kan også dreje sig om 10000 el. flere.

Så det skal være en metode der er rimelig hurtig til få poster, men som ikke går helt død ved mange data ...

Hvis du kender eller alligevle skal have lært Pascal er der Nicholas Wirths "Algorithms + Data Structures = Programs". Wirth er ret vild med ideen om at gode datastrukturer er ligeså vigtige som gode algoritmer.
http://www.amazon.com/exec/obidos/search-handle-form/103-4575615-3599862

Knuths "Fundamental Algorithms" (bind 1 til 3) er super, men ret svær at læse nutildags for han baserer den på et hjemmelavet assemblersprog.
http://www.amazon.com/exec/obidos/ASIN/0201896834/qid=1021654671/sr=8-1/ref=sr_8_1/103-4575615-3599862

mvh JakobA

Først og fremmest kræver sortering at du har en klippefast og fuldstændigt specificeret definition af hvad "større end" betyder.
eg:
ved sortering af navne:
  "Jack Vance"  er større end  "Poul Anderson"
fordi man sammenligner på efternavnet først.

Og ved sortering ad et 2-dimesionalt array kan det endog være der skal være 2 helt forskellige "større end" definitioner. Hvis der på den ene led skal sorteres elementer, og på den anden led skal sorteres hele rækker.

Vi ved stadig alt for lidt til at give et fornuftigt råd.

en hashtabel er en måde at lagre på hvor indeks nummeret beregnes ud fra indholdet, det kaldes en hashfunktion.
Et simpel eksempel er en hashtabel til personnavne, der kan udregnes et indeks nummer ved at tage ASCII værdien af bogstaverne og lægge dem sammen. Når der så skal "søges" efter en person, udregnes indeks nummeret igen og navnet findes første gang. Dette medfører at der kun skal søges én gang for at finde et vilkårligt element. Virkeligheden er selvfølgelig ikke så perfekt, der kan opstå kollisioner hvis to navne giver samme indeks nummer.

Et multidimensionelt array kan anskuliggøres ved et lille tankeeksperiment.

Du skal indeksere nogle personer et eller andet sted i verden.

Der er lande
i lande er der kommuner
i kommuner er der byer
i byer er der huse
i huse er der personer.

indeks 1 i lande viser et land, derunder skal indekseres til kommunen, derunder til byen osv. (5-Dimensionelt array)
fx array
landnr = 2, kommune i det land = 7, by i den kommune = 23, hus i den kommune = 9, person i det hus = 1.
verdensperson[2][7][23][9][1]

Men som sagt vil dette ikke forekomme i moderne objekt orienteret programmering.

// Vi ved stadig alt for lidt til at give et fornuftigt råd.

Jamen så må jeg jo prøve at forklare mig lidt bedre ...

Jeg er ved at lave en webmail (i ASP) hvor jeg viser en liste over meddelser i indbakken (via jMail). For at kunne sortere denne liste efter afsender, emne, størrelse og data/tid fik jeg den idé at man kunne stoppe dataene ind i et array og derefter trække dem ud sorteret igen ...

Der skal altså kun være mulighed for at sortere på et af felterne (f.eks. størrelse) og dette skal kunne gøres både stigende og faldende ...

Håber det var information nok ...

det tror jeg.  Hvert array på 'den anden led' er en email, og der skal så byttes om på de arrays så dine emails er sorteret.

Desværre ved jeg ikke nok om ASP til at sige hvordan du skal gøre det.

Nu kommer jeg i tvivl ???

Jeg har læst på en hjemmeside at den første dimension i et 2-dimensionelt svarer til kolonerne og at den anden dimension i et array er rækken.

Det vil altså hvis jeg har forstået det rigtigt sige at

Array[første dimension/kolone,anden dimension/række]

Men er det altid sådan ??? Jeg har fundet en anden kode (til QuickSort) som lige laver det omvendt ... (Array[række,kolone]).

Det er vel ligemeget ? Hva' er bedst at bruge ?

Mht. point ... så skal jeg nok snart gi jer nogen :-) Har bare ikke fået løst mit problem endnu.

Da ingen gider svare lukker jeg hermed spørgsmålet...

Hvis I ser dette må I meget gerne kigge på dette spg.:

http://www.eksperten.dk/spm/225721