선택정렬(Selection Sort)

https://visualgo.net/en/sorting?slide=8

가장 작은 값을 선택한다고 해서 선택정렬이라고 한다.

배열이 있을때 배열을 순회하면서 가장 작은 값과 인덱스를 변수에 저장한다. 저장된 인덱스를 사용해서 가장 작은 값과 0번 인덱스의 값과 스왑한다.
그 다음 순회에서는 1번 인덱스부터 탐색해서 가장 작은 값을 찾고 1번 인덱스의 값과 스왑한다
그 다음 순회에서는 2번 인덱스부터 탐색해서 가장 작은 값을 찾고 2번 인덱스의 값과 스왑한다
반복~~

시간복잡도는 버블정렬과 같이 O(N^2)

장점
쉽다.

단점
불안정 정렬( 같은 원소가 자리바꿈 일어난다)

public class SelectionSort {

    private ArrayList<Integer> list;

    SelectionSort()
    {
        list = new ArrayList();
    }

    void Add(Integer value)
    {
        list.add(value);
    }

    void Sort()
    {
        int min = Integer.MAX_VALUE;
        int minidx = 0;
        int temp = 0;
        for(int i = 0; i < list.size()-1; ++i)
        {
            for(int j = i; j < list.size(); ++j)
            {
                if(min > list.get(j))
                {
                    min = list.get(j);
                    minidx = j;
                }
            }

            temp = list.get(i);
            list.set(i, list.get(minidx));
            list.set(minidx, temp);
            min = Integer.MAX_VALUE;
        }
    }

    @Override
    public String toString() {
        return "SelectionSort{" +
                "list=" + list +
                '}';
    }
}

public class SelectionSortTest {
    public static void main(String[] args) {

        SelectionSort ss = new SelectionSort();

        ss.Add(10);
        ss.Add(9);
        ss.Add(8);
        ss.Add(7);

        ss.Sort();

        System.out.println(ss);
    }
}

CS공부하면서 복습겸 다시 짜봄

public class Main {
    public static void main(String[] args) {

        int[] arr = {20, 10, 6, 5, 2};

        for (int i = 0; i < arr.length; i++) {
            int idx = 0;
            int value = Integer.MAX_VALUE;
            for (int j = i; j < arr.length; j++) {

                if(value > arr[j]){
                    idx = j;
                    value = arr[j];
                }

            }
            int temp = arr[i];
            arr[i] = value;
            arr[idx] = temp;
        }

        for(int i : arr){
            System.out.println(i);
        }
    }
}

public class Main {
    public static void main(String[] args) {

        int[] arr = {20, 10, 6, 5, 2};

        int counter = 0;

        for (int i = 0; i < arr.length; i++) {
            int minidx = i;
            for (int j = i+1; j < arr.length; j++) {

                counter++;
                if(arr[minidx] > arr[j]){
                    minidx = j;
                }

            }
            if(i != minidx){
                int temp = arr[minidx];
                arr[minidx] = arr[i];
                arr[i] = temp;
            }
        }

        for(int i : arr){
            System.out.println(i);
        }

        System.out.println("비교횟수: " +  counter);
    }
}