16. december 1999 - 13:37Der er
21 kommentarer og 1 løsning
Sortering
Jeg vil også gerne have hjælp til en sorterings funktion til tidligere omtalte program, Det må bare ikke være Bubblesort. 100 point, kan det gøre det??
Som tidligere skrevet til dig, findes funktionen qsort() i de fleste compilere. Den tager en tabel som parameter, længden på hvert element i tabellen og en funktion som kan returnere -1, 0 eller 1 alt efter et givent element i tabellen er mindre end, ens eller større end et andet element.
En ikke rekursiv implementering af qsort-algoritmen har du herunder. Algoritmen viser løbende "status" via nogle externe variable i dit hovedmodul, deklareret under overskriften 'External variables' - dem kan du blot fjerne hvis du ikke gider se på det.
/***************************************************************************/ /* This module implements a BSORT optimized QSORT algorithm WITHOUT recur- */ /* sive calls. */ /***************************************************************************/
#ifdef __WIN32__ #define far #define huge #endif
#include <conio.h>
/* [Extern variables] */ const int maxStsIdx = 4; extern long nbrSwaps, nbrCompare; extern char stsChar[maxStsIdx], sts; extern int stsIdx;
/**********************/ void find_pivot(void) /**********************/ { /* Set initial boundaries and find pivot value/location. */ pivotLeft = pivotMiddle = pivotMin; ptrLeft = sortTbl+(sortElmLen*pivotLeft); pivotRight = pivotMax; ptrRight = sortTbl+(sortElmLen*pivotRight); if ((tempLong = (pivotMax-pivotMin)/2) > 2) { /* More than 5 elements - select middle VALUE of */ /* left, center and right as pivot. */ pivotMiddle += tempLong; ptrMiddle = sortTbl+(sortElmLen*pivotMiddle); if (sortFcmp(ptrLeft, ptrRight) > 0) memswapLR(); if (sortFcmp(ptrMiddle, ptrRight) > 0) memswapMR(); if (sortFcmp(ptrLeft, ptrMiddle) > 0) memswapLM(); } else ptrMiddle = sortTbl+((pivotMiddle += tempLong)*sortElmLen);
/* Loop until left and right side ordered in relation */ /* to the pivot. */ while (pivotLeft < pivotRight) { while (pivotLeft < pivotMax && sortFcmp(ptrLeft, ptrMiddle) <= 0) ptrLeft = sortTbl+((++pivotLeft)*sortElmLen); while (sortFcmp(ptrRight, ptrMiddle) > 0) ptrRight = sortTbl+((--pivotRight)*sortElmLen); if (pivotLeft < pivotRight) { /* left belongs on right side of pivot, right on the left, so */ /* swap the two elements. */ memswapLR();
/* Left always ends past pivot due to nature of above check. */ /* However right might actually have pointed to same location */ /* as pivot, and pivot thus have been moved to left. Correct */ /* middle and thus pivot in that case. */ if (pivotRight == pivotMiddle) { pivotMiddle = pivotLeft; ptrMiddle = ptrLeft; }; }; }; /* Until left has passed right. */ nbrCompare += pivotMax-pivotMin+1;
/* Right now at location where pivot should be, and left at next */ /* location. Nature of above if means that pivot and right have */ /* not been swapped yet, so do that. */ memswapMR();
/* Loop as long as there's still stacked sorts. */ while (stackTop > 0) { /* Pop the stacked sort boundaries. */ left = stack[--stackTop].min; right = stack[stackTop].max; if (stackTop > sortMaxDepth) sortMaxDepth = stackTop;
/* Loop while there's still unsorted elements */ /* on either side of the pivot element. */ while (left < right) { /* Find pivot element - ordering left & right side. */ pivotMin = left; pivotMax = right; find_pivot(); middle = pivotRight;
/* Stack largest unsorted side. (As more likely to require */ /* additional stacking.) */ if ((middle-left) > (right - middle)) { /* Left side largest - stack it. */ stack[stackTop].min = left; stack[stackTop++].max = middle - 1;
/* Continue current loop with right side. */ left = middle + 1; } else { /* Right side largest or same as left. */ stack[stackTop].min = middle + 1; stack[stackTop++].max = right;
/* Continue current loop with left side. */ right = middle - 1; }; }; /* While unsorted on either side of the pivot. */ }; /* While still stacked sorts. */ cprintf("- OK. (Max dybde %d.)\r", sortMaxDepth); } /* qsort non-recursive. */
Princippet i qsort-algoritmen er at udvælge et data-element cirka midt i hele sættet (den såkaldte pivot), og dernæst løbe igennem fra henholdvis top og bund, idet du placerer alle elementer der er mindre end pivot'en til venstre for denne og alle der er større end pivot'en til højre for denne. Når det er gjort, vil pivot'en stå korrekt placeret. (Altså være sorteret.) Herefter gentager man proceduren for henholdsvis venstre og højre side af sættet og så fremdeles indtil den enkelte side kund er 1 dataelement langt, idet den jo så er sorteret. Kunsten i qsort-algoritmen består i at vælge den rigtige pivot - jeg har valgt at vælge den midterste værdi af top, bund og midt i tabellen.
Hej igen DMK, nå, det var godt der er nemlig nogen ting jeg godt ville have læst igen. Jeg har stadig problemer med at få det til at fungere når der bliver indtastet skal man indtaste id nr to gange og den viser ikke den samlede fortjeneste + den viser -2 i solgt efter der er blevet indtastet.Jeg sætter det hele ind såkan du garanteret se hvad jeg gør galt, Er du ikke snart træt af mig???? Spørgsmål 7 i opgaven sige at man skal sortere efter størst fortjeneste, og det skal vises.Men det er ikke aktuelt før det andet virker og jeg er også snart dødtræt af denne opgave, glæder mig til i morgen når det er afleveret. //- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - #include "stdio.h" #include "string.h" #include "iostream.h" #include <stdlib.h> #include "conio.h"
Undskyld Soepro, men jeg forstår ikke et kuk, jeg er slet ikke på det stadie Kan det ikke gøres lidt mere enkelt. Det kan godt være jeg bare skal droppe den sortering.
QSort er selvfølgelig en god algoritme til optimerede systemer, men til små skoleopgaver der skal være pædagogiske og nemme at forstå, tror jeg qsort fejler lidt.
Jeg har skrevet et hurtigt og nem-at-forstå eksempel.
void SwapElements(int &d1, int &d2) { int temp=d1; d1=d2; d2=temp; }
void SortArray(int* Array, unsigned int Size) { unsigned int SmallestIdx; for (unsigned int i=0; i<Size-1; i++) { SmallestIdx=i; for (unsigned int j=i+1; j<Size; j++) if (Array[j]<Array[SmallestIdx]) SmallestIdx=j; if (SmallestIdx!=i) { SwapElements(Array[i], Array[SmallestIdx]); } } // END for each element }
int main() { unsigned int Size=10; int Array[10]; for (unsigned int i=0; i<Size; i++) Array[i]=rand()%200;
SortArray(Array, Size);
for (i=0; i<Size; i++) printf("%d\n", Array[i]); getchar(); return 0; }
Du Blackie, kunne du ikke tage og diskutere spørgsmålet der hvor det hører hjemme? Det er lidt irriterende hvis man er interesseret i sortering, at man så skal læse 6-7 skærmbilleder om detailhandels-programmer.
Hmmm, beklager hvis jeg tog fejl (indrømmet: jeg gad ikke læse alt det der allerede står). Hvis det var sorteringen i programmet du skulle have hjælp med, så er det jo bare helt ok :-)
Pyh... Jeg har kigget lidt på det, og ja, der var nogle fejl (mine, undskyld!). Jeg har rettet dem, og har desuden tilføjet en sorteringsfunktion. Du kan prøve at kigge lidt på den, og se om det er sådan noget lignende du vil have.
Var det virkelig i morgen du skulle aflevere!?! Hvis du har spørgsmål må du jo i så fald skynde dig. Jeg tror dog snart jeg vil hjem, det har været en ret hård dag i dag, så du skal nok skynde dig.
Der er mange ting i programmet der muligvis er mindre heldige, og jeg ville da egentlig godt være sikker på, at du er helt inde i hvordan programmet fungerer, og hvordan jeg har valgt at behandle de forskellige tal. Især hvis du skal være i stand til at forsvare dem! Jeg tror nemlig der er flere af de formler jeg bruger, som muligvis ikke er helt efter opgavens ordlyd. Jeg håber også du forstår min simple simple sorterings algoritme, og at du er i stand til at forklare hvad der foregår i den? Måske du skulle prøve at forklare den for mig, så kan jeg jo se om du har forstået det.
Men jeg vil da ønske dig alt muligt held og lykke!
//------------------------------------------------------------------------------------ void VareDataBase::Sorter() { int SmallestIdx; double MindsteFortjeneste1, MindsteFortjeneste2; for (int i=0; i<Antal-1; i++) { SmallestIdx=i; for (int j=i+1; j<Antal; j++) { MindsteFortjeneste1=VareListe[SmallestIdx].SamledeSalgspris-VareListe[SmallestIdx].SamledeKobspris; MindsteFortjeneste2=VareListe[j].SamledeSalgspris-VareListe[j].SamledeKobspris; if (MindsteFortjeneste2<MindsteFortjeneste1) SmallestIdx=j; } // END for each element, inner if (SmallestIdx!=i) { SwapElements(VareListe[i], VareListe[SmallestIdx]); } // END if swap } // END for each element outer } // END Sorter
blackie >> Jeg har ikke sat mig ind i programmet, men det man også kunne gøre var at man indsatte posterne i rækkefølge fra starten, så listen altid var sorteret.
dmk >> Jeg har ikke kigget så meget i din kode, men umiddelbart ser det jo godt ud. Men du har dog lavet bobbelsortering som det netop IKKE skulle være. Alligevel kan jeg ikke lade være med at kommentere det fordi det er noget af det mest besværlige bobbelsortering jeg nogensinde har set. Nedenstående mener jeg er noget mere indlysende - og kortfattet!
void SwapElements(int &d1, int &d2) { int temp=d1; d1=d2; d2=temp; }
void SortArray(int* Array, unsigned int Size) { int i,j; for (i=0; i<Size-1; i++) for (j=i+1; j<Size; j++) if (Array[j]<Array[i]) SwapElements(Array[i], Array[i]); }
og så er det selvfølgelig smag og behag om swappen skal være inline eller ej...
NB: Jeg har ikke lige set på din nye sorteringsalgorimte, men den ser da ud som om, at der er en masse overflødigt. Det er ikke for at kritisere, men for at bidrage, for ellers ser det umiddelbart godt ud :-)
Tys,Bjarke, Bare jeg er glad, er det ikke hovedsagen. DMK, Jeg skal ikke forsvare noget andet end kort på skrift, Jeg går ind og aflevere og går igen. slut for dette semester. Du må meget gerne forklarer mig det kort.Du er simpelhen en skat.Du får de 100 point. Jeg kigger på dit kunstværk.
Tak for dine kommentarer til min sortering. Det ser nok ud til at du ved hvad du taler om, men jeg mener dog ikke det jeg har lavet er en boublesort. Så vidt jeg husker fra min tid som studerende var der to kategorier af sortering. Den ene kategori var de simple og nemme at forstå, og dem som man som regel lærer først, for at lære hvordan man sorterer. Vi lærte to algoritmer, som havde nogenlunde samme tidskompleksitet. Den ene var boublesort, og den anden var den jeg her har skrevet, og som jeg mener gik under navnet udvalgssortering (jeg kan ikke huske det engelske navn).
Boublesort fungere nogenlunde som som du har skrevet, og udvalgssortering fungerer som jeg har skrevet. Jeg har en outer loop, som først finde det mindste element, placerer det rigtigt, derefter finde det næste mindste, osv. Tidskompleksiteten for begge algoritmer er den samme, nemlig O(n!), hvilket vil sige n*(n-1)*(n-2) ned til n-(n-1). For et array af 5 elementer vil det være 5*4*3*2*=120. Hvis vi tager dobbelt så mange elementer vil det give en tidskompleksitet på 10*9*... = 3628800, så det skalerer jo helt tydeligvis overhovedet ikke. Derfor kan det egentlig også være latterligt ligegyldigt om man gør funktionen inline eller ej, da det uanset hvad ikke er plausibelt at lave algoritmer for alvor der har sådanne tidskompleksiteter. Der er dog EN stor forskel på de to sorterings algoritmer, hvis vi skal tale om tid. Tidskompleksiteten er som sagt den samme, men eksekveringstiden vil blive meget dårligere for boublesort end den vil for udvalgssortering. Det skyldes, at du flytter utrolig meget rundt med dine objekter. Så vidt jeg kan se, så flytter du potentielt dine objekter lige så mange gange som tidskompleksiteten. Det vil sige, at du kan risikere at lave en swap funktion 368800 gange, for at sortere et 10 element stort array. Jeg laver maksimalt 1 swap pr. element, hvilket vil sige 10. Og alt andet lige, Swap vil være en væsentlig faktor for eksekveringstiden.
Men hvis man skal skrive en sorterings algoritme der fungerer ordentligt, så skal man bruge den anden kategori af sorteringsfunktioner, som består af fx. qsort (quicksort) og mergesort. Disse to sorterings algoritmer har en noget mere acceptabel tidskompleksitet, som ikke stiger expotentielt. Standard c har implementeret en qsort som fungerer ganske udemærket. Jeg har selv lavet en mergesort funktion, som er noget mere optimeret end standard qsort. Da jeg lavede mine tests var min sorterings funktion ca. 7 gange hurtigere på integers, strenge og structs. Så hvis man gerne vil have en optimeret algoritme, så kan det godt anbefales at sætte sig ind i mergesort.
Sådan, nu må alle være faldet i søvn over min lange enetale.
Bjarke, jeg er ikke ud på at slagte dig, pointen er blot, at jeg ikke mener jeg har skrevet en boublesort i mit eksempel.
dmk >> Nej jeg faldt skam ikke i søvn. Tak for din hjælpsomhed. Jeg har kun kigget på din første sorteringsalgoritme (den anden krævede for meget tid at sætte sig ind i - er det det samme?).
Men, jeg skal nu altså tage meget fejl om ikke det er en (halvfordækt;-) boubble-sort du har lavet her:
void SortArray(int* Array, unsigned int Size) { unsigned int SmallestIdx; for (unsigned int i=0; i<Size-1; i++) { SmallestIdx=i; for (unsigned int j=i+1; j<Size; j++) if (Array[j]<Array[SmallestIdx]) SmallestIdx=j; if (SmallestIdx!=i) { SwapElements(Array[i], Array[SmallestIdx]); } } // END for each element }
Prøv selv at følge hvad der sker med arrayet (4,3,2,1):
4 3 2 1 3 4 2 1 2 4 3 1 1 4 3 2 1 2 3 4
Tager jeg fejl? (jeg har ikke prøvet at kompile noget af det)
Ja du tager fejl ! Array'et (4,3,2,1) sorteres således:
4 3 2 1 (i=0, SmallestIdx bliver 3) 1 3 2 4 (i=1, SmallestIdx bliver 2) 1 2 3 4 (i=2, SmallestIdx bliver 2) 1 2 3 4 (I=3, SmallestIdx bliver 3)
Færdig ! BubbleSort er i øvrigt en af de få sorteringsalgoritmer hvor man kan optimere hvis de data man sorterer allerede er helt eller delvist sorteret. Dine betragtninger omkring effektiviteten af de forskellige algoritmer er derfor ikke helt ritige - Bubblesort er den absolut hurtigste algoritme hvis mindre end 15% af dataene er u-sorterede. Effektiviteten kan yderligere forbedres hvis bubblesort'en skiftevis sætter højeste og mindste element på plads.
Og så lige et PS: Det er almindelig kutyme på "eksperten" at man fordeler sine point mellem ALLE dem der har gidet bruge tid på at forsøge at give et svar - også selvom man ikke lige synes man kunne bruge det, fordi det var for komplekst. (Og da især når man bare fik det man bad om !) Man kan så fordele forholdsmæssigt som man synes folk har fortjent.
Jeg kan se at du har forstået mit forsøg på at lave en sortering der ikke er boublesort rigtigt. Så kan du måske også fortælle mig hvad min algoritme hedder?
Jeg er i øvrigt ikke helt med på din redegørelse for hastigheden af de to algoritmer. Jeg går ud fra at vi er enige om, at de begge to har en tidskompleksitet på O(n!) ? Så på det område er de lige latterlige. Og så vidt jeg lige kan regne ud, dog uden at have tænkt specielt meget over det, så fungerer udvalgssortering (hvis det hedder det) vel bedst på delvist sorterede arrays?
Betragt følgende array: 6 2 3 1
I dette tilfælde vil 4 blive swappet 3 gange, før det ender på den rigtige plads. 1 vil også blive swappet 3 gange før det ender på den rigtige plads. 2 og 3 vil blive swappet hver gang 4 og 1 ikke bliver swappet sammen, hvilket kun sker 1 gang. Med udvalgssortering vil alle elementer der står på den rigtige plads fra starten aldrig blive swappet.
Hvis du vil have din 15% regel modbevist, så forestil dig det samme for følgende array:
Her er kun 10 procent af dataene usorterede, men boublesort vil bytte uendelig meget rundt på elementerne, for at få 20 og 1 til at skifte plads. Udvalgssortering vil kun bytte 20 og 1, og den er dermed færdig. Begge algoritmer vil lave 20! sammenligninger, så her er der ingen forskel.
MHT fordeling af point skal jeg ikke være den store dommer, da jeg er ret ny her på eksperten. Men jeg vil dog sige, at hvis du kigger lidt på det arbejde jeg har lagt i det, så er det måske ikke helt urimeligt at jeg har fået pointene? Du har pastet et eksempel ind som du vist ikke selv har lavet, og som er fuldstændig uforståeligt for enhver nybegynder. Skal det give point?
Den QSORT-algoritme har jeg selv lavet til mit produkt PCSORt - kig min hjemmeside http://hjem.get2net.dk/soepro, så ned det er ikke copy/paste.
Og jo, du har lagt meget mere arbejde i at løse hans FØRSTE problem - men ikke sorteringen som det her spørgsmål gik på. Jeg havde da gerne set at jeg havde fået bare 5 point for mit besvær. Men .. flot arbejde DU har lavet.
Okay, alt respekt for din qsort. Godt arbejde! Men du må da indrømme, at det er nogenlune ubrugeligt for en nybegynder der gerne vil have et eksempel, som hun kan prøve at integrere i sit meget simple program.
I øvrigt er dette spørgsmål jo netop, at hun gerne vil have en sorterings funktion til det "tidligere omtalte program", og det er jeg vel den eneste der har lavet. I andre er kommet med nogle udemærkede algoritmer, men ikke nogen hun har kunne bruge til sin opgave, så derfor har de ikke løst hendes problem. Jeg ville i øvrigt også hellere have redegjort for min merge-sort algoritme, og hvorfor jeg mener den er qsort overlegen. Men det var ikke det der var opgaven.
Hej alle sammen. Jeg kan se der har været en del diskutioner, mendens jeg har været væk og føler lidt, det er min skyld, håber ikke det er tilfældet, ihvertfald skal jeg nok fremtidig prøve at opfører mig ordentligt. Jeg synes nu også, at DMK har fortjent sine point, han har gjort et stort stykke arbejde.TUSIND TAK DMK. Det er ikke fordi, jeg vil gøre mig klog, for det er jeg ikke, jeg er kun begynder endnu, håber jeg bliver bedre med tiden. Vi havede på en hel dag i vores undervisning haft om algoritmer og blev præsenteret for temmelig mange forskellige henholdvis:
1. Indsættelsesalgoritmer Indsættelsessortering Shell-sortering 2. Ombytningsalgoritmer Boblesortering Cocktailshakersortering Batchersortering Delingssortering(quiksort) Radixombytningssortering 3. Udvælgelsesalgoritmer Udvælgelsessortering Heap-sortering 4. Fletningsalgoritmer Fordoblingsfletnings-sortering Naturlig tovejsfletnings- sortering 5. Øvrige algoritmer Indplacering ved optælling Radixsortering Er der noget at sige til, at man bliver en del forvirret, kunne man ikke nøjes med to? N.B. Jeg har et program, som viser grafisk med stave, hvordan det sker med de forskellige ovenstående algoritmer. Kan man gå ind i den fil (exe fil) og se programmeringen, hvordan gør man??? Jeg kører både med Borland 5.0 C++ og tcp30 C++. Omkring point, det vil til hver en tid være mig, som skal ofre point, da jeg ikke kan besvarer spørgsmål og ikke vinder point igen, jeg er ikke dygtig nok endnu. Derfor må jeg også passe lidt på de point, jeg har, hvis jeg skal have hjælp igen og det vil jeg jo gerne, bær over med mig, hvis i synes jeg stiller dumme spørgsmål... I er jo EKSPERTERNE.
At gå ind i koden på en exe-fil er ikke noget man bare gør. Først og fremmest er der copyright for firmaet/programmøren. Desuden er der det tekniske aspekt.
Når du kompilerer dit program, bliver din kode til en fil windows kan forstå - og mange af dine strukturer bliver lavet på en anden måde, og navnene på variable forsvinder. Det bliver derfor svært at sætte sig ind i koden, selv hvis man får den reversed, som det hedder.
Men jeg tror da nok at den slags programmer (stave til at symbolisere sorteringer) er ret udbredte. Mon ikke din lærer har et sådant program? Ellers er det relativt nemt at lave.
Synes godt om
Ny brugerNybegynder
Din løsning...
Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.