Bubble sort

안녕하세요! 이번시간에는 sorting에대해서 공부해볼겁니다!!! sorting 이란 정렬 이라는 뜻으로, bubble sort 는 두 인접한 원소를 검사하여 정렬하는 방법입니다. 시간은 상당히 많이 걸리지만, 코드가 단순하기 때문에 자주 사용된답니다! 그렇다면 10개의 숫자를 입력받고 입력받은 숫자를 오름차순으로 (작은숫자먼저!) 정리하는 프로그램을 만들어 봅시다!

*needs*

1. 10개의 수를 받을수있는 배열을 생성합니다

2. 순서대로 정렬 시킵니다

10개의 배열을 생성하는것은 굉장히 쉽습니다. 단순히 int[] arr = new int[10];

만 작성하면 되기 때문입니다. 그렇다면 순서대로 정렬은 어떻게 할까요...?

이번시간에 저희가 할 정렬은 bubble sort입니다. 인접한 두 숫자중 누가더 큰 수인지 검사하여 바꾸는 방법인데 그 모습이 거품이 움직이는 것같기에 bubble sort라고 합니다! 그렇다면 이건 어떤가요? 만약 53124 라는 숫자 배열이 있다고 생각해 봅시다! 먼저 앞에 2개의 숫자 , 5와 3을 비교합니다. 누가더 큰가요?? 5가더 크네요!! 그

럼 5와 3의 자리가 바뀌어 35124가 됩니다. 그뒤에 2번째와 3번째 숫자를 비교합니다! 어떤가요? 5와 1이네요 역시 5가더 크기에 바뀌어서 31524가 됩니다. 마찬가지로 계~~속 진행하다보면 결국 31245가 되는군요! 그런데 완벽히 12345로 정렬이 되지 않았습니다! 그렇다면 한번더 첫번째 수부터 정렬이 진행되면 될것같군요! 한번 아래의 소스코드를 보시죠!

반복문의 변수 i는 0부터 시작해서 배열 last index 바로 전 index까지 증가시키게 하였습니다!(마지막 인덱스+1 이되면 배열의 index가 넘어가기 때문에...)

그리고 이반복문을 여러번 반복하게되면!!!

한 10번정도 반복하여 제가 원하고자하는 오름차순 정렬된 배열들을 구할수 있습니다! 그런데 for(int value : arr)가 무엇인지 의아해 하시는 분들이 있을겁니다! 요것은

for-each루프라고 하여서 JDK1.5 버전부터 사용할수 있는 루프입니다. 배열의 index값을 생각할 필요없이 배열안의 모든 요소들을 방문할수 있는 장점이 있기에 단순히 배열을 출력하는데 있어서 조금은 간단해 지네요! 자~ 이제 마지막 입니다. 10번을 반복문이 반복하는데요, 이미 정렬이 끝났음에도 필요없는 반복문이 도는 경우가 있을수도 있습니다. 그. 래. 서. 정렬이 마무리되면 반복문을 실행되지 않고 마무리 할 수 있게 프로그램을 수정하고 싶은데요.. 어떻게 하면 좋을까요?? point는 if문이 실행되지 않는 경우는 정렬이 끝난것이라고 생각할 수도 있기에.. 이렇게 해봅시다! 아래를 보시죠!

네~ 그렇습니다. if 문이 실행되면 바깥 for 문에서 초기화했던 cnt를 ++ 시켜 1로만들고 안의 for문에서 나오자마자 과연 cnt가 0인지 , 0이라면 if 문이 실행된게 아니기에 추가로 반복문을 반복할 필요없이 바로 탈출! 하게 하였습니다!! 

여기까지 bubble sort를 함께 하셨는데요!! 감사합니다. 다음시간에는 quick sort에대해서 공부해보도록 합시다!