정렬(sort) : Selection sort(선택정렬)

치타·2020년 10월 15일
0

Java

목록 보기
5/6

정렬에는 많은 종류의 정렬이 있다.
다양한 정렬을 시각적으로 볼 수 있는 사이트가 있다.
https://www.toptal.com/developers/sorting-algorithms

정렬

정렬은 데이터를 순차적으로 배치할 수 있는 과정이다.
[오름차순(ascending) / 내림차순(descendeing)] 많이 들어봤을 것이다.
최신순, 별점순, 이름순, 성적순, 번호순 등 다양한 정렬이 있다.

프로그래밍에서 정렬은 많이 쓰이고 있다.

1. Selection Sort (선택정렬)

단순하게 정렬할 수 있는 정렬이다.
단순하다는 것은 곧 느리다는 것을 말한다.

선택정렬은 전체에서 최소값을 찾아서 앞으로 세운다.
전체 데이터를 한번 훑어 최소값을 찾아서 맨 앞으로 배치하고,
전체 데이터를 두번 훑어 최소값을 찾아서 앞으로 배치하고,
전체 데이터를 세번 훑어 최소값을 찾아서 앞으로 배치하고
...
똑같은 패턴으로 최소값을 찾아 끝까지 정렬하는 것이 바로 선택정렬이다.

선택정렬을 구현하려면 최소값을 찾는 방법을 알아야 한다.

최소값 구하기

  1. 최소값을 찾을 데이터 준비
int[] data = new int[] {30, 50, 20, 10, 40};
  1. 최소값을 알기 위한 변수 준비
    (값)
int minValue = data[0];

(값의 위치)

int minIndex = 0;
  1. 전체 데이터를 배열에 담긴 마지막까지 비교하여 최소값을 찾는다.
for(int i = 1; i < data.length; i++) {
	if(minValue > data[i] {
    	minValue = data[i];
        minIndex = i;
        }
}

최소값의 위치는 minIndex에 담겼고,
최소값의 값은 minValue에 담겼다.

최소값을 구해봤다면, 이제 선택정렬을 해볼차례다.

값 30,50,20,10,40 을 선택정렬해라.
단, 값이 추가되거나 변경되어도 정렬이 되도록 해야한다.
tip_ 선택정렬은 최소값을 찾아서 정렬하는 것이기 때문에,
최소값을 찾는 구문을 먼저 생성한 뒤
다음에 해야할 것들을 생각해보자.

int[] data = new int[] { 30, 50, 20, 10, 40 }; // 1. 배열생성

//3. 배열 안에서 최소값 찾기
int minIndex = 0; // 최소값을 알기 위한 변수 준비

for(int i = 1; i < data.length; i++) {
	if(data[minIndex] > data[i]) {
    	minIndex = i;
    }
}
//minIndex 에 넣은 최소값을 data[0] 옮긴다.
    int temp = data[minIndex];
    data[minIndex] = data[0];
    data[0] = temp;


//2. 출력구문
for(int i = 0; i < data.length; i++) {
	System.out.println(data[i]); }
    
// 출력 : 10, 50, 20, 30, 40  => 30과 10의 자리가 바뀌었다.

자, 이제 나머지 값들도 정렬을 해보자.

int[] data = new int[] { 30, 50, 20, 10, 40 };

int minIndex = 1; // 0 -> 1로 변경

for(int i = 2; i < data.length; i++) { // i = 1 -> i = 2로 변경
	if(data[minIndex] > data[i]) {
    	minIndex = i;
    }
}
//minIndex 에 넣은 최소값을 data[1] 옮긴다.
    int temp = data[minIndex];
    data[minIndex] = data[1]; // data[0]에서 data[1]로 변경
    data[1] = temp;  //data[0]에서 data[1]로 변경


//출력구문
for(int i = 0; i < data.length; i++) {
	System.out.println(data[i]); }
    
// 출력 : 30, 10, 20, 50, 40  => 50과 10의 자리가 바뀌었다.

minIndex를 0부터 3까지 반복하면 정렬이 되겠다!

int[] data = new int[] { 30, 50, 20, 10, 40 };

for(int j = 0; j < data.length-1; j++) {
int minIndex = j; // 0 -> j 반복문으로 변경

for(int i = j+1; i < data.length; i++) { // i = 1 -> i = j+1로 변경
	if(data[minIndex] > data[i]) {
    	minIndex = i;
    }
}
//minIndex 에 넣은 최소값을 data[j] 옮긴다.
    int temp = data[minIndex];
    data[minIndex] = data[j]; // data[0]에서 data[j]로 변경
    data[j] = temp;  //data[0]에서 data[j]로 변경
}

//출력구문
for(int i = 0; i < data.length; i++) {
	System.out.println(data[i]); }
    
// 출력 : 10, 20, 30, 40, 50

이로써 선택정렬이 끝이났다...!!

profile
iOS 주니어개발자

0개의 댓글