Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
Tags
- Smilegate
- LIS #Algorithm #요소추적
- 식단
- 스마일게이트
- BFS
- 투포인터
- 카카오인턴
- IBK기업은행 #기업은행 #디지털 #직무 #정리
- 카카오
- 유니온파인드
- 알고리즘
- BaekJoon
- 중반부
- 코테
- Algorithm
- 삼성 #코테 #2020상반기 #c++
- 소감
- 백준
- 서버개발캠프
- 보석쇼핑
- 코딩테스트
- 1편
- c++
- Union-find
Archives
- Today
- Total
짱아의 개발 기록장
버블 정렬(bubble sort) 구현하기(c++) 본문
반응형
0~n-1까지 인접한 값들을 비교하면서, 크기가 더 큰 원소를 뒤로 보내주는 연산을 (원소의 개수-1)만큼 반복해주면 된다.
왜? (원소의 개수-1)만큼 반복해주나?
5, 4, 3, 2, 1 처럼 모든 원소의 자리를 바꿔야 하는 경우에는 총 4번을 연산하면 1, 2, 3, 4, 5와 같은 형태로 바꿀 수 있다.
즉, 최악의 경우까지 고려하여 (원소의 개수-1)만큼 반복 연산해주면 오름차순으로 정렬할 수 있다.
*시간복잡도*
Best | Avg | Worst |
O(n^2) | O(n^2) | O(n^2) |
코드 첨부
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
// 버블 정렬 구현(오름차순)
#include <iostream>
using namespace std;
// 초기 배열 상태
int arr[5] = {2, 1, 4, 0, 3};
void bubble_sort(int arr[], int size)
{
for(int i=0; i<size-1; i++){ // 반복(size-1만큼)
for(int j=0; j<size-1; j++){
if(arr[j]>arr[j+1]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
int main()
{
bubble_sort(arr, 5);
for(int i=0; i<5; i++){
cout<<arr[i]<<" ";
}
cout<<"\n";
}
|
cs |
위의 표는 아래 블로그에서 참조했습니다.
https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html
반응형
'CS(Computer Science)' 카테고리의 다른 글
삽입 정렬(insertion sort) 구현하기(c++) (0) | 2020.08.10 |
---|---|
선택 정렬(selection sort) 구현하기(c++) (0) | 2020.08.10 |
큐 구현하기(c++) (0) | 2020.08.03 |
스택 구현하기(c++) (0) | 2020.08.03 |
큐로 스택 구현하기(c++) (0) | 2020.08.03 |