Java - 정렬 알고리즘 - 1 (버블 정렬)

◎버블 정렬

두 개의 인접한 원소를 비교하여 정렬하는 방식.

인접한 2개의 레코드를 비교하여 크기가 순서대로 되어있지 않으면 서로 교환한다.

정렬 과정에서 원소의 이동이 마치 거품이 수면 위로 올라오는 것 같다고 해서 bubble 정렬이다.

 

---

◎버블 정렬의 특징

1. 비교 정렬(comparison sort)

버블 정렬은 데이터를 바교하면서 찾는다.

 

2. 제자리 정렬(in-place sort)

정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하지 않는다.

 

3. 안정 정렬(stable sort)

정렬되지 않은 상태에서 같은 키값을 가진 원소의 순서가 정렬 후에도 유지된다.

---

◎버블 정렬의 동작

출처: https://godgod732.tistory.com/11?category=659135

1. 앞에서부터 현재 원소와 다음의 원소를 비교한다.

2. 현재 원소가 다음 원소보다 크면 서로 교환한다.

3. 다음 원소로 이동하여 다음 원소와 그다음 원소를 비교한다.

4. 1~3을 반복하며, n회전을 돌 때마다 뒤에서부터 n개의 원소가 정렬되고, n회전에서는 배열 크기 -n까지만 비교한다

 

출처: 위키백과, bubblesort

---

◎버블 정렬의 구현

package SortAlgorithm;

import java.util.Arrays;

public class sort {
	
	//버블 정렬
	private void bubblesort(int[] numarr) {
		
		//회전은 배열의 길이 -1만큼 반복된다
		for(int i = 1; i<numarr.length; i++) {
			//i번 회전할 때마다, 뒤에서부터 i개가 정렬되므로, numarr.length -i개만 비교하면 된다
			for(int j =0; j<numarr.length -i ; j++) {
				if(numarr[j]>numarr[j+1]) { //오름차순 정렬
					swap(numarr,j,j+1 );
				}
			}
		}
		
		print(numarr, "버블 정렬");
	}
	
	
	
	//swap
	private void swap(int[] numarr, int i, int j) {
		int temp = numarr[i];
		numarr[i] = numarr[j];
		numarr[j] = temp;
	}
	
	//출력
	private void print(int [] numarr, String sortname) {
		System.out.println(sortname +"로 정렬된 배열:" +Arrays.toString(numarr));
	}
	
	

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] numarr = {5,6,3,1,4,2}; // 정렬할 배열
		System.out.println("원래 배열:" + Arrays.toString(numarr));
		
		sort Sort = new sort(); 
		
		Sort.bubblesort(numarr);
		
	}
}

실행 결과:

원래 배열:[5, 6, 3, 1, 4, 2]
버블 정렬로 정렬된 배열:[1, 2, 3, 4, 5, 6]

---

◎버블 정렬 개선

 

버블 정렬은 구현하기 쉽고 정렬 시에 추가적인 공간이 필요하지 않지만, 시간 복잡도가 O(N^2)로 정렬 시간이 매우 오래 걸린다는 단점이 있다.

앞의 원소들이 정렬되어 있는지 확인하지 않고, 무조건 원소의 비교를 실행하는 버블 정렬의 특성상, 정렬된 배열이 버블 정렬 메서드에 들어가도 O(N^2)의 시간 복잡도를 보인다.

그러므로, 앞의 원소들이 정렬되어있는지 확인하기 위해서, 전 회전에서 원소의 교환이 일어났는지 확인하는 변수를 두어, 전 회전에서 원소의 교환이 일어나지 않았다면, 앞의 원소들은 모두 정렬되어있는 것이므로 정렬을 종료하면 된다,

 

ex) 길이가 6인 정렬된 배열이 개선된 버블 정렬에 들어가면, 1회전에서 모두 정렬되어있으므로 원소의 교환이 아무것도 일어나지 않고, 이에 따라 2회전을 시행하지 않고 바로 정렬을 마친다.

 

package SortAlgorithm;

import java.util.Arrays;

public class sort {

	// 버블 정렬
	private void bubblesort(int[] numarr) {

		// 회전은 배열의 길이 -1만큼 반복된다
		for (int i = 1; i < numarr.length; i++) {
			
			boolean isswap = false; //회전에서 swap이 있었는지 판단하는 boolean 변수
			
			// i번 회전할 때마다, 뒤에서부터 i개가 정렬되므로, numarr.length -i개만 비교하면 된다
			for (int j = 0; j < numarr.length - i; j++) {
				if (numarr[j] > numarr[j + 1]) { // 오름차순 정렬
					swap(numarr, j, j + 1);
					isswap = true; //swap이 있었으면, true로 전환
				}
			}
			
			if(isswap == false) {
				break; //isswap이 flase면 앞의 원소들이 모두 정렬되어있다는 뜻이므로 종료
			}
		}

		print(numarr, "버블 정렬");
	}

	// swap
	private void swap(int[] numarr, int i, int j) {
		int temp = numarr[i];
		numarr[i] = numarr[j];
		numarr[j] = temp;
	}

	// 출력
	private void print(int[] numarr, String sortname) {
		System.out.println(sortname + "로 정렬된 배열:" + Arrays.toString(numarr));
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] numarr = { 5, 6, 3, 1, 4, 2 }; // 정렬할 배열
		System.out.println("원래 배열:" + Arrays.toString(numarr));

		sort Sort = new sort();

		Sort.bubblesort(numarr);

	}
}

 

개선된 버블 정렬에서 정렬된 배열이 입력되면 최선의 시간복잡도 O(n)을 가진다.

 

---

◎Sorting algorithm 시간 복잡도(time complexity) & 평균 정렬 속도(average sorting rate)

Sorting algorithm 시간복잡도(time complexity) & 평균 정렬 속도(average sorting rate) 출처: https://st-lab.tistory.com/195

---

◎정렬 알고리즘 구현-github

github.com/jerry-ryu/java_problemsolving_algorithm/tree/main/sorting_algorithm

jerry-ryu/java_problemsolving_algorithm