Sort array in descending order and show output per iteration

Question

So I am trying to create a program that takes in array int list and prints out array items in descending order. However, print statement should be implemented to show each progress made in doing the task. I mean lets say the input is 20 10 30 40. The output shouldn't be just 40 30 20 10 The output should be as follows:

40 10 30 20 
40 30 10 20 
40 30 20 10 

however when I run my code I get the following output:

40  10  20  30
40  30  10  20
40  30  20  10
40  30  20  10

I don't understand what I am doing wrong here. here is my code:

import java.util.Arrays;
import java.util.Scanner;

public class check {

    public static void main(String[] args) 
    {
        int n, temp;
        Scanner s = new Scanner(System.in);
        System.out.print("Enter no. of elements you want in array:");
        n = s.nextInt();
        String str;
        int a[] = new int[n];
        System.out.println("Enter all the elements:");
        for (int i = 0; i < n; i++) 
        {
            a[i] = s.nextInt();
        }
        for (int i = 0; i < n; i++) 
        {
            for (int j = i + 1; j < n; j++) 
            {
                if (a[i] < a[j]) 
                {
                    temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;

                }

            }
            str=Arrays.toString(a).replace(",", " ")  
                    .replace("[", "")  
                    .replace("]", "")  
                    .trim(); 

            System.out.println(str);
        }

    }
}

Answer 1

You need to determine where the problem is in your code. To debug code, I often will use System.out.println outputs, placed at intervals where I want to check some value. In this particular example, you know that the output of the program isn't what you expect, which is different from isn't correct. I typically use the following debugging steps when trying to isolate a logic problem of this source.

1. First, check the inputs: It's possible something slipped in during your input of the initial values. Adding:

   System.out.println("Value of a[" + i + "]:" + a[i]);
   

   after:

   [i] = s.nextInt(); 
   

   Reveals that this is not the case, so we can safely skip this. I just put it here because, there have been many times I disregard this step, only to find out much later that the problem was with my inputs not being what I expect (e.g. a newline character snuck in somehow)

2. Check to see what the state of each iteration of the loop is: In this case, you already have output for each iteration of the loop. What we're seeing is that there's an extra iteration of the loop that we don't expect.

   This second debugging step leads to the hypothesis that perhaps the loop condition is set up incorrectly. Looking at the outer for loop (which is the block containing this output), we see:

   for (int i = 0; i < n; i++)
   

   So, what this means, is that for an input of n items, the loop will always execute exactly n times. In this case, n is 4, so the loop executes 4 times, but the list is sorted after 3 iterations.

Ok, so we've found the problem. Now, how do we solve it? There are two possible options. The first is to use a different looping condition, such as setting up a while loop to execute until the loop is sorted, rather than looping a specific number of times. However, this particular code seems like a school exercise, in which case, it's possible that you're required to use the for loop syntax as part of the exercise constraints. In this case, we can use the break statement at the beginning of the loop:

for (int i = 0; i < n; i++) {
  if (arrayIsAlreadySorted(a)) {
    break;
  }
  ... rest of for loop body ...
}

Given that I suspect this is an exercise, I'm going to leave it to you to write the function arrayIsAlreadySorted(), as, given your existing code starting point, I think you'll have no problem accomplishing this.

Answer 2

Following the logic of your algorithm, the program output is correct.

For each position in the list, compare the next values in the list with the value of this position. If some next value if bigger than the value of this position, swap values. So, for a input 20 10 30 40, the output would be:

// first position
20 10 30 40
20 10 30 40
30 10 20 40
40 10 20 30 (print)

// second position
40 10 20 30
40 20 10 30
40 30 10 20 (print)

// third position
40 30 10 20
40 30 20 10 (print)

// fourth position (not necessary)
40 30 20 10 (print)

To get the expected output, try Bubblesort algorithm.