이 글은 다음의 글을 참고해서 작성되었습니다.
[알고리즘] 선택 정렬 - Selection Sort (Python, Java)
Selection Sort
Sorting Algorithms Animations
선택정렬~!
참고란의 맨 마지막링크를 보면 정렬 과정을 자료의 상태에 따라 애니메이션으로 보여주는 사이트가 있는데, 선택정렬의 속도가 가장 느리다.
선택정렬이란?
선택정렬은 데이터 배열에서 가장 작은 데이터를 선택하여 앞으로 보내는 정렬이다.
우리가 일상에서 어떤 것을 정렬한다고 할 때 쉽게 떠올리는 정렬방법과 비슷하다고 생각하면 기억하기 쉽다.
선택정렬의 정렬과정 및 특징
[7,3,9,8,2] #라는 배열이 있다고 했을 때,
전체 배열을 훑으며 작은 가장 작은 값을 찾아낸다.
인덱스 4번에 있는 2의 값이 가장 작으므로 2와, 7의 위치를 바꿔준다. -> [2, 3, 9, 8, 7]
가장 작은 수가 인덱스 0에 있으므로 인덱스 0을 제외하고 가장작은 수를 선택해 1번 인덱스와 교환해준다. 예시의 경우 두 번째로 작은 3이 이미 1번 인덱스에 있으므로 교환은 일어나지 않는다. -> [2, 3, 9, 8, 7]
.
.
.
위의 과정을 반복하면 [2, 3, 7, 8, 9] 순서대로 정렬이 완료된다.위의 예시를 통해 알 수 있 듯, 선택정렬은 배열의 맨 앞 부분부터 하나씩 채워나가게 된다. 뒤에있는 인덱스로 갈수록 비교범위가 하나씩 줄어드는 특성을 갖는다.
입력배열이 정렬되어있거나 아니거나 연산량이 동일하기 때문에 최적화 여지가 적어, 성능이 떨어지는 편이다.
가장 구현이 쉬운 알고리즘이라 알고리즘을 처음 접하는 초보자가 구현해보기 쉬운 알고리즘으로 유명하다.
python으로 선택정렬 구현하기
def selection_sort(arr):
for i in range(len(arr)-1):
min)idx = i
for j in range(i+1, len(arr)):
if arr[j] < arr[min_idx]:
min_idx =j
arr[i], arr[min_idx] = arr[min_idx], arr[i]java로 선택정렬 구현하기
public class Selection {
public static void sort(int[] arr) {
for (int i = 0; i < arr.length-1; i++) {
int minIdx = i;
for (int j = i+1; j < arr.length; j++) {
if (arr[j] < arr[minIdx])
minIdx = j;
}
swap(arr, i, minIdx);
}
}
private static void swap(int[] arr, int a, int b) {
int tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
}
