Homework: Sorting Algorithms

Question

I am supposed to create an algorithm that sorts according to these steps:

Method 1

Select the lowest number in the list and swap with the first number.

Select the lowest number in the list and swap with the second number. Start checking from the second number.

Select the lowest number in the list and swap with the third number. Start checking from the third number.

Select the lowest number in the list and swap with the fourth number. Start checking from the fourth number.

Repeat…until you reach the last number.

Currently, this is the code I have come up with:

public static void method1() {
    int low = 999;        
    int index = 0;
    int safe;
    int[] num = new int[] { 33, 22, 8, 59, 14, 47, 60, 27 };

    for(int i = 0; i < num.length; i++) {
        if(low > num[i]) {
            low = num[i];
            index = i;
        }
    }

    for (int i = 0; i < num.length; i++) {
        safe = num[i];
        num[i] = num[index];
        low = 999;
        for(int j = (i+1); j < num.length; j++) {
            if(low > num[j]) {
                low = num[j];
            }
        }
    }

    for (int i = 0; i < num.length; i++) {
        System.out.print(num[i] +", ");
    }
}

The output looks like this:

run:
8, 8, 8, 8, 8, 8, 8, 8, 
BUILD SUCCESSFUL (total time: 0 seconds)

Why am I only getting values of 8 in the output? As this is homework, please don't tell me the answer. I would only like guidance, thanks!

EDIT:

Code now looks like this:

int low = 999;        
        int index = 0;
        int safe;
        int[] num = new int[] { 33, 22, 8, 59, 14, 47, 60, 27 };

        for(int i = 0; i < num.length; i++) {
            if(low > num[i]){
                low = num[i];
                index = i;
            }
        }

        for (int i = 0; i < num.length; i++) {
            safe = num[i];
            num[i] = num[index];
            low = 999;
            for(int j = (i+1); j < num.length; j++) {
                if(low > num[j]){
                    low = num[j];
                    index = j;
                }
            }
        }

        for (int i = 0; i < num.length; i++) {
            System.out.print(num[i] +", ");
        }
        System.out.println("");

Which gives me an output of:

run:
8, 8, 8, 14, 14, 27, 27, 27, 
BUILD SUCCESSFUL (total time: 0 seconds)

You didn't ask a question. And what have you tried to debug it? — Carcigenicate
– Carcigenicate, Commented May 11, 2017 at 0:38
Sorry, I added it in the post. I already did this: ` for (int i = 0; i < num.length; i++){ ` safe = num[i]; num[i] = num[index]; low = 999; for(int j = (i+1); j < num.length; j++){ if(low > num[j]){ low = num[j]; index = j; } } } — Lance
– Lance, Commented May 11, 2017 at 0:42
He wants to solve it himself. Honestly this is one of the better homework-type questions I've seen here. @OP: You're not using safe and you're setting incorrect values in your num[i] = num[index]; line. Focus on that. — Marvin
– Marvin, Commented May 11, 2017 at 0:45
@Lance In your second loop you're going over num and setting the value at every index to num[index], which is the "lowest" value you've determined in your first loop. — Marvin
– Marvin, Commented May 11, 2017 at 0:50

Stewart · Accepted Answer · 2020-01-24 12:42:38Z

The date for this homework has been and gone, but thought I would add some step-by-step methodology.

The way I would approach this is to break it down into small steps. Each step should be a method or function.

1. The first step is to find the smallest number in the array, starting from N.

So the method for this would be:

private int findLowestStartingAtNth( int n ) {
    int lowest = Integer.MAX_VALUE;
    for( int i = n ; i < numbers.length ; i++ ) {
        if( numbers[i] < lowest ) {
            lowest = numbers[i]; 
        }
    }
    return lowest;
}

2. Then we need to swap two arbitrary numbers in an array.

This is quite simple:

private void swapNumbers( int i, int j ) {
    int temp = numbers[i];
    numbers[i] = numbers[j];
    numbers[j] = temp;
}

3. But if we want the output of `findLowestStartingAtNth()` to feed into the input of `swapNumbers()`, then we need to return the index not the number itself.

So the method from step 1. is altered to be:

private int findLowestStartingAtNth( int n ) {
    int lowest = Integer.MAX_VALUE;
    int index = n;
    for( int i = n ; i < numbers.length ; i++ ) {
        if( numbers[i] < lowest ) {
            lowest = numbers[i]; 
            index = i;
        }
    }
    return index;
}

4. Let's use what we have to achieve step one

Select the lowest number in the list and swap with the first number.

The first number is the zero-th in the array.

int numbers = new int[] {33, 22, 8, 59, 14, 47, 60, 27};
int found = findLowestStartingAtNth( 0 );
swapNumbers(0, found);

5. We have a pattern. Start checking from 1st, swap with 1st. Start checking from 2nd, swap with 2nd. Start checking with X, swap with X.

So let's wrap this pattern in a further method:

private int[] numbers = new int[] {33, 22, 8, 59, 14, 47, 60, 27};
private void sort() {
    for( int i = 0 ; i < numbers.length ; i++ ) {
        int j = findLowestStartingAtNth( i );
        swapNumbers(i, j);
    }
}

6. Finally, wrap it in a class, and trigger it from `main()` method. See how clear the code is because it is broken into small steps.

The entire resulting class would be:

public class Method1 {

    public static void main(String[] args) {
        Method1 m = new Method1();
        m.numbers = new int[] {33, 22, 8, 59, 14, 47, 60, 27};
        m.sort();
        System.out.println(Arrays.toString(m.numbers));
    }

    private int[] numbers;

    private int findLowestStartingAtNth( int n ) {
        int lowest = Integer.MAX_VALUE;
        int index = n;
        for( int i = n ; i < numbers.length ; i++ ) {
            if( numbers[i] < lowest ) {
                lowest = numbers[i]; 
                index = i;
            }
        }
        return index;
    }

    private void swapNumbers( int i, int j ) {
        int temp = numbers[i];
        numbers[i] = numbers[j];
        numbers[j] = temp;
    }

    private void sort() {
        for( int i = 0 ; i < numbers.length ; i++ ) {
            int j = findLowestStartingAtNth( i );
            swapNumbers(i, j);
        }
    }
}

It's also worth to mention that this algorithm is called Selection sort for both educational purposes and indexing the page.

Collectives™ on Stack Overflow

Homework: Sorting Algorithms

Method 1

EDIT:

1 Answer 1

1. The first step is to find the smallest number in the array, starting from N.

2. Then we need to swap two arbitrary numbers in an array.

3. But if we want the output of `findLowestStartingAtNth()` to feed into the input of `swapNumbers()`, then we need to return the index not the number itself.

4. Let's use what we have to achieve step one

5. We have a pattern. Start checking from 1st, swap with 1st. Start checking from 2nd, swap with 2nd. Start checking with X, swap with X.

6. Finally, wrap it in a class, and trigger it from `main()` method. See how clear the code is because it is broken into small steps.

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

Method 1

EDIT:

1 Answer 1

1. The first step is to find the smallest number in the array, starting from N.

2. Then we need to swap two arbitrary numbers in an array.

3. But if we want the output of findLowestStartingAtNth() to feed into the input of swapNumbers(), then we need to return the index not the number itself.

4. Let's use what we have to achieve step one

5. We have a pattern. Start checking from 1st, swap with 1st. Start checking from 2nd, swap with 2nd. Start checking with X, swap with X.

6. Finally, wrap it in a class, and trigger it from main() method. See how clear the code is because it is broken into small steps.

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related

3. But if we want the output of `findLowestStartingAtNth()` to feed into the input of `swapNumbers()`, then we need to return the index not the number itself.

6. Finally, wrap it in a class, and trigger it from `main()` method. See how clear the code is because it is broken into small steps.