Java-알고리즘 ( selection sort )

1. 선택 정렬 (selection sort) 란?

• 다음과 같은 순서를 반복하며 정렬하는 알고리즘
  1. 주어진 데이터 중, 최솟값을 찾음
  2. 해당 최소값을 데이터 맨 앞에 위치한 값과 교체함
  3. 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복함

 

2. 선택 정렬을 어떻게 구현하면 좋을까?

• 데이터가 세 개 일떄
  • 예: dataList = [9, 1, 7]
    • 처음 한번 실행하면 1, 9, 7 이 됨
    • 두 번쨰 실행하면 1, 7, 9가 됨
• 데이터가 네 개 일떄
  • 예: dataList = [9, 3, 2, 1]
    • 처음 한번 실행하면 1, 3, 2, 9 가 됨
    • 두 번쨰 실행하면 1, 2, 3, 9 가 됨
    • 세 번째 실행하면, 변화 없음

 

3. 알고리즘 구현

// src/com.company/Sort/SelectionSort.java

package com.company.Sort;


import java.util.ArrayList;
import java.util.Collections;

public class SelectionSort {
    public ArrayList<Integer> sort(ArrayList<Integer> dataList) {
        // 최솟값의 인덱스를 저장하는 변수 선언
        int lowest;
        for(int idx1 = 0; idx1 < dataList.size() - 1; idx1++) {
            // idx1 부터 최솟값을 찾아서 최솟값을 idx1이 가리키는 인덱스와 바꾸는 코드
            lowest = dataList.get(idx1);
            for(int compareIdx = idx1 + 1; compareIdx < dataList.size(); compareIdx++) {
               if(dataList.get(lowest) > dataList.get(compareIdx)) {
                   lowest = compareIdx;
               }
           }
            // swap
            Collections.swap(dataList, lowest, idx1);
        }
        return dataList;
    }
}

// src/com.company/Main.java

package com.company;

import com.company.Sort.BubbleSort;
import com.company.Sort.SelectionSort;

import javax.swing.plaf.basic.BasicInternalFrameTitlePane;
import java.util.ArrayList;

public class Main {

    public static void main(String[] args) {
        ArrayList<Integer> testData = new ArrayList<Integer>();

        for(int i = 0; i < 100; i++) {
            testData.add((int)(Math.random() * 100));
        }
        SelectionSort sSort = new SelectionSort();
        sSort.sort(testData);
        System.out.println(testData);
    }
}

4. 알고리즘 분석

• 반복문이 두 개 O(n^2)
  • 실제로 상세하게 계산하면, n * (n - 1) / 2