[Java] 자바 버블 정렬 / java 버블 정렬 구현하기

2020-09-28

---

거품 정렬(Bubble sort)은 두 인접한 원소를 검사하여 정렬하는 방법이다. 

시간 복잡도가 O(n2)로 상당히 느리지만,

코드가 단순하기 때문에 자주 사용된다.

원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다.

양방향으로 번갈아 수행하면 칵테일 정렬이 된다. 

 

오름차순으로 정렬하는 거품정렬의 과정은 다음과 같다

 

출처 : 위키피디아

링크 : ko.wikipedia.org/wiki/%EA%B1%B0%ED%92%88_%EC%A0%95%EB%A0%AC

---

소스코드

		Scanner scan = new Scanner(System.in);
		int [] arr = new int [10];
		//정렬할 숫자가 들어갈 배열
		
		int n = -1;
		//입력받을 숫자의 개수가 저장될 변수
		int count = 0;
		//자료의 교환 횟수가 저장될 변수
		int sw = 0;
		//자료가 교환 되었는지 검사할 변수
		
		do {
			n++;
			arr[n] = scan.nextInt();
		}while(n < 9);
		//숫자 입력 반복문
		
		int temp = 0;
		//위치를 바꿀때 숫자를 잠시 담아둘 변수
		
		for(int i = 1; i <=9; i++) {
			sw = 0;
			loop : for(int j = 0; j <= (9-i); j++) {
				if(arr[j] > arr[j + 1]) {
					temp = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = temp;
					count++;
					sw = 1;
				}
			}
			//sw 가 1이되면 자료가 변경되었다는 의미
			//변경될게 없을떄까지 loop 문 반복
			if(sw == 0)
				break;
		}
		
		for(int i =0; i < 10; i++) {
			System.out.print(arr[i] + " ");
		}