티스토리 뷰
반응형
소개
- 배열을 조회하면서 현재 위치에 들어갈 값 (남은 숫자들 중 가장 크거나 작은 값) 을 찾아 정렬한다.
과정

코드
- 현재 위치 i 값과 배열의 나머지 모든 값을 비교하여 가장 작은 값을 가진 인덱스 idx 를 j로 갱신한다.
- 두 번째 for문이 끝나면 i와 idx 위치의 값을 바꾼다.
public static void main(String[] args) {
int[] nums = { 8, 5, 2, 6, 9, 4, 1, 3, 0, 7 };
int len = nums.length;
for (int i = 0; i < len - 1; ++i) {
int minIdx = i;
for (int j = i + 1; j < len; ++j) {
if (nums[minIdx] > nums[j]) {
minIdx = j;
}
}
if (arr[minIdx] < arr[i]) {
Swap(nums, minIdx, i);
}
}
}
결과

계산 복잡도
Time Complexity : for문 두 개가 지배하며, (N−1)+(N−2)+...+1=(N−1)∗(N)2
- Best : O(N2)
- Average : O(N2)
- Worst : O(N2)
Space Complexity : O(1)
반응형
'Algorithm > Sort' 카테고리의 다른 글
힙 정렬 (Heap Sort) (2) | 2020.12.24 |
---|---|
병합 정렬 (Merge Sort) (0) | 2020.12.24 |
셸 정렬 (Shell Sort) (0) | 2020.12.24 |
삽입 정렬 (Insertion Sort) (0) | 2020.12.24 |
버블 정렬 (Bubble Sort) (0) | 2020.12.24 |