컴퓨터 사이언스/자료구조와 알고리즘
2021. 4. 29. 14:30
[정렬] 거품 정렬, 선택 정렬, 삽입 정렬
거품 정렬, 선택 정렬, 삽입 정렬이 무엇인지, 시간 복잡도를 계산하고 소스코드를 구현해본다. 또한, 각 정렬의 특징을 알아보고 마지막으로 각 정렬을 비교해 무엇이 더 효율적인지에 대해 알아본다. 1. 거품 정렬(Bubble Sort) 1) 거품 정렬이란 서로 인접한 두 원소를 비교해, 대소 관계에 따라 자리를 바꿔주는 정렬이다. 1회전에 첫 번째 원소를 두번 째 원소와, 두 번째 원소를 세 번째 원소와 ,,, N-1을 N번째 원소와 비교해 교환해준다. 다음과 같은 과정을 수행하고 나면, N번째 자리에 가장 큰(혹은 가장 작은) 원소가 위치하게 된다. 이를 N-1번 수행하고 나면 거품이 일어나듯 정렬이 완료된다. 다음은 이해를 돕기 위한 유튜브 영상이다. 2) 거품정렬의 비교 횟수 시간 복잡도 거품 정렬..