선택 정렬(Selection Sort) 알고리즘

선택 정렬(Selection Sort) 알고리즘이란?

가장 작은 데이터를 찾아 가장 앞 데이터와 교환하는 알고리즘

 

사용 방법

1. 아직 정렬하지 않은 부분에서 가장 작은 키의 값을 선택한다.

2. 가장 작은 값과, 아직 정렬하지 않은 부분의 첫 번째 요소를 교환한다.

 

자바에서 구현하기

package sort;

import java.util.Random;

public class selectionSort {
	
	//두 인접한 요소의 값을 교환한다.
	static void swap(int[] a, int idx1, int idx2) {
		int tmp = a[idx1];
		a[idx1] = a[idx2];
		a[idx2] = tmp;
	}

	//(단순) 선택 정렬
	static void selectionSort(int[] a) {
		int n = a.length;
		for(int i=0; i<n-1; i++) {
			int min = i;	//아직 정렬되지 않은 부분에서 가장 작은 요소의 인덱스를 기록.
			for(int j=i+1; j<n; j++) {
				if(a[j]<a[min]) {	//a[j]의 값보다 a[min]의 값이 크다면
					min=j;			//가장 작은 요소의 인덱스를 j로 바꾼다.
				}
				swap(a, i, min);	//아직 정렬되지 않은 부분의 첫 요소와 가장 작은 요소를 교환.
			}
		}
	}
	
	public static void main(String[] args) {
		Random r = new Random();
		int[] array = new int[r.nextInt(5)+5];
		
		for(int i=0; i<array.length; i++) {
			array[i] = r.nextInt(99)+1;
			System.out.printf("%3d",array[i]);
		}
		System.out.println();
		
		selectionSort(array);
		
		for(int i=0; i<array.length; i++) {
			System.out.printf("%3d",array[i]);
		}
	}
}

 

lktprogrammer.tistory.com/26

01 정렬 알고리즘 - 선택 정렬(Selection Sort)