잘못된 정보가 있다면, 꼭 댓글로 알려주세요(비로그인 익명도 가능).
여러분의 피드백이 저와 방문자 모두를 올바른 정보로 인도할 수 있습니다.
감사합니다. -
후원해주실 분은 여기로→
현록의 기록저장소
정렬 - 버블 정렬 본문
이미 Quick Sort와 Merge Sort를 살펴봤지만,
[Study/Algorithm] - 정렬 - 합병 정렬
시간복잡도를 보는 겸 버블 정렬도.
https://ko.wikipedia.org/wiki/%EA%B1%B0%ED%92%88_%EC%A0%95%EB%A0%AC
거품 정렬 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 무작위 배열수의 거품 정렬 예 거품_정렬 편집된 색상 거품 정렬(Bubble sort)은 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복잡도가 O ( n 2 ) {\displaystyle O(n^{2})} 로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다. 오름차순으로 정렬하는 거품정렬의 과정은 다음과 같다. 55 07 7
ko.wikipedia.org
이중 for문을 사용하기 때문에 시간복잡도(O)는
O(n^2).
void bubbleSort(int[] arr) {
for(int i = 0; i < arr.length; ++i) {
for(int j = 0; j < arr.length - 1 - i; ++j) {
if(arr[j] > arr[j + 1]) {
int temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
}
}
}
}j에서 1만큼 빼는 이유는
비교를 j와 j+1로 하기 때문.
j에서 i만큼 빼는 이유는
최종 확정 위치에 정착하는 요소가 가장 오른편부터 누적되고(위 코드에서는 왼→오로 진행되기 때문),
이 요소들은 다음에 검토할 필요가 없으므로.
'Study > Algorithm' 카테고리의 다른 글
| Hash Function (0) | 2019.06.27 |
|---|---|
| 한 선이 만나는 다른 선의 수 (0) | 2019.05.11 |
| 정규표현식(Regular Expression) (0) | 2019.05.05 |
| 정렬 - 합병 정렬 (0) | 2019.04.28 |
| 정렬 - 퀵 정렬 (0) | 2019.04.27 |
잘못된 정보가 있다면, 꼭 댓글로 알려주세요(비로그인 익명도 가능).
여러분의 피드백이 저와 방문자 모두를 올바른 정보로 인도할 수 있습니다.
감사합니다. -
후원해주실 분은 여기로→