#1517 버블 소트
버블 소트는 정렬에서 가장 재미있는 정렬 방식이자, 사실 실생활에서도 많이 이루어지는 정렬 방식이죠. 이웃하는 것끼리 크기를 비교해서 위치가 잘못되었으면 서로 교환을 하는 방식입니다. 대략 해당되는 알고리즘을 코드로 표현하면 다음과 같습니다. function Bubble(a, from, to): for i in (to, from+1, -1): for j in (from, i-1): if a[j] > a[j+1]: swap(a, j, j+1) 위의 알고리즘에서 swap하는 횟수가 몇번인가를 구하는 것이 이번 문제죠. 이 문제를 풀기 위해서 swap 횟수는 몇번 일어날 것인지 알아볼께요. 3, 5, 1, 2, 4 라는 수열이 있습니다. 3 5 1 2 4 이 수열이 버블 정렬에 의해서 swap이 발생하는 과정..
2022. 8. 23.
