본문 바로가기
Develop/Algorithm

선택 정렬 ( select sort)

by 코딩의성지 2021. 7. 4.

오늘부터 간단하게 정렬 알고리즘을 정리해두려고 한다.

 

첫번째는 알고리즘 수업을 들을 때 맨 처음 배우는 선택 정렬 알고리즘이다.

 

이 알고리즘은 아래의 방식을 따라 수행된다.

 

1. 아직 정렬 안된 리스트 중 가장 앞의 원소를 최소값 or 최댓값으로 설정

2. 가장 앞에 원소를 제외한 나머지 원소를 차례로 비교하여 최솟값 or 최댓값을 찾아감

3. 리스트를 끝까지 비교하여 찾은 최소값을 가장 앞의 원소와 교환

4. 정렬이 다될때까지 1~3 반복

 

선택 정렬의 경우 데이터를 교환하는 횟수는 적지만 결국 비교하는 횟수가 많아서 대용량 데이터에서는 비효율적이다.

시간 복잡도는 O(N²) 을 따른다.

 

예제 소스 코드

class SelectSort {
    public static void main(String[] args) {
        int[] data = {3,5,-5,1,4,0};

        int[] result = selectionSort(data);

        for(int num : result) {
            System.out.println(num);
        }
    }
    public static int[] selectionSort(int[] data) {
        int result[] = data;
        int min,temp;

        for(int i=0; i<result.length-1; i++){
            min = i;
            for(int j=i+1; j<result.length; j++){
                if(result[min] > result[j]){
                    min = j;
                }
            }
            temp = result[min];
            result[min] = result[i];
            result[i] = temp;
        }

        return result;
    }


}
반응형

'Develop > Algorithm' 카테고리의 다른 글

재귀 함수 정리  (0) 2021.07.27
병합 정렬 (Merge Sort)  (0) 2021.07.06
퀵 소트 (Quick Sort)  (0) 2021.07.05
버블 정렬 (Bubble Sort)  (0) 2021.07.05
삽입 정렬 (Insertion Sort)  (0) 2021.07.04

댓글