[알고리즘] 선택정렬

 

 

1. 선택정렬의 개념

 

: 선택정렬은 제자리정렬의 알고리즘 중 하나이다.

 여기서 제자리 정렬이란, 입력 배열(정렬되지 않은 값들) 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법이며,
 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘이다.

 

 선택정렬은 해당 순서에 원소를 넣는 위치는 이미 정해져 있고,

 그 위치에 어떤 원소를 넣을지 선택하는 알고리즘이라고 할 수 있다.

 

 비효율적 정렬 방식은 시간복잡도 순으로 버블정렬 > 선택정렬 > 삽입정렬 세가지로 구분한다.

 

 

 

---

 

 

2. 선택정렬의 과정

 

1) 이론 설명(순서)

1. 주어진 배열에서 최솟값을 찾는다.
2. 그 값을 맨 처음에 위치한 값과 교환한다.
3. 2번에 해당하는 위치를 제외한 나머지 배열들을 같은 방법으로 교체한다.
4. 하나의 원소만 남을때까지 반복한다.

 

---

 

2) 사진 첨부

 

 : 이론을 시각적으로 이해하기 위한 사진을 아래에 첨부하였다.

 

위의 이론 설명과 같은 이치로 해석한다.

 

 

---

 

 

3. 구현

 

: 아래 코드는 위의 내용을 기반으로 하여 선택정렬을 구현한 것이다.

10개의 배열을 만들고, 그 안에 1~100까지의 랜덤수를 중복 없이 출력, 교환알고리즘을 이용해 내림차순 정렬 하였다.

 

package day004;

import java.util.Random;

public class Homework {

	public static void main(String[] args) {
		int [] data = new int [10];
		Random r = new Random();
		int i=0;

		// 10개의 배열에 100까지의 랜덤수 삽입(중복 없이)
		while(i<data.length) {
			data[i] = r.nextInt(100)+1;
			boolean flag = false;
			for(int j=0; j<i; j++) {
				if(data[i]==data[j]){
					flag = true;
					break;
				}
			}
			if(flag) {
				continue;
			}
			i++;
		}
		System.out.println("정렬할 원소 :");
		for(int v: data) {
			System.out.print(v + " ");
		}
		// 선택정렬
		for(int j=0; j<data.length-1; j++) {        
			int max = j;
			for(int a=j+1; a<data.length; a++) {
				if(data[a] > data[max]) {
					int tmp = data[a];
					data[a] = data[max];
					data[max] = tmp;
				}							
			}
		}
		System.out.println("\n정렬 결과 : ");
		for(int v: data) {
			System.out.print(v + " ");
		}
	}
}

 

오름차순의 경우 등호를 반대로 하면 된다.

 

 

 

 

* 코드 해석 *

첫번째 방 부터 시작할 index를 max라는 이름의 변수를 이용하여 가장 큰 값이라고 가정한다.

index[1]가 index[0](이면서 int max의 값)보다 크다면 max는 index[1]이다.

이 식을 배열-1번 반복한다. 원소 하나만 남을때 까지 반복 하면 되기 때문이다.