구 원트노/알고리즘
[알고리즘]정렬-버블 정렬(Bubble Sort)정렬-버블 정렬(Bubble Sort)
버블 정렬은 이웃하는 숫자를 비교하여 정렬하는 알고리즘입니다.
여러 정렬 알고리즘 중 성능면에서는 시간복잡도가 O(n^2)로 비교적 떨어지지만 컨셉도 간단하고 코드도 단순하여 자주 사용됩니다.
버블 정렬 컨셉
오름차순 기준입니다.
정렬을 배열에 집어넣고 시작합니다.
이제 입력을 전체적으로 1번 처리하는 것을 패스(pass)라고 하겠습니다.
1번째 pass부터 가장 앞의 데이터와 그 다음 데이터를 비교해서 큰 수를 뒤로 보냅니다.
그렇게 배열의 끝까지 순서를 바꾸면 1번째 pass에서 가장 큰 수의 위치가 배열의 끝으로 고정이 되어집니다.
이와 같은 방식으로 다음 pass부터는 확정된 마지막 배열을 제외하고 전의 작업을 반복합니다.
결과적으로 (배열의 크기-1)번의 pass를 수행하면 모든 데이터는 오름차순으로 정렬이 됩니다.
예시 입니다.
코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | def Bubble_sort(n) s = Array.new (1..n).each do |s_n| s << rand(15) end for pass in 1..n-1 for i in 1..n-pass if s[i-1]>s[i] s[i],s[i-1] = s[i-1],s[i] end end end return s end sorted_num=Bubble_sort(gets.to_i) sorted_num.each do |bs| puts bs end | cs |
사실 루비로는 sort메서드 쓰기만 하면 오름차순 정렬이 되지만 직접 구현해봤습니다.
중점적으로 봐야 할 부분은 Bubble_sort 메서드에 6번째 줄 반복문 부분입니다.
생각해보면 pass당 마지막 배열 요소 1개씩 확정되다가 (배열크기 -1)pass 순서가 되면 정해지지 않은 부분은 두 자리 밖에 없어집니다.
이때 한 자리만 확정이 되어도 모두 확정이 되므로 pass의 범위는 배열크기 -1이 됩니다.
7번째 반복문은 pass안에서 이웃한 데이터와 크기 비교하는 횟수 부분입니다. 위의 예제 사진을 참고해서 보면 이해가 될 것 같습니다.
9번째 코드는 루비에서의 변수 값을 swap하는 코드인데 x <=> y를 바꾸는 코드를 x,y=y,x로 하는 루비 문법입니다.
궁금하신 점 있으시면 댓글 남겨주세요!!
'구 원트노 > 알고리즘' 카테고리의 다른 글
[알고리즘]정렬-삽입 정렬(Insertion Sort) (0) | 2017.01.22 |
---|---|
[알고리즘]정렬-선택 정렬(Selection Sort) (2) | 2017.01.14 |
[루알풀]2839번: 설탕 배달 (0) | 2017.01.09 |