버블정렬 : 데이터의 인접 요소 끼리 비교하고, swap 연산을 수행하여 정렬하는 방식
선택정렬 : 대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하면서 정렬하는 방식
삽입정렬 : 대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬하는 방식
퀵정렬 : pivot(피벗)값을 선정해 해당 값을 기준으로 정렬하는 방식
병합정렬 : 이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬하는 방식
기수정렬 : 데이터의 자릿수를 바탕으로 비교해 데이터를 정렬하는 방식
시간복잡도는 O(n²)으로 다른 정렬 알고리즘보다 속도가 느린편이다
루프loop를 돌면서 인접한 데이터간의 swap 연산으로 정렬한다
한번 돌때 N번의 시간복잡도 발생. 이 행위를 N번 반복 = N X N = N²
만약 특정한 루프의 전체 영역에서 swap이 한 번도 발생하지 않았다면 그 영역 뒤에 있는 데이터가 모두 정렬됐다는 뜻이므로 프로세스를 종료한다 => 더 이상 정렬수행 x
간단하게 말해, 인접한 두 원소를 비교하여 큰 수를 계속하여 뒤로 보내는 방식
(오름차순으로 정렬하는 경우)
이 과정에서 이미 뒤로 보내진 수는 다시 정렬 여부를 확인해 줄 필요가 없기 때문에 한 번의 반복마다 교체를 확인하는 인덱스를 1씩 줄여주며 반복을 하는 구현 방법을 주로 사용한다
[장점]
1. 추가적인 메모리 소비가 작다
2. 구현이 쉽다
3. 안정정렬이 가능하다
[단점]
다른 정렬 알고리즘에 비해 교환 과정이 많이 많은 시간을 소비한다
public class 버블정렬 {
public static void main(String[] args) {
int[] arr = {5,3,1,2,4,10,8,7,9,6};
int temp;
// 한 번의 반복이 완료될 때마다 가장 큰 수는 배열의 가장 마지막 부분으로 밀리는 것이 보장
for(int i = arr.length-1; i>0; i--)
// 한 번의 반복마다 가장 뒤의 인덱스는 비교하지 않도록 반복문 설정
for (int j = 0; j < i; j++)
// 만일 앞의 수가 뒤의 수 보다 더 크다면 swap 연산
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
System.out.println(Arrays.toString(arr));
}
}하지만 각 라운드에서 비교수행을 할 때 원소가 교환되지 않는다면(swap 발생 x) 이는 이미 정렬된 데이터라는 의미이기 때문에 정렬을 종료하면 된다
즉, 각 라운드에서 비교수행을 했는지를 판단할 수 있는 변수를 하나 두면 된다
만약 boolean으로 스왑된 것은 true, 스왑되지 않은 것에 false를 두고
반복문이 다 돌았을때 정렬여부를 따져 break를 둔다면
정렬 된 경우 첫 라운드에서 탐색을 하고 바로 종료가 된다.
이렇게 변수를 둔 경우는 시간복잡도가 O(N)이라고 할 수 있다.
public class 버블정렬 {
public static void main(String[] args) {
int[] arr = {5,3,1,2,4,10,8,7,9,6};
int temp;
// 한 번의 반복이 완료될 때마다 가장 큰 수는 배열의 가장 마지막 부분으로 밀리는 것이 보장
for(int i = arr.length-1; i>0; i--) {
boolean swapped = false;
// 한 번의 반복마다 가장 뒤의 인덱스는 비교하지 않도록 반복문 설정
for (int j = 0; j < i; j++) {
// 만일 앞의 수가 뒤의 수 보다 더 크다면 swap 연산
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
// 비교했다면 true로 변경
swapped = true;
}
}
// 만약 swap된 적이 없다면 이미 정렬되었다는 의미이므로 반복문 종료
if(swapped == false) {
break;
}
}
System.out.println(Arrays.toString(arr));
}
}