[D+13] Sort, Bubble Sort

 

 

Algorithm

-  Sort, Bubble Sort -

 

---

 

Sort

Sort는 데이터를 기준에 따라 재배치하는 알고리즘이다.

 

목적) 

- Searching을 잘 하기 위해서

- 무차별적으로 나열되어있는 데이터 보다는 어떠한 기준에 맞추어 나열되어있는 것이 특정 데이터를 찾는데 훨씬 수월하다.

 

특징)

① 데이터의 위치만 바뀌는 것이지 데이터의 양이 바뀌는 것이 아니다.

② 다양한 기준이 존재한다. ex) 오름차순, 내림차순 등등...

 

 

---

Bubble Sort

- 서로 인접한 위치에 있는 두 값을 비교하여 크기가 순서대로 되어있지 않을 경우 위치를 변경하는 알고리즘

- (마지막-1)번째의 값과 마지막번째에 있는 값을 최종적으로 비교하고 나면 1회전이 끝난것이며, 이때 오름차순 기준으로 가장 마지막에 있는 값은 가장 큰 값이 배치되어있다.

- 마지막에 배치된 값은 정렬이 완료된 것으로 보기 때문에 이후에 더이상 크기를 비교하는 대상에서 제외된다.

- 어느정도 회전을 다 돌고 나서 1번째의 값만 남을경우 데이터가 하나밖에 없어 더이상 비교할 대상이 없기 때문에 정렬하지 않고 종료한다.

 

예시를 보면 이런식으로 한번 회전이 끝이 날때마다 끝의 값이 고정되고 더이상 비교하지 않는 것을 확인할 수 있으며, 결론적으로 버블정렬의 최종 목적은 끝의 값을 결정하기 위해서라고 할 수 있다.

 

• 구현코드

BubbleSort Class

public class BubbleSort3 {

	// 변수 선언
	private int[] arr;
	private int sortBy;
	
	///////////////////////////////////////////////////////////////////////////////////
	// Setter
	
	public void setArr(int[] arr)
	{
		this.arr = arr;
	}
	
	public void setSortBy(int sortBy)
	{
		this.sortBy = sortBy;
	}
	
	///////////////////////////////////////////////////////////////////////////////////
	// Getter
	
	public int[] getArr()
	{
		return arr;
	}
	
	public int getSortBy()
	{
		return sortBy;
	}
	
	///////////////////////////////////////////////////////////////////////////////////
	// Check sortBy
	
	public boolean agreeSortBy(int num)
	{
		if((num == 1) || (num == 2))
			return true;
		
		else return false;
	}
	
	///////////////////////////////////////////////////////////////////////////////////
	// Sort
	
	public void startSort()
	{
		if(getSortBy() == 1) ascSort();
		else descSort();
	}
	
	public void ascSort()
	{
		int compareCnt = arr.length - 1;
		int box;
		
		for(int i = 0; i < arr.length - 1; i++)
		{
			for(int j = 0; j < compareCnt; j++)
			{
				if(arr[j] > arr[j+1])
				{
					box = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = box;
				}
			}
			
			compareCnt--;
		}
	}
	
	public void descSort()
	{
		int compareCnt = arr.length - 1;
		int box;
		
		for(int i = 0; i < arr.length - 1; i++)
		{
			for(int j = 0; j < compareCnt; j++)
			{
				if(arr[j] < arr[j+1])
				{
					box = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = box;
				}
			}
			
			compareCnt--;
		}
	}
	
	
	///////////////////////////////////////////////////////////////////////////////////
	// Print arr
	
	public void printArr()
	{
		for(int i = 0; i < arr.length; i++)
		{
			System.out.print(arr[i] + " ");
		}
	}
	
}

 

main()

import java.util.Scanner;

/*
 * 1. 사용자에게 숫자를 입력받으시오
 * 그 숫자만큼 int 배열을 할당하시오 (예 10을 입력하면 int[10])
 * 2. 사용자에게 정렬기준 (오름차순/내림차순)을 입력받으시오 
 * 3. int 배열을 1 ~ 100 사이의 임의의 값으로 설정하시오 
 * 4. 이 배열을 사용자에게 받은 정렬기준에 따라 버블소트를 수행하시오 
 */

public class Test3 {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		BubbleSort3 bs = new BubbleSort3();
		
		// 1> 사용자에게 사이즈 크기 및 정렬기준 입력받기 
		
		System.out.print("원하는 배열의 크기를 입력해 주세요 : ");
		int size = scan.nextInt();		// 배열의 사이즈 
		
		System.out.print("원하시는 정렬기준을 참고하여 입력해 주세요 (1: 오름차순, 2: 내림차순) : ");
		int sortBy = scan.nextInt();	// 정렬기준 (1: 오름차순, 2: 내림차순)
		
		// ++ 올바를 정렬기준을 입력했는지 확인하기
		
		while(bs.agreeSortBy(sortBy) == false)
		{
			System.out.println("정렬 기준을 다시 확인해주세요");
			System.out.println("");
			
			System.out.print("원하시는 정렬기준을 참고하여 입력해 주세요 (1: 오름차순, 2: 내림차순) : ");
			sortBy = scan.nextInt();
			
			if(bs.agreeSortBy(sortBy) == true)
				break;
		}

		
		///////////////////////////////////////////////////////////////////////////////////
		// 2> 배열에 1 ~ 100 사이의 임의의값 설정하기
		
		int arr[] = new int[size];
		
		for(int i = 0; i < size; i++)
		{
			arr[i] = (int)(Math.random() * 100) + 1;
		}
		
		///////////////////////////////////////////////////////////////////////////////////
		// 3> 클래스를 new로 힙에 할당한 후 메소드 사용하기
		 
		bs.setSortBy(sortBy);
		bs.setArr(arr);
		bs.startSort();
		
		bs.printArr();
		 
	}

}