Uppgift 12 - BubbleSort

Börja med att importera klassen Random. Skapa sedan alla variabler som behövs i ditt program. Skicka sedan in dessa variabler till din nya metod, exempelvis med namnet generateTestData().

import java.util.Random;

public class Uppgift12 {
    public static void main(String[] args) {
        int numberOfElements = 20;
        int minVal = 0;
        int maxVal = 100;

        int[] testData = generateTestData(numberOfElements, minVal, maxVal);
    }
}

I din nya metod kan du sedan skapa en for-loop där du skapar och lägger till ett slumpmässigt heltal med klassen random. Exempelvis,

Random random = new Random();
int value = random.nextInt(100); // 0 till 99

Skapa en ny metod som heter printArray() som tar emot en array.

public static void printArray(int[] arr) {

}

Det finns olika sätt att lösa uppgiften på. Antingen kan du bara loopa igenom alla element i arrayen och spara undan varje element i en sträng. Alternativt kan du använda dig av den inbyggda metoden toString().

String text = Arrays.toString(arr);

Det kommer krävas två for-loopar för att gå igenom alla element.

for (int i = 0; i < arr.length; i++) {
    for (int j = 1; j < arr.length - i; j++) {
    
    }
}

Undersök därefter intilliggande element och avgör om de ska byta plats eller ej. Du kommer behöva använda dig av en temporär variabel för att spara undan ena värdet medans du byter plats på elementen.

import java.util.Arrays;
import java.util.Random;

public class Uppgift12 {
    public static void main(String[] args) {
        int numberOfElements = 20;
        int minVal = 0;
        int maxVal = 100;

        // Generate test data
        int[] testData = generateTestData(numberOfElements, minVal, maxVal);

        // Print original array
        printArray(testData);
        
        // Print sorted array
        printArray(bubbleSort(testData));

    }

    // Generates random test data 
    public static int[] generateTestData(int nmbrOfElements, int minVal, int maxVal) {
        Random random = new Random();
        int arr[] = new int[nmbrOfElements];

        for (int i = 0; i < nmbrOfElements; i++) {
            arr[i] = random.nextInt(maxVal - minVal) + minVal;
        }

        return arr;
    }

    // Print array
    public static void printArray(int[] arr) {
        System.out.println(Arrays.toString(arr));
    }

    // Bubble sort algorithm
    public static int[] bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 1; j < arr.length - i; j++) {
                if (arr[j - 1] > arr[j]) {
                   int tmp = arr[j - 1];
                   arr[j - 1] = arr[j];
                   arr[j] = tmp;
                }
            }
        }
        return arr;
    }
}

Förklaring:

generateTestData():

Metoden generateTestData() skapar först en tom array med ett bestämt antal värden i. Vi loopar sedan igenom alla index i arrayen och tilldelar ett slumpmässigt värde för varje index.

Koden

int value = random.nextInt(maxVal - minVal) + minVal;

genererar ett slumpmässigt heltal större eller lika med minVal och mindre än maxVal. Läs mer om hur man genererar ett slumptal i ett visst intervall under klassen Random.

printArray():

Vi använder sedan den inbygda klassen toString() för att skriva ut alla värden i en array.

String text = Arrays.toString(arr);

Det går självklart lika bra att loopa igenom alla värden i arrayen och spara undan varje element i en lista.

BubbleSort():

Algoritmen BubbleSort löste vi på detta sätt:

for (int i = 0; i < arr.length; i++) {
    for (int j = 1; j < arr.length - i; j++) {
        if (arr[j - 1] > arr[j]) {
            int tmp = arr[j - 1];
            arr[j - 1] = arr[j];
            arr[j] = tmp;
        }
    }
}

Vi använder en temporär variabel medans vi byter plats på elementen så att vi inte skriver över någon data.

int tmp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = tmp;

Observera att bubbelsortering är en förhållandevis långsam sorteringsalgoritm och det finns betydligt effektivare sätt att sortera på. Mer om det i framtiden!