#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.
[C/C++] 백준 #1377 버블 소트(안정적 정렬)
이번 문제는 난이도 Gold V입니다. 저는 이런 문제를 좋아합니다. 알고리즘의 기본을 잘 이해하는지 물어보는 문제이기도 하니까요. 정렬은 알고리즘을 배우면서 가장 먼저 배우는 알고리즘이기도 합니다만, 기본을 충실하게 알고 있는 사람은 많지 않습니다. https://www.acmicpc.net/problem/1377 1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 대부분 기본정렬은 선택정렬, 삽입정렬, 버블정렬이 있고, 고급정렬은 병합정렬, 힙정렬, 퀵정렬이 있고, 기본정렬은 \(O(N..
2020. 2. 5.
