📝 오늘 한 것

1. 버블 정렬 알고리즘

📖 학습 자료

1. [TIL] 211015

2. 책 '누구나 자료 구조와 알고리즘'

📚 배운 것

1. 버블 정렬 알고리즘

1) 설명

버블 정렬 알고리즘은 선택 정렬, 삽입 정렬과 함께 단순 정렬 알고리즘의 한 종류이다.

배열의 2개의 아이템을 비교한 후 왼쪽이 오른쪽보다 크면 아이템을 교환한다.
큰 아이템이 오른쪽에서 더 큰 아이템을 만나면 교환을 멈춘다.
계속해서 더 큰 아이템은 그 다음 아이템과 비교한다.

결국 가장 큰 아이템이 맨 뒤로 이동한 후에 한 싸이클(패스스루)이 끝난다.
정렬된 마지막 아이템을 제외하고 같은 과정을 반복한다.

2) 빅오

N-1 + N-2 + N-3 + ... + 2 + 1번의 '비교'를 하고, 최악의 경우에 모든 싸이클마다 모든 아이템을 '교환'해야 한다. => N(N-1) / 2

정리하면, 데이터의 개수가 N개일 때, 대략 N² 단계가 걸린다.
따라서, 버블 정렬의 시간 복잡도는 O(N²)이다.

3) 코드 구현

저작권 문제로 VS code에 따로 정리해 둠 ( Gitlab 참고 )

✨ 내일 할 것

1. 강의 듣기