정렬(Sort)

선택 정렬(Selection Sort) : 첫번째 인덱스부터 뒤에 있는 인덱스들과 비교를 통해 가장 작은 것을 선택해서 앞으로 보내는 과정을 반복 맨 마지막 인덱스는 비교대상이 없으므로 수행하지 않는다.(오름차순 기준)

 

public class SelectSort {

	public static void main(String[] args) {
		int[] array = {0, 3, 9, 5, 7};
		int count = 0; // 정렬하기 위해 데이터를 비교한 횟수 
		
		// 오름차순 선택정렬 수행 
		int min_index = 0;
		for(int i=0;i<array.length-1;i++) {
			min_index = i;
			for(int j=i+1;j<array.length;j++) {
				count++;
				if(array[min_index] > array[j]) {
					min_index = j;
				}
			}
			// min_index 와 정렬되지 않은 데이터의 위치를 바꿔줌(스와프 기법 사용)
			int temp = array[i];
			array[i] = array[min_index];
			array[min_index] = temp;
		}

		// 정렬된 데이터 출력 (개선된 for문 사용)
		for(int data : array) {
			System.out.print(data+" ");
		}
		System.out.println("데이터 비교 횟수:"+count); // 10번 수행 
	}

}

 

삽입 정렬(Insertion Sort) : 두번째 인덱스부터 시작해서 마지막 인덱스까지 해당 인덱스를 왼쪽을 기준으로 차례대로 첫 번째 인덱스까지 비교하면서 삽입이 될 장소를 찾음 

 

public class InsertSort {

	public static void main(String[] args) {
		int[] array = {0, 3, 9, 5, 7};
		int count = 0; // 정렬하기 위해 데이터를 비교한 횟수
		
		// 오름차순 
		for(int i=1;i<array.length;i++) {
			// 삽입이 될 인덱스가 5번째 인덱스라면 4번째 인덱스부터 차례대로 비교함 
			for(int j=i;j>0;j--) {
				count++;
				// 한 칸씩 왼쪽으로 이동 
				if(array[j] < array[j-1]) {
					int temp = array[j-1];
					array[j-1] = array[j];
					array[j] = temp;
				}
				// 자신보다 작은 데이터를 만나면 그 위치에서 멈춤 
				else break;
			}
		}

		for(int data : array) {
			System.out.print(data+" ");
		}
		System.out.println("데이터 비교 횟수:"+count); // 6번 수행 
		
		// 내림차순 (데이터가 큰것부터 정렬) 
		for(int i=1;i<array.length;i++) {
			// 삽입이 될 인덱스가 5번째 인덱스라면 4번째 인덱스부터 차례대로 비교함 
			for(int j=i;j>0;j--) {
				// 한 칸씩 왼쪽으로 이동 
				if(array[j] > array[j-1]) {
					int temp = array[j-1];
					array[j-1] = array[j];
					array[j] = temp;
				}
				// 자신보다 큰 데이터를 만나면 그 위치에서 멈춤 
				else break;
			}
		}

		for(int data : array) {
			System.out.print(data+" ");
		}
		
	}

}

 

- 무조건 모든 데이터를 비교를 해서 정렬을 하는 선택 정렬과는 다르게 삽입될 해당 지점까지 비교를 하고 for문을 빠져나가기 때문에 데이터가 거의 정렬되어 있을 때 삽입 정렬을 사용한다면 해당 프로그램은 훨씬 빠르게 동작함