-2

I'm trying to make a selection sort algorithm in java that finds the smallest element of an unsorted array and puts it on the end of a new array. But my program only copies the first element twice, gets the next one, and then the rest is all zeroes:

  public static int find_min(int[] a){
    int m = a[0];
    for (int i = 0; i < a.length; i++){
      if (m > a[i])
        m = a[i];
    }
    return m;
  }

  public static int[] selectionSort(int[] unsorted){
    int[] c = new int[unsorted.length];

    for(int i = 0; i < unsorted.length; i++){
      int smallest = find_min(unsorted);
      c[i] = smallest;
      unsorted = Arrays.copyOfRange(unsorted, i+1, unsorted.length );
    }

    return c;
  }

When I put in something like:

  public static void main(String[] args){
    int a[] = {1,-24,4,-4,6,3};
    System.out.println(Arrays.toString(selectionSort(a)));
  }

I get: [-24, -24, -4, 0, 0, 0]

where is this going wrong? Is this a bad algorithm?

user73218
  • 13
  • 6
  • 1
    `Is this a bad algorithm?` It is a bad implementation. I give you a tip. You don't have to use `Arrays.copyOfRange`, and you don't need to allocate a new array. If you use these, your algorithm isn't a `Selection Sort` anymore. – lilezek Oct 24 '17 at 23:17
  • That's a lot of code for just selecting the minimum element in a subarray. Congrats. – xiaofeng.li Oct 24 '17 at 23:18
  • 1
    [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173/5221149) – Andreas Oct 24 '17 at 23:19
  • lilezek, why wouldn't it be a selection sort? I thought a selection sort was finding the min of an unsorted array and putting it in the place. What should I use instead? – user73218 Oct 24 '17 at 23:20
  • 1
    Did you even bother to look at how Selection Sort works? E.g. see [Wikipedia](https://en.wikipedia.org/wiki/Selection_sort#Implementation). – Andreas Oct 24 '17 at 23:21
  • what is wrong with just helping people?? – user73218 Oct 24 '17 at 23:32
  • @user73218 What's wrong with doing your own research, and your own trouble-shooting, rather than asking others to do it for you? Nothing. It's actually a requirement for this site. This site is not a substitute for doing your own work. Do your research on how Selection Sort works, and you'll quickly find that your code is not the same. Do your own debugging, and you'll quickly find that why your code is not working. If you still cannot figure it out after that, you can at least write a better question, asking about a *specific* problem that you've narrowed it down to. – Andreas Oct 25 '17 at 00:01

1 Answers1

0

Ok, let's revisit the selection sort algorithm.

public static void selectionSort(int[] a) {
    final int n = a.length; // to save some typing.

    for (int i = 0; i < n - 1; i++) {
        // i is the position where the next smallest element should go. 
        // Everything before i is sorted, and smaller than any element in a[i:n).
        // Now you find the smallest element in subarray a[i:n). 
        // Actually, you need the index
        // of that element, because you will swap it with a[i] later.
        // Otherwise we lose a[i], which is bad.
        int m = i;
        for (int j = m + 1; j < n; j++) {
            if (a[j] < a[m]) m = j;
        }

        if (m != i) {
            // Only swap if a[i] is not already the smallest.
            int t = a[i];
            a[i] = a[m];
            a[m] = t;
        }
    }
}

In conclusion

  • You don't need extra space to do selection sort
  • Swap elements, otherwise you lose them
  • Remembering the loop invariant is helpful
xiaofeng.li
  • 8,237
  • 2
  • 23
  • 30