[Java] 버블 정렬 알고리즘

프로그래밍을 하다 보면 수많은 값을 처리하게 됩니다. 
특별한 순서 없이 섞인 값들을 오름차순 또는 내림차순으로 정렬해야 하는 경우가 많은데 
정렬을 빠르고 효율적으로 처리하기 위한 다양한 알고리즘이 있죠. 

오늘은 정렬 알고리즘 중 가장 간단한 버블 정렬을 구현해보겠습니다. 
랜덤한 값 6개를 배열로 뽑아낸 후, 버블 정렬(오름차순)을 이용하여 정리 해보도록 하겠습니다. 
먼저 간단히 알고리즘 규칙과, 배열을 설명드리겠습니다.

---

버블 정렬의 사전적 의미

거품 정렬(Bubble sort)은 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복잡도가 {\displaystyle O(n^{2})}로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습이여서 지어진 이름이다. 출처 : 위키백과

쉽게 설명하면, 버블 정렬이란 원소를 두개씩 묶어서 순회하는 정렬이라고 할 수 있습니다.

그 모양이 마치 거품같아서 지어진 이름이고요!

 

 

버블 정렬 알고리즘의 규칙 

• 처음부터 끝까지 모든 요소들을 순회하면서 비교한다.
• 현재 값과 다음 값을 비교하여 큰 값을 다음으로 보낸다. -> 오름차순

---

오늘 구현하려는 코드에 꼭 필요한 것들을 지금부터 하나씩 공부해볼께요

1. 배열

2. 버블 정렬 알고리즘

3. 랜덤 값 

4. 자리 바꾸기 스왑 (temp) 

 

1. 배열이란?

배열이란 번호(인덱스)와 번호에 대응하는 데이터들로 이루어진 자료구조를 나타냅니다.

일반적으로 배열에는 같은 종류의 데이터들이 순차적으로 저장되어, 값의 번호가 곧 배열의 시작점으로부터 값이 저장되어 있는 상대적인 위치가 되죠

대부분의 프로그래밍 언어에서 사용할 수 있는 가장 기초적인 자료 구조라고 할 수 있습니다.

 

++ 변수는 한개의 데이터만 저장 할 수 있기 때문에, 저장해야 할 데이터의 수가 많아진다면 많은 양의 변수를 선언 해야하는 불편함이 존재합니다.(비효율적임) 이런 불편한 점을 해결 할 수 있는 것이 바로 데이터 관리의 효율성을 높여주는 "배열" 이랍니다.

 

 

배열은 두가지 방법으로 선언 할 수 있는데 (저같은 경우 int 타입에 arr이라는 변수를 사용하였습니다.)

 

• int []arr = new int[3]---->> 타입 [ ] 변수 
• int arr[] = new int[3]---->> 타입 변수 [ ]

위와 같이이런 방법이 있습니다.

 

 

그림으로 설명 드리자면 아래와 같은데, 배열을 선언하게 되면 크기가 할당되고 인덱스 (index) 번호가 부여됩니다.

배열은 0번째 방부터 시작하기 때문에, 6을 선언하였다면 0~5까지 인덱스가 매겨집니다.

 

2. 버블 정렬 알고리즘

버블 정렬에 대한 설명은 위에 명시했기 때문에 생략하고

버블 정렬 알고리즘을 그림으로 보여드리겠습니다.

배열에 9,3,6,1,2 값이 순서대로 저장되있다고 가정 후 버블 정렬을 오름차순으로 적용해 보겠습니다.

1회전을 하고 나면, 마지막 자리에는 가장 큰 수가 자리하게 됩니다. (고정 값)

1회전 차에서는 고정으로 지정된 값이 없으므로 비교가 : 4번 일어남

2회전 까지 하고 나면 6,9는 고정이 됩니다.

즉 2회전 차에서는 9가 고정되어있으므로 6과 2까지만 비교를 함 -> 비교 수 : 3번 

 

3회전이 끝나면 3,6,9 는 고정이 됩니다 ---> 비교수 : 2번

 

4회전에서는 3,6,9 고정을 제외한 "1번"만 비교를 하고

1의 값이 더 작으므로 회전을 종료 합니다.

즉 결과는 1,2,3,6,9가 나오겠죠.

버블 정렬은 이런식의 알고리즘으로 값을 정렬합니다.

 

 

3. 랜덤 값

자바에는 랜덤 값을 배출해내는 난수 클래스가 존재 합니다.

난수 클래스는 'Math' 라는 클래스 안에 존재 하는데 'Math'는 최상위 클래스인 'Object'클래스 안에 존재하므로

따로 import를 해줄 필요가 없습니다.

 

 ++랜덤 함수 넣는 다른 방법은
Random random = new Random();로 객체 생성 후 import해준다.
객체 사용하여  nextInt() 메소드 호출 --> 정수인 모든 숫자들 내에서 랜덤한 난수를 발생시킴.

Math.random(); 이란 명령어로 랜덤 값을 출력 할 수 있는데 

숫자 범위는 0.0보다 크거나 같고, 1.0보다 작다. --> 그렇기 때문에 원하는 값을 int형으로 출력 시 +1을 해주어야 한다.

1보다 작은 소수 범위로 랜덤 값이 나오는데 정수형 int는 소수점을 무시하기 때문에 원하는 수보다 -1 이 된 수가 나오기 때문이다.

 

내가 원하는 랜덤값 => 1~45 일 경우

 

(int)(Math.random() *45)+1;  --> 이렇게 되면 1~45 사이 랜덤 값 발생

(int)(Math.random() *45); --> 이런 경우에는 0~44 사이 랜덤 값이 발생합니다.

 

4. 자리 바꾸기 스왑 (temp)

아래 코드에 주석으로 설명을 달았습니다.

코드를 보시면 이해가 빠르실 것 같아 

코드를 짜보았는데요 이렇게 값을 바꾸기 위해 값을 담을 변수인 temp를 선언해주어

자리를 옮기는 것입니다!

---

자 이렇게 중요한 포인트 4가지를 찝어봤으니 이제 전체적인 코드를 짜볼까요?

제가 짜볼 코드는 배열에 6개의 방을 선언한 후, 랜덤으로 그안에 값을 넣고 (범위 : 1~45) 

그 값들을 오름 차순으로 정렬 할꺼예요!

나중에 응용을 해서 (중복제거, 2차원 배열) 로또를 짜볼껍니당 ㅎㅎ

 

바로 아래에 코드를 캡쳐 했는데요, 설명은 코드안에 주석으로 써놓겠습니다.

 

이렇게 코드를 짜봤어요...

아직 저도 코딩실력이 미흡하여 더 열심히 노력해서 다음번에는 조금 더 깔끔한 코드로 짜볼께요!

코드는 눈에 보이기 쉽게 (저와 같은 초보자 분들도 이해하기 쉽게_!!)

일부러 "{" "}" 이런 부호들을 보이게 다 Enter해주었답니당^_^ 

 

결과는

이렇게 나오네요~ 6개의 숫자를 랜덤으로 고르고 -> 정렬되어 작은 수가 앞으로 왔죠!

ㅎㅎ 이번 글은 여기까지 마무리 하겠습니당!

다들 수고 하셨어요~ 👩