![[자료구조] 버블 정렬 (bubble sort)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbwUWOx%2FbtrSIrd5LAU%2FJ9qAUUTeetlgj42EWoHUIk%2Fimg.jpg)
버블 정렬이란?
버블 정렬은 두 개의 인접한 원소를 비교해 순서에 맞지 않으면 서로 교환하는 정렬 방식입니다. 이렇게 인접한 원소를 교환하는 모습이 마치 물 속의 거품과 비슷
해 버블 정렬이라고 부르는 것입니다.
순서에 맞지 않은 원소들을 교환하다 보면 오른쪽 리스트는 자동으로 정렬되기 시작합니다. 이 과정에서 왼쪽 리스트에 있는 원소들을 반복적으로 교환하면 정렬이 완료됩니다.
버블 정렬 구현
버블 정렬의 핵심은 비교 후 순서에 어긋나면 교환하는 것입니다.
각자 아래 목적에 맞게 분리되어야 하므로 반복문을 통해 숫자가 담겨있는 배열이나 리스트에 제대로 접근해야 합니다.
- 왼쪽 리스트: 인접한 원소의 순서가 맞지 않으면 바꿔줍니다.
- 오른쪽 리스트: 리스트 끝에서부터 정렬이 되어 있는 상태이므로 이 안에서 절대 자리를 바꾸면 안됩니다.
코드로 구현하면 아래와 같습니다.
void bubble_sort(int list[], int n) {
int temp;
for(int i = n - 1; i > 0; i—) {
for(j = 0; j < i; j++) {
// 앞 뒤를 비교한 후 순서에 맞지 않으면 교체
if(list[j] > list[j + 1]) {
SWAP(list[j], list[j + 1], temp);
}
}
}
}
버블 정렬의 시간 복잡도
버블 정렬 상한
버블 정렬은 반복문이 이중으로 들어가 있기 때문에 $O(n^2)$입니다.
버블 정렬 하한
이미 정렬된 경우 버블 정렬은 실행시간의 하한으로 $O(n)$의 시간 복잡도를 가질 수 있다.
아래 사진은 $O(n^2)$으로 나와있어 유의가 필요하다.
[자료구조] 선택 정렬 (selection sort)
선택 정렬이란? 정렬이 되어 있는 왼쪽 리스트와 정렬이 되어 있지 않은 오른쪽 리스트로 나누었다고 가정해봅시다. 오른쪽 리스트에서 가장 작은 숫자를 선택해서 왼쪽 리스트에 차례대로 넣
laurent.tistory.com
[자료구조] 삽입 정렬 (insertion sort)
삽입 정렬이란? 정렬이 되어 있는 왼쪽 리스트와 정렬이 되어 있지 않은 오른쪽 리스트로 나누었다고 가정해봅시다. 배열의 첫 원소부터 차례대로 앞에 이미 정렬되어 있는 왼쪽 리스트와 비교
laurent.tistory.com
[자료구조] 셸 정렬 (shell sort)
셸 정렬이란? 이전에 포스팅 했던 삽입 정렬은 시간 복잡도가 $O(n^2)$로 정렬 알고리즘 중에서는 느린 축에 속하는 정렬 방식이었습니다. 하지만 삽입 정렬은 어느 정도 배열이 정렬이 된 상태라
laurent.tistory.com
[자료구조] 합병 정렬 (merge sort)
합병 정렬이란? 합병 정렬은 리스트를 분할하고 결합하는 과정 속에서 정렬을 수행하고자 하는 방법입니다. 분할-정복에 따른 수행 방식입니다. 앞서 정렬을 할 때는 기존의 리스트를 그대로 이
laurent.tistory.com
[자료구조] 퀵 정렬 (quick sort)
퀵 정렬이란? 퀵 정렬은 합병 정렬과 동일하게 분할 정복 알고리즘을 사용합니다. 차이점이 존재한다면, 퀵 정렬은 리스트를 비균등하게 분할합니다. 작동 방식 작동 방식에 앞서, 퀵 정렬에는
laurent.tistory.com
[자료구조] 힙 정렬 (heap sort)
힙 정렬이란? 힙 정렬은 힙 트리를 이용해 정렬을 하는 것을 말합니다. 사실 최대 힙과 최소 힙은 각각 루트에 최댓값과 최솟값이 이미 있습니다. 루트를 계속 꺼내면 힙의 정의에 의해 그 다음
laurent.tistory.com
[자료구조] 기수 정렬 (radix sort)
기수 정렬이란? 처음 이 정렬을 들으면 기수라는 단어가 생소할 겁니다. 사전에서 찾아보면 다음과 같습니다. 십진수에서는 0부터 9까지의 숫자를 각 자릿수에 넣을 수 있습니다. 우리는 이 리스
laurent.tistory.com
'CSE > 자료구조 (data structure)' 카테고리의 다른 글
[자료구조] 합병 정렬 (merge sort) (0) | 2022.11.13 |
---|---|
[자료구조] 셸 정렬 (shell sort) (0) | 2022.11.12 |
[자료구조] 삽입 정렬 (insertion sort) (0) | 2022.11.10 |
[자료구조] 선택 정렬 (selection sort) (0) | 2022.11.09 |
[자료구조] 그래프 위상 정렬 알고리즘 (0) | 2022.11.08 |
경북대학교에서 컴퓨터과학을 전공하고 있는 학부생입니다. 컴퓨터 전공 관련 내용들과 프론트엔드 개발 지식들을 공유합니다. React, Javascript를 다룰 줄 알며 요즘에는 Typescript에도 관심이 생겨 공부하고 있습니다. 서로 소통하면서 프로젝트 하는 것을 즐기며 많은 대외활동으로 개발 능력과 소프트 스킬을 다듬어나가고 있습니다.
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!