정렬 알고리즘은 2가지 방법으로 나뉘어진다.
int[] arr = {7,6,2,4,3,9,1}
private static void sort(int[] arr){
for(int i=0; i<arr.length; i++){
int standard = i;
for(int j = i+1; j<arr.length; j++{
if(arr[j] <arr[standard]) standard = j;
}
//자리 바꾸는 과정
int temp = arr[standard];
arr[standard] = arr[i];
arr[i] = temp;
print(arr);
}
}
private static void print(int[] arr){
for(int i=0; i<arr.length; i++){
System.out.println(arr[i]+" ");
}
System.out.println();
}
// 단계별 결과.
1단계 : 1 6 2 4 3 9 7
2단계 : 1 2 6 4 3 9 7
3단계 : 1 2 3 4 6 9 7
4단계 : 1 2 3 4 6 9 7
5단계 : 1 2 3 4 6 9 7
6단계 : 1 2 3 4 6 7 9
7단계 : 1 2 3 4 6 7 9
"기준이 되는 수와 나머지 수를 비교해서 가장 작은 수를 앞으로 계속 보내는 정렬"
간단하지만, 매우 비효율적.
1단계 -> N개의 원소 비교
2단계 -> N-1개의 원소 비교
...
비교 횟수 = n(n-1)/2가 된다.
시간 복잡도는 O(N^2)가 된다.
최악, 최선, 평균 모두 시간 복잡도가 O(N^2)가 된다.
공간 복잡도는 주어진 배열 안에서 교환을 통해 정렬이 수행되므로 O(N)이다.