Selection Sort(선택정렬)

사실 java에서는 sort가 제공되기 때문에 실제로 Selection sort를 사용할지는 알수 없지만 Selection, Bubble, quick Sort 는 확실하게 이해하고 코딩하고 싶어 작성하게 되었습니다.

 

목표

1) Selection Sort가 어떤식으로 순서를 바꾸는지를 이해

2) 해당 정렬의 방식에 맞는 Source Code 구현

3) 역순(오름차순, 내림차순)으로 나눠서 구현

 

1. Selection Sort란?

  - 각 데이터를 첫번째 데이터부터 마지막 데이터까지 전부 비교하여 정렬하는 것

  ex)      17   20   30   15   29
  1Pass   15   20   30   17   29
  2Pass   15   17   30   20   29
  3Pass   15   17   20   30   29
  4Pass   15   17   20   29   30

 

< 예시 >

 

Pass별 순차 정렬

 

2. 코드 설명

  1) 입력받은 배열의 크기를 int형 변수 length에 넣음

  2) 이중for문으로 전체의 내용을 비교(첫째 for문은 i부터 length-1까지, 둘째 for문은 i+1부터 length까지)

     - 전체를 순차적으로 모두 둘러볼수 있도록 해야함

  3) i의 값보다 작은 수를 만나면 자리를 바꾸며 진행

  4) 결과 값 int형 배열 arr을 return.

  5) 내림차순의 경우 조건문에서 부등호의 방향만 바꾸면 변경됨

 

3. 구현

package naver.insa8029.SortProject;

import java.util.Arrays;

public class SelectionSortClass {
	public int[] dataAscendingSort(int [] arr) {
		int length = arr.length;
		
		//오름차순 정렬
		System.out.println("====오름차순 selectionSort====");
		System.out.println("정렬 전 : " + Arrays.toString(arr));
		
		for(int i=0; i<length-1; i+=1) {
			for(int j=i+1; j<length; j += 1) {
				if(arr[i] > arr[j]) {
					int temp = arr[i];
					arr[i] = arr[j];
					arr[j] = temp;
				}
			}
            //Pass마다 데이터 확인
            //System.out.println(i + "Pass : " + Arrays.toString(arr));
		}
		return arr;
	}
	
	public int[] dataDescendingSort(int[] arr) {
		int length = arr.length;
		
		//내림차순 정렬
		System.out.println("====내림차순 selectionSort====");
		System.out.println("정렬 전 : " + Arrays.toString(arr));
		for(int i=0; i<length-1; i+=1) {
			for(int j=i+1; j<length; j += 1) {
				if(arr[i] < arr[j]) {
					int temp = arr[i];
					arr[i] = arr[j];
					arr[j] = temp;
				}
			}
            //Pass마다 데이터 확인
            //System.out.println(i + "Pass : " + Arrays.toString(arr));
		}
		
		return arr;
	}

}