- 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘입니다.
- 이름의 유래로는 정렬 과정에서 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어졌다고 합니다.
void bubbleSort(int[] arr) {
int temp = 0;
for(int i=0; i<arr.length; i++) {
for(int j=1 ; j<arr.length-i; j++) {
if(arr[j-1] > arr[j]) {
temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
}
}
}
(n-1) + (n-2) + (n-3) + .... + 2 + 1 => n(n-1)/2 이므로 O(n^2) 이다.- Bubble Sort 는 정렬이 되어 있던 안되어 있던 2개의 원소를 비교하기 때문에 최선, 평균, 최악의 경우 모두 시간복잡도가 n^2 으로 동일하다.
- 시간복잡도가 최악, 최선, 평균 모두 O(n^2)으로, 굉장히 비효율적이다.
- 정렬 되어있지 않은 원소가 정렬 됐을때의 자리로 가기 위해서, 교환 연산이 많이 일어나게 된다.
- 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘입니다.
void selectionSort(int[] arr) {
int indexMin;
int temp;
for (int i=0; i<arr.length-1; i++) {
indexMin = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[indexMin]) {
indexMin = j;
}
}
temp = arr[indexMin];
arr[indexMin] = arr[i];
arr[i] = temp;
}
}
- 첫 번째 비교횟수 : 1 ~ (n-1) => n-1
- 두 번째 비교횟수 : 2 ~ (n-1) => n-2
(n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2- 선택 정렬도 마찬가지로 정렬이 되어 있든 안되어 있든 작은 값을 찾기 위해 계속 순회하기 때문에 최선, 평균, 최악의 경우 시간복잡도는 n^2 으로 동일하다.
- Bubble sort와 마찬가지로 구현이 매우 간단하며 소스가 직관적입니다.
- 정렬을 위한 비교 횟수는 많지만, Bubble Sort에 비해 실제로 교환하는 횟수는 적기 때문에 많은 교환이 일어나야 하는 자료상태에서 비교적 효율적입니다.
- 시간복잡도가 최악, 최선, 평균 모두 O(n^2)으로, 굉장히 비효율적이다.
- 2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입 하여 정렬하는 알고리즘입니다.
- 최선의 경우 O(N)이라는 엄청나게 빠른 효율성을 가지고 있어, 다른 정렬 알고리즘의 일부로 사용될 만큼 좋은 정렬 알고리즘이라고 합니다.
void insertionSort(int[] arr)
{
for(int index=1; index<arr.length; index++) {
int temp = arr[index];
int prev = index - 1;
while((prev>=0) && (arr[prev]>temp)) {
arr[prev+1] = arr[prev];
prev--;
}
arr[prev + 1] = temp;
}
}
- 최악의 경우(역으로 정렬되어 있을 경우) Selection Sort와 마찬가지로,
(n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2 즉, O(n^2) 이다.
- 모두 정렬이 되어있는 경우 한번씩 밖에 비교를 안하므로 O(n) 의 시간복잡도를 가지게 된다.
- 이미 정렬되어 있는 경우, 시간복잡도가 O(n) 으로 매우 효율적일 수 있다.
- 평균과 최악의 시간복잡도가 O(n^2)으로 비효율적이다.
