Test110 ~ 114 정렬 알고리즘

   ○ 정렬
      : 데이터를 특정한 규칙(기준)에 맞게 순서대로 나열(오름차순, 내림차순)

   ○ 정렬의 목적
      : 데이터 처리 과정의 편의성이나 가독성을 높이기 위함
    → 보기 좋게... 검색하기 위함

   ○ 정렬의 종류
      : 선택 정렬, 버블 정렬, 삽입 정렬, 힙 정렬, 퀵 정렬, 쉘 정렬, ...


 실행 예)
 Source Data : 52 42 12 62 60
 Sorted Data : 12 42 52 60 62
 계속하려면 아무 키나 누르세요...

---

① 삽입 정렬

 

삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. k번째 반복 후의 결과 배열은, 앞쪽 k + 1 항목이 정렬된 상태이다.

 

삽입 정렬 알고리즘

public class Test110
{
	public static void main(String[] args)
	{
		int[] a = {52, 42, 12, 62, 60};
		int i, j;
		// 정렬 전 데이터
		System.out.print("Source Data : ");
		for (int n: a)
			System.out.print(n + " ");
		System.out.println();
		//--==>> Source Data : 52 42 12 62 60
		
		// Selection Sort 구현
		for (i = 0; i < a.length - 1; i++)		// 비교 기준 데이터(0    1   2  3)
		{											//					|    |   |  |
			for (j = i + 1; j < a.length; j++)  // 비교 대상 데이터(1234 234 34 4)
			{	
				/*
				if(비교기준이 비교대상보다 크다면)
				{
					자리바꿔라
				}
				*/
		
				// if(a[i] < a[j])		// 내림차순 정렬
				if (a[i] > a[j])		// 오름차순 정렬
				{
					a[i]=a[j]^a[i];
					a[j]=a[i]^a[j];
					a[i]=a[j]^a[i];
				}
			}
		}

		System.out.print("Sorted Data : ");
		for(int n : a)
			System.out.print(n + " ");
		System.out.println();	
	}
}

// 실행 결과
/*
Source Data : 52 42 12 62 60
Sorted Data : 12 42 52 60 62
계속하려면 아무 키나 누르십시오 . . .
*/

---

② 버블 정렬

 

버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, … 이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬한다. 

 

1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 자료까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다. 

 

 

버블 정렬 알고리즘

 

 

		// 정렬 전 데이터
		int[] a = {52, 42, 12, 62, 60};
		int i, j;
		System.out.print("Source Data : ");
		for(int n : a)
			System.out.print(n + " ");
		System.out.println();
        
      	  	// Bubble Sort 구현
		for (i = 1; i < a.length; i++)			
		{
			for (j = 0; j < a.length-i; j++)	
			{
				// 테스트(확인)
				//System.out.print("[" + j + "," + (j + 1) + "]");
				//--==>> [0,1][1,2][2,3][3,4][0,1][1,2][2,3][0,1][1,2][0,1]
				
				if (a[j] > a[j+1])	// 오름차순 정렬
				{
					a[j] = a[j]^a[j+1];
					a[j+1] = a[j]^a[j+1];
					a[j] = a[j]^a[j+1];
				}
			}
		}

		// 결과 출력
		System.out.print("Sorted Data : ");
		for(int n : a)
			System.out.print(n + " ");
		System.out.println();

	}
}

// 실행 결과

/*
Source Data : 5 4 3 2 1
Sorted Data : 1 2 3 4 5
계속하려면 아무 키나 누르십시오 . . .
*/

 

---

 

③ 삽입 정렬

 

삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. k번째 반복 후의 결과 배열은, 앞쪽 k + 1 항목이 정렬된 상태이다.

 

삽입 정렬 알고리즘

 

		int[] a = {52, 42, 12, 62, 60};
		//int[] a = {5,4,3,2,1};
		int i, j;
		
		System.out.print("Source Data : ");
		for(int n : a)
			System.out.print(n + " ");
		System.out.println();
		
		
		// 삽입 정렬
		for (i = 1; i < a.length; i++)		// i = 1
		{
			int tmp = a[i];			//tmp = 42
			j = i-1;			//j = 0

			while((j >= 0) && (a[j] > tmp))	// true && true
			{
				a[j+1] = a[j];		//a[1] = 52		→ 52 52 12 62 60
				j--;			// j = -1
			}
			a[j+1] = tmp;			//a[0] = 42		→ 42 52 12 62 60

		}

		// 결과 출력
		System.out.print("Sorted Data : ");
		for(int n : a)
			System.out.print(n + " ");
		System.out.println();


// 실행 결과

/*
Source Data : 52 42 12 62 60
Sorted Data : 12 42 52 60 62
계속하려면 아무 키나 누르십시오 . . .
*/

 

---

④ 향상된 버블 정렬

 

 앞에서 확인해 본 Selection Sort(Test110) 나 Bubble Sort(Test111)의 성능은 같다.
   (→ 반복의 횟수로 추정)
   하지만, 향상된 Bubble Sort 는 대상 데이터의 구조에 따라
   일반 Bubble Sort 나 Selection Sort 보다 성능이 좋게 나타날 수 있다.

원본 데이터 : 61 15 20 22 30
  15 20 22 30 61 - 1회전 (스왑 발생 → true) → 다음 회전 진행 ○
  15 20 22 30 61 - 2회전 (스왑 발생 → false)   → 다음 회전 진행 Ⅹ 

==> 1회전 수행... 2회전 수행... 을 해보았더니
       2회전에서 스왑(자리바꿈)이 전혀 일어나지 않았기 때문에
       불필요한 추가 연산(더 이상의 회전)은 무의미한 것으로 판단하여
       수행하지 않는다.

 

향상된 버블정렬 알고리즘

		int[] a = {10, 50, 22, 31, 43};
		//int i, j;
		int cnt = 0;
		boolean swap = true;
		
		boolean flag;
		int pass = 0;

		System.out.print("Source Data : ");
		for(int n : a)
			System.out.print(n + " ");
		System.out.println();
		
		//향상된 버블 정렬(Bubble Sort)
		do
		{
			// 테스트 확인
			//System.out.println("반복문 수행");		//-- 2회전 확인


			flag = false;	//-- 자리바꿈이 발생할 경우 true 로 설정
			pass++;

			for (int i = 0; i < a.length-pass; i++)	// 0 1 2 3 / 0 1 2 / 0 1 / 0
			{
				//System.out.println(쑝);

				if (a[i] > a[i+1])		// 01 12 23 34
				{						// 01 12 23
					//자리바꾸기		// 01 12
					a[i]=a[i]^a[i+1];   // 01
					a[i+1]=a[i+1]^a[i];
					a[i]=a[i]^a[i+1];
					flag =true;
					//-- 단 한 번이라도 스왑(자리바꿈)이 발생하게 되면
					//   flag 변수를 true 로 변경하여
					//   다음 회전을 추가로 진행할 수 있도록 처리
				}				   
			}
		}
		while (flag);
		//-- flag 변수가 false 라는 것은
		//   회전이 구분적으로 발생하는 동안 스왑이 일어나지 않은 경우
		//   더 이상의 반복문 수행은 무의미한 것으로 판단 가능~!!!

		// 결과 출력
		System.out.print("Sorted Data : ");
		for(int n : a)
			System.out.print(n + " ");
		System.out.println();