JAVA - 선택정렬(Selection Sort)
✅ 선택정렬 ( Selection Sort )
선택정렬은 거품정렬과 마찬가지로 O(n^2)의 시간복잡도는 가지고 구현이 간단하다.
하지만 제일큰 원소를 뒤로보내며 끝인덱스부터 정렬하는 방식인 거품정렬과 다르게 제일 앞인덱스부터 정렬한다.
데이터를 '비교'하고 그중 가장 최소값을 가진 원소와 위치를 '교환'하기 때문에 교환횟수가 적다.
마찬가지로 데이터외의 추가공간을 필요로 하지않기때문에 '제자리정렬' 이기도 하다.
📌 정렬과정
1. 초기데이터배열이 주어진다.
2. 제일 첫 인덱스부터 배열의 끝까지 돌며 최소값을 가진 인덱스를 찾는다.
3. 최소값을 가진 인덱스와 첫인덱스의 위치를 교환한다.
4. 제일첫 인덱스는 정렬된 상태이므로 다음인덱스를 최소값과 교환하며 반복해나간다.
초기 데이터배열이 주어진다.
1. 0번째 인덱스의 위치(0)를 min이라는 변수에 담아두었다.
2. 이후 최소값을 비교하며 값이 더 작다면 작은값을 가진 인덱스의값을 첫인덱스의값과 교환한다.
3. 최소값1을 가진 인덱스와 첫인덱스의 위치를 교환한다.
1. 첫반복에서 정렬된 원소의 다음 인덱스부터 반복한다.
2. 5와 9를 비교해 5가 최소값인상태
3. 5와 4를 비교해 4가 최소값이 되었다.
4. 4와 7을 비교해 4가 최소값인상태를 유지하고
5. 4와 3을 비교해 3이 최소값이 되었다.
6. 최소값3을 가진 인덱스와 정렬된 다음인덱스의 위치를 교환한다
위의 과정에서 정렬된 인덱스들은 비교하지 않는다
🚩 배열의길이가 6인데 5번을 반복했을경우 마지막인덱스의 값은 최대값이 있다는 말이므로
마지막반복을 실행할 필요가 없다.
📌 코드구현
package sort;
public class SelectionSort {
public static void main(String[] args) {
int[] data = {7,5,9,4,1,3};
for(int i=0;i<data.length-1;i++) {
int minIdx = i; // 최소값의 인덱스를 담고있을 변수
for(int j=i+1;j<data.length;j++) {
if(data[j]<data[minIdx]) {
minIdx=j;
}
}
int temp=data[i];
data[i]=data[minIdx];
data[minIdx]=temp;
for(int x=0;x<data.length;x++) {
System.out.print(data[x]);
}
System.out.println();
}
}
}
🚩 최소값의 인덱스를 기억하고있을 변수 minIdx는 인덱스의 위치를 기억하지만
값변경을 할때는 해당배열의 minIdx를 사용해 안에들어있는 값을 변경한다.
출력결과
📌 선택정렬 정리
선택정렬알고리즘은 가장 기초적인 알고리즘이며 같은 시간복잡도를 가진 거품정렬, 삽입정렬과 함께 배운다.
성능상 좋지못하더라도 기초가 중요하듯이 이를 이해하고 익혀야 다음 단계의 정렬들도 이해할 수 있을것이다.
선택정렬은 이전 거품정렬과 다르게 실제로 값을 교환하는 횟수가 상당히 적다.
🟢 장점
- 추가메모리 소비가 작다.
- 구현이 매우 간단하다.
- 값을 교환하는 횟수가 적다.
🔴 단점
- 시간복잡도가 O(n^2)이며 안정정렬이아니다.
-참고
https://st-lab.tistory.com/168?category=892973