구 원트노/알고리즘

[알고리즘]정렬-버블 정렬(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로 하는 루비 문법입니다.




궁금하신 점 있으시면 댓글 남겨주세요!!