알고리즘을 공부를 시작해보려고 한다..!
평소에 조금씩이라도 해야할것 같다는 생각이 들었다.
버블정렬을 알아보니 평소에 생각없이 쓰던 정렬 방법이였다는것을 알았다..!
이제는 무엇이든 알고 사용하도록 하자..!!
[⭐항상 새겨두어야할 공부 방법⭐]
- 다른 사람한테 설명 가능해야 함! (설명 못하면 제대로 이해 못한거)
- 항상 구조적으로 생각하고 이해하기 ( 왜 이렇게 되는지 )
- 하고 많은 다양한 똑같은 것들 중에서 왜 이걸 사용하는지?
항상 무엇을 학습하든 위 내용을 생각하면서 살아야지..!
본론으로...
버블정렬 프로세스
- 첫 번째 원소와 두 번째 원소 비교하고, 두 번째 원소와 세 번째 원소를, 세 번째와 네 번째....~~ 이런식으로
마지막-1 번째 원소와 마지막 원소 까지 비교하여 서로 교환하면서 정렬한다!
- 처음 1회 정렬을 하면 가장 큰 원소가 맨 뒤로 가고 맨뒤에는 이제 고려하지 않아도 되는 원소가 된다
그렇게 반복을 할 때마다 정렬에서 제외되는 데이터는 하나씩 늘어난다!
직접 움직임을 보는게 더 도움이 될것 같다!
void bubbleSort(int[] arr) {
int temp = 0;
for(int i = 0; i < arr.length; i++) { // 1.
for(int j= 1 ; j < arr.length-i; j++) { // 2.
if(arr[j-1] > arr[j]) { // 3.
// swap(arr[j-1], arr[j])
temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
}
}
System.out.println(Arrays.toString(arr));
}위 코드와 gif를 보며 비교해보면 이해가 더 쉬울 것 같다!!
시간복잡도
예전엔 복잡도에 대한 생각을 아예 안했던것 같다..
이제 좀 이런 것도 생각 할 줄 알아야 하고 복잡도도 산정할 수 있어야 할 것 같다!!
버블정렬의 시간 복잡도는 (n-1) + (n-2) + (n-3) + ~~~ + 2 + 1 인데
이것을 점화식으로 나타내면 n(n-1)/2 가 된다. 이는 O(n^2)이다.
버블정렬은 정렬이 되어져있던지 아니던지, 2개의 원소를 비교하기 때문에
최선,평균,최악의 경우 모두 시간 복잡도가 동일하다... << 좋은건지 안좋은건지..?ㅎ
이 때문에 개선된 버블정렬이 있다고 한다!
어떠한 경우에 버블정렬을 사용하면 좋고 어떤 경우에 버블정렬을 사용하면 안되는지,
개선된 버블정렬이란 무엇인지 추가적으로 공부해보고 포스팅해서 정리를 해야겠다!!
우선 이 포스팅에서는 버블정렬이 무엇인지 어떻게 정렬이 되는지 정확히 이해하고 넘어가자!
공간복잡도
공간복잡도는 주어진 배열 안에서 교환을 통해 정렬이 수행되므로 O(n) 이라고 한다!!
공간복잡도와 시간복잡도에 대한 내용도 공부를 해서 정리해야겠다!!
공부할게 많구나..
장점
- 구현이 매우 간단하고, 소스코드가 직관적이다. << 내가 정확히 모르고 사용하고 있었던걸 보면 맞는것 같다 ㅎ
- 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간이 필요없다. (제자리정렬 [in-place-sorting])
- 안정 정렬이다. (stable sorting)
단점
- 시간복잡도가 모든 케이스에서 O(n^2) 이므로 매우 비효율적..
- 교환 연산이 많이 일어나게된다!
⭐⭐정리!
버블정렬은 쓰기 쉽지만 그렇게 효율적이진 않다!
위에서 말했던 것 처럼
- 어떠한 경우에 버블정렬을 사용하면 좋고 어떤 경우에 버블정렬을 사용하면 안되는지,
- 개선된 버블정렬이란 무엇인지
- 공간복잡도와 시간복잡도
이 내용들을 세부적으로 공부해서 포스팅 하도록 하자!!
