1.
선택 정렬(selection sort)란?
•
다음과 같은 순서를 반복하여 정렬하는 알고리즘
1.
주어진 데이터 중, 최소값을 찾음
2.
해당 최소값을 데이터 맨 앞에 위치한 값과 교체함
3.
맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복함
2.
어떻게 코드로 만들까
간단한 로직에 집중해서, 각각 데이터가 저장되어 있는 배열이 있다고 가정
•
데이터가 두 개 일때
◦
예: dataList = [9, 1]
▪
dataList[0] > dataList[1] 이므로 dataList[0] 값과 dataList[1] 값을 교환
•
데이터가 세 개 일때
◦
예 : dataList = [9, 1, 7]
▪
처음 한번 실행하면 : 1, 9 ,7
▪
두번 째 실행하면 : 1, 7, 9
•
데이터가 네 개 일떄
◦
예: dataList = [9, 3, 2, 1]
▪
처음 한번 실행하면 1, 3, 2, 9
▪
두번째 실행하면 1, 2, 3, 9
▪
세번째 실행하면 변화 없음
3.
알고리즘 구현
1. for(int stand = 0; stand < dataList.size()-1;stand++)로 반복
2. lowest = stand로 놓고
3. for(int index = stand + 1; index < dataList.size();index++)로 stand 이후부터 반복
- 내부 반복문 안에서 dataList[lowest]>dataList[index] 이면,
- lowest = num
4. dataList[lowest]와 dataList[index]
Java
복사
import java.util.ArrayList;
import java.util.Collections;
public class SelectionSort {
public ArrayList<Integer> sort(ArrayList<Integer> dataList){
int lowest;
for(int stand = 0; stand<dataList.size()-1; stand++){
lowest = stand;
for(int index = stand + 1; index < dataList.size(); index++){
if(dataList.get(lowest) > dataList.get(index)){
lowest = index;
}
Collections.swap(dataList, lowest, stand);
}
return dataList;
}
}
Java
복사