설명#

The selection sort works by selecting the smallest unsorted item remaining in the list, and then swapping it with the item in the next position to be filled. The selection sort has a complexity of O(n<span class="sup">2</span>).

The selection sort is the unwanted stepchild of the n<span class="sup">2</span> sorts. It yields a 60% performance improvement over the bubble sort, but the insertion sort is over twice as fast as the bubble sort and is just as easy to implement as the selection sort. In short, there really isn't any reason to use the selection sort - use the insertion sort instead.

If you really want to use the selection sort for some reason, try to avoid sorting lists of more than a 1000 items with it or repetitively sorting lists of more than a couple hundred items.

  • 장점: Simple and easy to implement.
  • 단점: Inefficient for large lists, so similar to the more efficient insertion sort that the insertion sort should be used in its place.

실행횟수

O(n<span class="sup">2</span>)

자바 소스#

public class SelectionSort {

  public static void sort(int numbers[]) {
    int i, j;
    int min, temp;
    int array_size = numbers.length;

    for (i = 0; i < array_size - 1; i++) {
      min = i;
      for (j = i + 1; j < array_size; j++) {
        if (numbers[j< numbers[min])
          min = j;
      }
      temp = numbers[i];
      numbers[i= numbers[min];
      numbers[min= temp;
    }
  }

  public static void main(String[] args) {
    int[] a = 4731582};
    sort(a);
    for (int i = 0; i < a.length; i++)
      System.out.print(a[i"  ");
  }
}

효율성#

selection.jpg

Add new attachment

Only authorized users are allowed to upload new attachments.

List of attachments

Kind Attachment Name Size Version Date Modified Author Change note
jpg
selection.jpg 27.9 kB 1 14-Jul-2007 21:34 DongGukLee
« This page (revision-2) was last changed on 14-Jul-2007 23:16 by DongGukLee