선택정렬 (Selection Sort)
선택정렬은 배열중에 가장 작은 원소들을 왼쪽부터 채워나가면서 숫자를 정렬하는 방법입니다.
최소원소를 찾은 후
=> 최소원소를 맨 왼쪽원소와 교환(즉, 왼쪽부터 정렬된 원소로 채워집니다.)
=> 왼쪽원소를 제외하고 원소가 하나남을때 까지 이단계를 반복
선택정렬의 비교횟수를 구해보면
1단계 => n개의 원소 비교
2단계 => n-1 개의 원소 비교
3단계 => n-2 개의 원소 비교
....
를 하여 비교 횟수는
n(n-1) /2 가 됩니다.
즉, 시간복잡도는 O(n^2)이 됩니다.
for(i=0; i<num.length-1; i++) {
for (j=i+1;j<num.length;j++) {
if(num[i]>num[j]) { //오름차순
temp=num[i];
num[i]=num[j];
num[j]=temp;
}
}
}
버블정렬 (Bubble Sort)
배열을 순차탐색하여 i, i+1번째 요소를 비교하여 큰 것을 뒤로 이동 합니다.
위 과정이 1번 처리되는 경우 가장 큰 수가 배열 마지막에 위치 합니다.
다음 탐색부터는 마지막요소는 안해도 됩니다. ( 그래서 내부에 있는 for문은 arr.length - i 까지만 탐색)
public static void bubbleSort(int[] arr) {
for(int i = 0; i < arr.length; i++) {
for(int j = 0 ; j < arr.length - i - 1 ; j++) {
if(arr[j] > arr[j+1]) {
int temp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp;
}
}
}
}
출처
'알고리즘' 카테고리의 다른 글
[개념] 조합, 순열 + DFS,BFS (1) | 2020.01.16 |
---|---|
[개념] 그래프 이론 (0) | 2020.01.15 |
[개념] 피보나치 수열 알고리즘 (0) | 2020.01.10 |
Comparator<T> 인터페이스 - 정렬문제에서 자주 쓰이는 기법 (0) | 2020.01.05 |
[개념] KMP 알고리즘 (0) | 2020.01.04 |