자료구조/정렬
선택정렬 (selection sort) 을 간단하게 알아보자.
이재빵
2021. 1. 1. 02:22
728x90
선택 정렬을 간단하게 설명하면?
가장 작은 숫자를 선택하는 방식으로 정렬을 진행하기 때문에 선택 정렬!
- 배열의 최솟값을 찾아 첫 번째 인덱스부터 차례대로 그 자리에 스왑 합니다.
- 최솟값이 들어간 배열은 더 이상 건들지 않습니다. 이미 정렬이 된 인덱스들이기 때문이죠.
- 정렬이 안된 인덱스들 중에서 다시 최솟값을 알아내 정렬이 된 인덱스 다음 인덱스에 넣습니다.
구현 과정
import java.util.*;
public class Main {
public static void main(String[] args) {
int[] A= {70, 20, 10, 80, 60, 90, 30, 40, 100, 50};
for(int i=0; i<A.length; i++) { //정렬 전 배열 출력
System.out.print(A[i]+" ");
}
System.out.println();
for(int i=0; i<A.length-1; i++) { // n-1까지 정렬하면 자동으로 n번째 인덱스는 정렬됨.
int min=i; // i를 최소값으로 가정.
for(int j=i+1; j<A.length; j++) { // i번째 인덱스를 최소값으로 가정하고 그 다음 인덱스부터 비교.
if(A[min]>A[j]) { // A[min]보다 작으면 j가 min이 된다.
min=j;
}
}
int temp=A[min];
A[min]=A[i];
A[i]=temp;
}
for(int i=0; i<A.length; i++) {
System.out.print(A[i]+" ");
}
}
}
시간 복잡도
- Worst : O(n^2)
- Average : O(n^2)
- Best : O(n^2)