Working of the Bubble Sort
Coddy의 버블 정렬 코스 레슨. 11개 중 2번째.
버블 정렬(Bubble sort)은 리스트의 요소를 반복하며 인접한 요소를 비교하고, 순서가 잘못된 경우 서로 교체하는 간단한 정렬 알고리즘입니다.
리스트가 정렬될 때까지 리스트를 훑는 과정이 반복됩니다.
예시-
4개의 요소가 있는 리스트 [3,4,2,1]을 정렬해야 합니다.
첫 번째 패스(First Pass):
처음 두 요소를 비교합니다.
[3,4,2,1] -> [3,4,2,1] (이미 정렬되어 있으므로 변경 없음)
다음 두 요소를 비교합니다.
[3,4,2,1] -> [3,2,4,1] (정렬된 순서로 만들기 위해 요소를 교체함)
다음 두 요소를 비교합니다.
[3,2,4,1] -> [3,2,1,4] (정렬된 순서로 만들기 위해 요소를 교체함)
첫 번째 패스가 완료되었습니다. 무엇을 관찰하셨나요?
리스트가 정렬되었나요? 아니오, 그렇죠?
그래서, 우리는 이 과정을 다시 반복해야 합니다.
첫 번째 패스를 통해 리스트의 가장 큰 요소가 리스트의 끝에 위치하게 된 것을 확인해 보세요. 이것이 우리가 이후의 패스들을 통해 달성하고자 하는 것입니다.
두 번째 패스(Second Pass):
처음 두 요소를 비교합니다.
[3,2,1,4] -> [2,3,1,4] (정렬된 순서로 만들기 위해 요소를 교체함)
다음 두 요소를 비교합니다.
[2,3,1,4] -> [2,1,3,4] (정렬된 순서로 만들기 위해 요소를 교체함)
다음 두 요소를 비교합니다.
[2,1,3,4] -> [2,1,3,4] (이미 정렬되어 있으므로 변경 없음)
두 번째 패스 후에 마지막 두 요소가 정렬된 것을 확인하세요.
세 번째 패스(Third Pass):
처음 두 요소를 비교합니다.
[2,1,3,4] -> [1,2,3,4] (정렬된 순서로 만들기 위해 요소를 교체함)
이 패스 후에 우리가 원하는 리스트를 얻게 된 것을 확인하세요.
이것이 바로 버블 정렬이 작동하는 방식입니다!
이제 다음 레슨에서 버블 정렬 알고리즘을 이해해 봅시다.
즐거운 학습 되세요!
챌린지
쉬움배열, 배열의 크기, 그리고 두 개의 인덱스를 인자로 받는 swap_list라는 이름의 함수를 작성하세요. 이 함수는 두 인덱스의 요소를 서로 바꾸고 새로운 리스트를 반환합니다.
예시:
list=[1,2,3,4] (0부터 시작)
n=4 (리스트 내 요소의 개수)
i=1 j=3 (교환할 인덱스)
[1,2,3,4] -> [1,4,3,2]
반환값: list= [1,4,3,2]
직접 해보기
#include <stdio.h>
#include <stdlib.h>
int* swap_list(int* arr, int arr_size, int n, int i, int j, int* returnSize) {
// 여기에 코드를 작성하세요
*returnSize = n;
return arr;
}
버블 정렬의 모든 레슨
1Basics of Bubble Sort
IntroductionWorking of the Bubble SortSwap adjacent elementsBubble Sort Algorithm직접 연습해 보세요: 온라인 C 컴파일러