9 svar
233 visningar
Dani163 1035
Postad: 24 nov 2022 22:27

Hur ska jag sortera igenom en array av strängar genom en sorteringsalgoritm?

Här är uppgiftsbeskrivningen:

Jag behöver komplettera denna metod:

Jag tror detta är "selection sort algorithm":

 

Tanken är att koden ska sedan visa detta (tillsammans med de andra metoderna som jag inte tog med):

 

Som ni märker så är det en ganska omfattande uppgift, men jag har inte riktigt fattat den här sorteringsalgoritmen hur den går till, och vilka strängar man ska gå igenom, är det synonymData? Jag bifogar filen till synonymHandler här.

Laguna Online 30713
Postad: 26 nov 2022 12:10

Texten du visar verkar vara hur det kan se ut om man skriver ut vad algoritmen gör medan den arbetar, men jag kan inte riktigt tolka den. Om du har en fil med textsträngar som heter synonymData så är det nog den du ska sortera.

Prova att utföra algoritmen med penna och papper så förstår du den kanske.

Fermatrix 7841 – Fd. Medlem
Postad: 26 nov 2022 13:01 Redigerad: 26 nov 2022 13:02

Du ska sortera en array så att de är i bokstavsordning.

Det första du måste göra är att definiera för klassen vad det betyder om instansen this > that, och dylikt. Finns det ett lämpligt interface vi kan använda? 

Selection sort är väldigt simpel. Det man gör att man letar upp det minsta elementet, och slänger den sist i litan. Nu hittar man det nya minimum från en index fram:



Dani163 1035
Postad: 27 nov 2022 18:00
Dracaena skrev:

Du ska sortera en array så att de är i bokstavsordning.

Det första du måste göra är att definiera för klassen vad det betyder om instansen this > that, och dylikt. Finns det ett lämpligt interface vi kan använda? 

Selection sort är väldigt simpel. Det man gör att man letar upp det minsta elementet, och slänger den sist i litan. Nu hittar man det nya minimum från en index fram:



Så jag övade med ett litet experiment. 

class Main {
    public static void main (String[] args)
    {
        int[] arr = {16, 5, 5, 4, 13, 2, 0};
        System.out.println(findMin(arr, 3, 6));
    }
    public static int findMin (int[] arr, int minIndex, int maxIndex)
    {
        int min = arr[minIndex]; // set the min value at arr[3]
        for (int i = minIndex; i < maxIndex; i++) // start at arr[3]
        { // and go to arr[5]
            if (arr[i] < min) // if arr[3] < arr[3] then min = arr[3]
            {
                min = arr[i];
            } // if arr[4] < arr[3] then min = arr[4]
        }
        return min; // return arr[4]
    }
}

Dessutom skapade jag en metod som accepterar en heltalsarray som en parameter och returnerar elementet med det minsta värdet som returvärde; i huvudsak var allt som krävdes en loop som itererade tills vyn (det som är inom klamrarna) blev tom. Sedan ändrade jag min metod för att inkludera ytterligare två parametrar: metoden är tänkt att hitta minimivärdet i arrayen inom det givna indexintervallet istället för hela arrayen eftersom int startIndex och endIndex ska begränsa visningen på arrayen. Funktionen findMin(arr, 2, 5) kontrollerar index 2, 3, 4 och 5 och returnerar 2 som det minsta talet i arrayens intervall. Jag skapade också en metod för att byta två matrisindex, som swap(array, 3, 7) för att ersätta index 3 med index 7.

public static void swap (int[] arr, int index1, int index2)
    {
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }

Just nu har jag fastnat för att modifiera findMin-metoden så att den returnerar indexet för min-elementet snarare än det faktiska min-elementet. Och kanske byta namn på metoden till findMinIndex?

Fermatrix 7841 – Fd. Medlem
Postad: 27 nov 2022 18:09 Redigerad: 27 nov 2022 18:13

Initiera ii utanför scopen för din while-loop så kan du returnera den istället:

class Main {
    public static void main (String[] args)
    {
        int[] arr = {16, 5, 5, 4, 13, 2, 0};
        System.out.println(findMin(arr, 3, 6));
    }
    public static int findMin (int[] arr, int minIndex, int maxIndex)
    {
        int min = arr[minIndex]; // set the min value at arr[3]
        int i = minIndex;
        for (;i < maxIndex; i++) // start at arr[3]
        { // and go to arr[5]
            if (arr[i] < min) // if arr[3] < arr[3] then min = arr[3]
            {
                min = arr[i];
            } // if arr[4] < arr[3] then min = arr[4]
        }
        return i; // return arr[4]
    }
}

Om du tycker det är mer läsbart så kan du också skriva:

        int i = 0;
        for (i = minIndex;i < maxIndex; i++) // start at arr[3]
        { // and go to arr[5]
            if (arr[i] < min) // if arr[3] < arr[3] then min = arr[3]
            {
                min = arr[i];
            } // if arr[4] < arr[3] then min = arr[4]
        }
Laguna Online 30713
Postad: 27 nov 2022 18:27

Ovanstående kommer alltid att returnera maxIndex.

Fermatrix 7841 – Fd. Medlem
Postad: 27 nov 2022 18:30 Redigerad: 27 nov 2022 18:34

Oj, det missade jag! Bra fångst Laguna. :)

En enkel fix är att spara undan index för ditt minimum istället.

Fermatrix 7841 – Fd. Medlem
Postad: 27 nov 2022 18:41
class Main {
    public static void main (String[] args)
    {
        int[] arr = {16, 5, 5, 4, 13, 2, 0};
        System.out.println(findMin(arr, 3, 6));
    }
    public static int findMin (int[] arr, int minIndex, int maxIndex)
    {
        int min = arr[minIndex]; // set the min value at arr[3]
        int indexOfMinimum = minIndex;
        for (int i = minIndex; i < maxIndex; i++) // start at arr[3]
        { // and go to arr[5]
            if (arr[i] < min) // if arr[3] < arr[3] then min = arr[3]
            {
                min = arr[i];
                indexOfMinimum = i;
            } // if arr[4] < arr[3] then min = arr[4]
        }
        return indexOfMinimum; // return arr[4]
    }
}

Men din design, så borde detta producera index för ett minimum i din splice. 

Dani163 1035
Postad: 27 nov 2022 20:25
Dracaena skrev:
class Main {
    public static void main (String[] args)
    {
        int[] arr = {16, 5, 5, 4, 13, 2, 0};
        System.out.println(findMin(arr, 3, 6));
    }
    public static int findMin (int[] arr, int minIndex, int maxIndex)
    {
        int min = arr[minIndex]; // set the min value at arr[3]
        int indexOfMinimum = minIndex;
        for (int i = minIndex; i < maxIndex; i++) // start at arr[3]
        { // and go to arr[5]
            if (arr[i] < min) // if arr[3] < arr[3] then min = arr[3]
            {
                min = arr[i];
                indexOfMinimum = i;
            } // if arr[4] < arr[3] then min = arr[4]
        }
        return indexOfMinimum; // return arr[4]
    }
}

Men din design, så borde detta producera index för ett minimum i din splice. 

Det fungerar! Eftersom jag fick 5 har vi nu indexet för arr[4]. Bara en sak fascinerar mig: varför skriver vi (arr[i] min) på det sättet? Motsvarigheten är arr[3] < arr[3].

Jag fick höra att arr[i] representerar det aktuella värdet. Om det aktuella värdet är mindre än det kända minimivärdet har vi upptäckt ett bättre minimum. När vi itererar arrayen ändras min.

Jag tror att vi nu kan börja sätta ihop allt för att ta oss an uppgiften i inlägg #1 iaf. Vi har allt vi behöver för det. Så algoritmen börjar med hela arrayen, söker efter minimum, byter den framåt och minskar sedan visningen på arrayen med en. Vi behöver helt enkelt två variabler – en för startindexet och den andra för slutindexet – och en loop som itererar över arrayens element upprepade gånger tills vyn är tom (start == slutindex). Under loopen hittar vi minimum, byter det framåt och minskar sedan vyn med en (startIndex++). 

Är denna tolkning korrekt? Eller finns det något att tillägga?

Fermatrix 7841 – Fd. Medlem
Postad: 27 nov 2022 20:36 Redigerad: 27 nov 2022 20:42

Det fungerar! Eftersom jag fick 5 har vi nu indexet för arr[4]. Bara en sak fascinerar mig: varför skriver vi (arr[i] min) på det sättet? Motsvarigheten är arr[3] < arr[3].

Se min ritning:

Jag tror att vi nu kan börja sätta ihop allt för att ta oss an uppgiften i inlägg #1 iaf. Vi har allt vi behöver för det. Så algoritmen börjar med hela arrayen, söker efter minimum, byter den framåt och minskar sedan visningen på arrayen med en. Vi behöver helt enkelt två variabler – en för startindexet och den andra för slutindexet – och en loop som itererar över arrayens element upprepade gånger tills vyn är tom (start == slutindex). Under loopen hittar vi minimum, byter det framåt och minskar sedan vyn med en (startIndex++). 

slutet är alltid samma längd i alla iterationer, det som ändras är vart vi startar. Du kommer därför behöva två for-loopar. Men överlag så verkar du ha en aning om vad du skall göra. Prova att implementera din sort.


Det är därför inte så förvånansvärt att worst case är O(n2)\displaystyle O(n^2)

Svara
Close