[알고리즘] 자바에서의 선택 정렬

[알고리즘] 자바에서의 선택 정렬

선택 정렬(Selection Sort)

- 다음과 같은 순서를 반복하며 정렬하는 알고리즘 이다.

1. 주어진 데이터 중, 최소값을 찾는다.(배열 전체를 둘러보며 최소값을 찾는다.)

* 매 반복을 수행하며 최소값을 찾을 때마다 배열 끝까지 찾아가며 데이터를 비교해봐야 한다.

2. 해당 최소값을 데이터 맨 앞에 위치한 값과 교체한다.

3. 맨 앞의 위치(최소값) 을 뺀 나머지 데이터를 동일한 방법으로 반복한다.

자바 코드로 직접 구현해보자.

- SelectionSort.java

public class SelectionSort { private int[] array; public SelectionSort(int[] array) { this.array = array; } public int[] selectionSort() { for(int i = 0; i < this.array.length - 1; i++) { int lowest = i; for(int index = i + 1; index < this.array.length; index++) { if(this.array[lowest] > this.array[index]) lowest = index; } // 최소값을 찾은 이후 기준 인덱스와 위치를 바꿔준다. int temp = this.array[lowest]; this.array[lowest] = this.array[i]; this.array[i] = temp; } return this.array; } }

코드가 제대로 동작하는지 확인하기 위한 main 코드는 다음과 같다.

- SelectionSort_main.java

import java.util.Arrays; import java.util.Random; public class SelectionSort_main { public static void main(String[] args) { int[] array = new int[10]; Random random = new Random(); for(int i = 0; i < array.length; i++) { array[i] = random.nextInt(100); } SelectionSort sortArray = new SelectionSort(array); int[] resultArray = sortArray.selectionSort(); Arrays.stream(resultArray).forEach(x -> System.out.print(x + " ")); } }

선택 정렬 알고리즘 분석

- 버블 정렬, 삽입 정렬과 같이 2중첩 반복문을 활용하기 때문에 시간복잡도는 O(n^2) 이다.

- 실제로 상세하게 계산하면 n * (n - 1) / 2

from http://evan-development.tistory.com/131 by ccl(A) rewrite - 2021-11-30 22:02:13