11장 정렬 교환 방식<선택 정렬, 버블 정렬, 퀵 정렬>

정렬

순서 없이 배열되어 있는 자료들을 작은 것부터 큰 것 순서의 오름차순이나 큰 것부터 작은 것 순서의 내림차순으로 재배열하는 것이다. 정렬 방법은 수행되는 위치에 따라서 컴퓨터 메모리 내부에서 수행하는 내부 정렬과 메모리의 외부인 보조 기억 장치에서 수행하는 외부 정렬로 분류할 수 있고, 수행 방법에 따라 비교식 정렬과 분산식 정렬로 구분할 수 있다.

 

내부 정렬

1. 교환 방식 - 키를 비교하고 교환하여 정렬하는 방식(선택, 버블, 퀵)

2. 삽입 방식 - 키를 비교하고 삽입하여 정렬하는 방식(삽입, 셸)

3. 병합 방식- 키를 비교하고 병합하여 정렬하는 방식(2-way 병합, n-way 병합)

4. 분배 방식 - 키를 구성하는 값을 여러 개의 부분집합에 분배하여 정렬하는 방식(기수)

5. 선택 방식 - 이진 트리를 사용하여 정렬하는 방식(힙, 트리)

 

정렬되지 않은 { 69, 10, 30, 2, 16, 8, 31 }을 예시로 들겠다.

선택 정렬

전체 원소들 중에서 선택하여 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식으로 정렬한다.

 

1. 첫 번째 자리를 기준 위치로 정하고, 전체 원소 중에서 가장 작은 원소 2를 선택하여 기준 위치에 있는 원소 69와 자리를 교환한다.

2. 두 번째 자리를 기준 위치로 정하고, 나머지 원소 중에서 가장 작은 원소 8을 선택하여 기준 위치에 있는 원소 10과 자리를 교환한다.(룰에 따라 교환)

3. 여섯 번째 자리를 기준 위치로 정하고, 나머지 원소 중에서 가장 작은 원소 30을 선택하여 기준 위치에 있는 원소 30과 자리를 교환한다.(제자리)

4. 일곱 번째 자리를 기준 위치로 정하고, 나머지 원소 중에서 가장 작은 원소 31을 선택하여 기준 위치에 있는 원소 31과 자리를 교환한다.(제자리)

class Sort {
	public void selectionSort(int a[]) {
		int i, j, min;
		
		for(i=0 ; i<a.length-1 ; i++) {
			min = i;
			for(j=i+1 ; j<a.length ; j++) {
				if(a[j] < a[min])
					min = j;
			}
			swap(a, min, i);
			System.out.printf("\n선택 정렬 %d 단계 : ", i+1);
			for(j=0; j<a.length ; j++) {
				System.out.printf("%3d ", a[j]);
			}
		}
	}

	public void swap(int[] a, int i, int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;		
	}
}

public class selectA {

	public static void main(String[] args) {
		int a[] = {69, 10, 30, 2, 16, 8, 31, 22};
		Sort S = new Sort();
		System.out.printf("\n정렬할 원소 ");
		for(int i=0 ; i<a.length; i++) {
			System.out.printf(" %d ", a[i]);
		}
		System.out.println();
		S.selectionSort(a);

	}

}

 

 

버블 정렬

인접한 두개의 원소를 비교하여 자리를 교환하는 방식을 첫 번째 원소부터 마지막 원소까지 반복하여 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬된다.

 

1. 인접한 두 원소를 비교하여 자리를 교환하는 작업을 첫 번째 원소부터 마지막 원소까지 차례로 반복하여 가장 큰 원소 69를 마지막 자리로 정렬한다.

2. 나머지 원소 중에서 가장 큰 원소 31을 끝에서 두 번째로 자리로 정렬한다.

3. 나머지 원소 중에서 가장 큰 원소 30을 끝에서 세 번째로 자리로 정렬한다.(룰에 따라 반복)

4. 나머지 원소 중에서 가장 큰 원소 8을 끝에서 일곱 번째 자리로 정렬한다. 마지막에 남은 첫 번째 원소는 전체 원소 중에서 가장 작은 원소로 이미 맨 앞자리로 정렬된 상태 이므로 실행을 종료하고 버블 정렬이 완성된다.

class Sort {
	public void bubbleSort(int a[]) {
		int i, j, temp, size;
		size = a.length;
		for(i=size-1 ; i>0 ; i--) {
			System.out.printf("\n버블 정렬 %d 단계 : ", size-i);
			for(j=0 ; j<i ; j++) {
				if(a[j] > a[j+1]) {
					temp = a[j];
					a[j] = a[j+1];
					a[j+1] = temp;
				}
				System.out.printf("\n\t");
				for(int k=0 ; k<size ; k++) {
					System.out.printf("%3d ", a[k]);
				}
			}
		}
	}
}

public class bubbleA {
	public static void main(String[] args) {
		int a[] = {69, 10, 30, 2, 16, 8, 31, 22};
		Sort S = new Sort();
		System.out.printf("\n정렬할 원소 : ");
		for(int i=0 ; i<a.length ; i++) {
			System.out.printf(" %d", a[i]);
		}
		System.out.println();
		S.bubbleSort(a);
	}
}

 

퀵 정렬

정렬할 전체 원소에 대해서 정렬을 수행하지 않고 기준 값을 중심으로 왼쪽 부분 집합과 오른쪽 부분집합으로 분할한다. 왼쪽 부분집합에는 기준 값보다 작은 원소들을 이동시키고, 오른쪽 부분집합에는 기준 값보다 큰 원소들을 이동시킨다.

 

1. 원소의 개수가 8개 이므로 네번째 자리에 있는 원소 2를 첫 번째 피봇으로 선택하고 시작한다.

2. L이 오른쪽으로 이동하면서 피봇보다 크거나 같은 원소를 찾고, R은 왼쪽으로 이동하면서 피봇보다 작은 원소를 찾는다. L은 원소 69를 찾았지만, R은 피봇보다 작은 원소를 찾지 못한 채 원소 69에서 L과 만나게 된다. L과 R이 만났으므로 원소 69를 피봇과 교환하고 피봇 원소 2의 위치를 확정한다.

3. 피봇 2의 왼쪽 부분집합은 공집합이므로 퀵 정렬을 수행하지 않고, 오른쪽 부분 집합에 대해서 퀵 정렬을 수행한다. 오른쪽 부분집합의 원소가 7개이므로 가운데 있는 원소 16을 피봇으로 한다.

4. L이 오른쪽으로 이동하면서 피봇보다 크거나 같은 원소를 찾고, R은 왼쪽으로 이동하면서 피봇보다 작은 원소를 찾는다. L이 찾은 30과 R이 찾은 8을 서로 교환한다.

5. 현재 위치에서 L은 다시 오른쪽으로 이동하면서 피봇보다 크거나 같은 원소를 찾고, R은 왼쪽으로 이동하면서 피봇보다 작은 원소를 찾는다. L은 원소 69를 찾았지만, R은 피봇보다 작은 원소를 찾지 못한 채로 원소 69에서 L과 만나게 된다. L과 R이 만났으므로 원소 69를 피봇과 교환하고 피봇 원소 16의 위치를 확정한다.

6. 피봇 16의 왼쪽 부분집합에서 원소 10을 피봇으로 선택하여 퀵 정렬을 수행한다.

7. L은 오른쪽으로 이동하면서 피봇보다 크거나 같은 원소를 찾고, R은 왼쪽으로 이동하면서 피봇보다 작은 원소를 찾으므로 L의 원소 10과 R의 원소 8을 교환하는데, L의 원소가 피봇이므로 피봇 원소 10의 위치가 확정된다.(룰에 따라 반복)

8. L은 오른쪽으로 이동하면서 피봇보다 크거나 같은 원소인 31을 찾고, R은 왼쪽으로 이동하면서 피봇보다 작은 원소를 찾다가 원소 31에서 L과 만난다. L과 R이 만났으므로 피봇과 교환하는데, 이때 R의 원소가 피봇이므로 결국 제자리가 피봇 원소 31의 자리로 확정된다.

package array;

class Sort3 {
	int i=0;
	public int partition(int a[], int begin, int end) {
		int pivot, temp, L, R, t;
		L = begin;
		R = end;
		pivot = (begin + end)/2;
		System.out.printf("\n [퀵정렬 %d 단계 : pivot=%d ]\n", ++i, a[pivot]);
		while(L<R) {
			while((a[L]<=a[pivot]) && (L<=R)) L++;
			while((a[R]>a[pivot]) && (L<=R)) R--;
			if(L<R) {
				temp = a[L];
				a[L] = a[R];
				a[R] = temp;
				
				if(L == pivot) { //L과 R원소를 교환하여 결과적으로 피봇원소의 위치가 변경된 경우
					for(t=0 ; t<a.length ; t++)
						System.out.printf("%3d ", a[t]);
					System.out.println();
					return R;
				}
			}
		}
		// (L>R)이 된 경우
		temp = a[pivot];
		a[pivot] = a[R];
		a[R] = temp;
		for(t=0 ; t<a.length ; t++)
			System.out.printf("%3d  ", a[t]);
		System.out.println();
		return R;
	}
	
	public void quickSort(int a[], int begin, int end) {
		if(begin < end) {
			int p;
			p = partition(a, begin, end);
			quickSort(a, begin, p-1);
			quickSort(a, p+1, end);
		}
	}
	
}

public class quitA {

	public static void main(String[] args) {
		int a[] = {69, 10, 30, 2, 16, 8, 31, 22};
		Sort3 S = new Sort3();
		System.out.printf("\n정렬할 원소 : ");
		for(int i=0 ; i<a.length ; i++) {
			System.out.printf("%3d", a[i]);
		}
			
		System.out.println();
		S.quickSort(a, 0, 7);

	}

}