5. 선택 정렬 Selection Sort (Java)

Goal

 - 선택 정렬 알고리즘 이해

 - 선택 정렬 알고리즘 C언어 및 Java언어 구현  

 - 선택 정렬 알고리즘의 특징

 - 선택 정렬 알고리즘 시간복잡도 이해 

 

1. 선택 정렬 ( Selection sort ) 알고리즘 이해

 

 - 오름차순을 기준으로 정렬 

 - 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘

  -> 첫 번째 순서에는 첫 번째 위치에 가장 최솟값을 넣는다.

  -> 두 번째 순서에는 두 번째 위치에 남은 값 중에서의 최솟값을 넣는다.

  -> ... 반복

- 선택 정렬 알고리즘의 구체적인 이해

 -> 선택 정렬은 첫 번째 자료를 시작으로 자료크기의 - 1까지 값을 key변수에 저장하는 반복문과, 첫 번쨰 자료의 오른쪽 자료부터 마지막 자료까지 차례대로 비교하는 이중 반복문을 시행한다. 비교하는 과정에서 key값이 비교하는 값보다 클 경우 key값에 비교하는 값의 index를 저장함으로서 key값에는 제일 작은 값의 index가 유지되도록 반복수행한다.  반복이 끝난 후 i값과 key값이 같다면 최소값이 자기 자신이라는 의미기 때문에 자료 이동을 하지 않고, 최소값의 변동이 있었다면 자료의 이동을 수행한다. 자료 이동은 하나의 메서드로 구현하며, 값을 바꿔주기 위한 temp함수에 첫 번째 값을, 첫 번째 값에는 최소값이 와야 하기 때문에 반복 수행과정에서 최소값을 유지햔 key값을 설정한다. 그리고 key값에 해당하는 자리에는 기존의 첫번째에 있던 값(temp)을 설정하여 이동을 마무리 한다. 

 - > 1회전을 수행하고 나면 가장 작은 값의 자료가 맨 앞에 오게 되므로 그 다음 회전에서는 두 번째 자료를 가지고 비교함. 마찬가지로 3회전에서는 세 번째 자료를 정렬함.

2.  선택 정렬 알고리즘 C언어 및 Java언어 구현  

 

2-1 C언어

# include <stdio.h>
# define SWAP(x, y, temp) ( (temp) = (x), (x) = (y), (y) = (temp) )
# define MAX_SIZE 5

//선택 정렬 

void selection_sort(int list[], int n){
  int i, j, least, temp;
  
  // 마지막 숫자는 자동으로 정렬되기 때문에 (숫자 개수 -1) 만큼 반복한다.
  for(i = 0; i < n-1; i ++){
    least = i;
    // 최솟값을 탐색한다.
    for(j=i + 1; j < n; j++){
      if(list[j] < list[least])
        lesast = j;
    }    
    // 최솟값이 자기 자신이면 자료 이동을 하지 않는다.
    if(i != least){
      SWAP(list[i], list[least], temp);
    }
   }
  }
  
  void main(){
    int i;
    int n = MAX_SIZ, , E, ;
    int list[n] = {8, 5, 6, 2, 4};
    
    // 선택 정렬 수행
    selection_sort(list, n);
    
    // 정렬 결과 출력
    for (i = 0; i < n; i++){
      printf("%d\n", list[i]));
    }
  }

 

2-2 Java

 - SWAP함수 써서 구현해보기! 

package inflearn.chapter1.sort;

import java.util.Arrays;

public class SelectionSortImplement {

	public static void main(String[] args) {
		
		int[] arrNum = {8, 5, 6, 2, 4};
		selectionSort(arrNum);
		
		for(int i = 0; i < arrNum.length; i++){
		    System.out.printf("%d, ", arrNum[i]);
		}

		

	}
	
	static void selectionSort(int[] list) {
	    int indexMin, temp;

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

	
}
	  

 

3. 선택 정렬 알고리즘의 특징

 - 장점 : 자료 이동 횟수가 미리 결정된다.
 - 단점 : 안정성을 만족하지 않는다. 즉, 값이 같은 레코드가 있는 경우에 상대적인 위치가 변경될 수 있다.

 

4. 선택 정렬 알고리즘 시간복잡도 이해 

 - 비교 횟수

  -> 두 개의 for 루프의 실행 횟수
  -> 외부 루프: (n-1)번
  -> 내부 루프(최솟값 찾기): n-1, n-2, … , 2, 1 번
 - 교환 횟수
  -> 외부 루프의 실행 횟수와 동일. 즉, 상수 시간 작업
  -> 한 번 교환하기 위하여 3번의 이동(SWAP 함수의 작업)이 필요하므로 3(n-1)번

 - T(n) = (n-1) + (n-2) + … + 2 + 1 = n(n-1)/2 = O(n^2)

 

 

* 내용 참고

( https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html )

- 자바에서 swap함수를 사용하기 위해서는 CBR, CBV 개념을 잘 숙지해야 한다

( https://re-build.tistory.com/3 )