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

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.

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:

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?

Initiera $i$ 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]
        }

Ovanstående kommer alltid att returnera maxIndex.

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

En enkel fix är att spara undan index för ditt minimum 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 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. 

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?

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 $\displaystyle O(n^2)$