#013 선택 정렬

# 문제)

아래와 같이 정렬되지 않은 배열이 있을때 선택 정렬을 사용하여 오름차순 정렬하여라.

<초기>

5

2

4

3

1

선택정렬이란 오름차순 정렬의 경우,

처음 위치부터 시작하여 최소값을 찾아 첫 인덱스 값과 최소값을 swap 한다.

다음 단계에서는 두번째 인덱스부터 시작하여 최소값이 있는 인덱스를 찾아 swap한다.

계속 반복.

*붉은 색은 최소값 인덱스

<1회전>

5

2

4

3

1

5

2

4

3

1

5

2

4

3

1

5

2

4

3

1

1

2

4

3

5

<2회전>

1

2

4

3

5

1

2

4

3

5

1

2

4

3

5

swap 일어나지 않음.

<3회전>

1

2

4

3

5

1

2

4

3

5

1

2

3

4

5

<4회전>

1

2

3

4

5

swap 일어나지 않음.

package dataStructure.sort.selection;

public class SelectionSort {

   

    private int[] array;

    private int size;

    private int maxSize = 100;

   

    public SelectionSort(int maxSize) {

        // TODO Auto-generated constructor stub

        this.maxSize = maxSize;

        this.array = new int[this.maxSize];

    }

   

    public void add(int value) {

        if( size >= maxSize ) {

            System.out.println("error. max size.");

            return;

        }

        array[size++] = value;

    }

   

    public void add(int...values) {

        if( (size + values.length) >= maxSize ) {

            System.out.println("error. max size.");

            return;

        }

        for(int i=0; i< values.length; i++) {

            array[size++] = values[i];

        }

    }

   

   

    public void sort() {

        int minValueIndex = 0;

        for(int i=0; i<size; i++) {

            minValueIndex = i;

            for(int j=i; j<size; j++) {

                if(array[minValueIndex] > array[j]) {

                    minValueIndex = j;

                }

            }

            if(minValueIndex != i) {

                swap(minValueIndex, i);

            }

        }

    }

   

    private void swap(int prior, int next) {

        int temp = array[prior];

        array[prior] = array[next];

        array[next] = temp;

    }

   

    @Override

    public String toString() {

        // TODO Auto-generated method stub

        StringBuilder result = new StringBuilder();

        result.append("[");

        int i = 0;

        while(i < size) {

            result.append(array[i]);

            if(i != (size - 1) ) {

                result.append(",");

            }

            i++;

        }

        result.append("]");

        return result.toString();

    }

   

    public static void main(String[] args) {

        // TODO Auto-generated method stub

        SelectionSort selection = new SelectionSort(10);

        selection.add(5,2,4,3,1);

        System.out.println(selection);

        selection.sort();

        System.out.println(selection);

    }

}

버블정렬보다 swap이 발생하는 횟수가 적다.

*만약 정렬되어 있는 경우는?