Junior & rekrutacja cz.2

Cześć!! 🙂 w kolejnym wpisie z serii junior & rekrutacja. Tym razem zdecydowałam się przybliżyć nieco jedno z zadań rekrutacyjnych które jakiś czas temu otrzymałam. Ponieważ było to zadanie na czas jedyne co zdążyłam zrobić to sporządzić szybkie notatki aby później jeszcze raz przyjrzeć się mu przyjrzeć.

Treść zadania mniej więcej wyglądała następująco: poproszono o policzenie absolutnej minimalnej sumy tablicy integerów. Jako przykład miałam podane następujące wartości: [1,3,3,2,4] gdzie n = 5. Należało odejmować kolejno wartości bezwzględne np: |1 – 2| = 1, |2 – 3| = 1, |3 – 3| = 0, |3 – 4| = 1 zaś suma minimalna to 1+1+0+1 = 3. Przykładowe dane dla którego miałam wykonać zadanie to n=5, suma = 6, tablica [5,1,3,7,3]

Gdy przyjrzymy się przykładowi [1,3,3,2,4] zobaczymy że tablica najpierw została posortowana. Do rozwiązania zadania zastosowałam sortowanie przez wymianę/wybieranie. W dalszej części rozwiązania wykorzystuje metodę na policzenie sumy absolutnej.

Wracając do algorytmy sortowania przez wybieranie algorytm ten na początku szuka najmniejszego elementu aby po jego znalezieniu zamienić go z pierwszym elementem tablicy. Następnym krokiem jest szukanie drugiego najmniejszego elementu który zostanie zamieniony z drugim obecnym elementem w tablicy. Pierwszy odnaleziony element jest już na swoim miejscu i dlatego zastaje on pomijany. Procedura jest powtarzana aż do n-tego elementu tablicy.

Źrodło: http://www.algorytm.org/algorytmy-sortowania/sortowanie-przez-wymiane-wybor-selectionsort.html
 public static int arraySort(int[] sorted) {
        int temp;
        int min;
/* przechodzimy przez wszystkie elementy tablicy, do naszego min przypisujemy obecną wartości która znajduje pod indeksem zerowym w tablicy. */
        for (int i = 0; i < sorted.length; i++) {
            min = i;
//przechodzimy przez kolejne elementy tablicy
            for (int j = i; j < sorted.length; j++) {
/* sprawdzamy czy wartość pod obecnym indeksem "j" jest mniejsza od naszego obecnego min. Jeżeli tak jest, to do obecnego min przypisujemy nową mniejszą wartość.*/
                if (sorted[j] < sorted[min]) {
                    min = j;
                }
            }
// zamieniamy elementy w tablicy. 
            temp = sorted[i];
            sorted[i] = sorted[min];
            sorted[min] = temp;
        }
// wypisanie posortowanej tablicy [1,3,3,5,7]
        System.out.println(Arrays.toString(sorted));

//wykorzystanie metody na policzenie sumy absolutnej
int absSum = getAbsoluteSum(sorted);
        System.out.print(absSum);
        return absSum;
    }

Leave a Comment

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *