숙제 : 정렬을 구현하여 보자.

버블 정렬이란?

• 배열에 7, 4, 5, 1, 3이 저장되어 있다고 가정하고 자료를 오름차순으로 정렬해 보자.

위의 알고리즘을 참고 하여 아래의 함수를 구현하시오.

int[] 배열을 전달 정렬된 배열을 반환..

public int[] bubuleSort(int n, int[] arr)

풀이

	public static int[] bubuleSort(int n, int[] arr) {
		
		for(int i = 0; i < n; i++) {
	        
			for(int j = 0 ; j < n - i - 1 ; j++) {
	            
	        	if(arr[j] > arr[j+1]) {
	                int temp = arr[j+1];
	                arr[j+1] = arr[j];
	                arr[j] = temp;
	            }
	        	
	        }
	    }
		
		return arr;		
	}

선택정렬(Selection Sort) 이란?

과정 설명

1) 주어진 배열 중에서 최솟값을 찾는다.
2) 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
3) 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
4) 하나의 원소만 남을 때까지 위의 1~3 과정을 반복한다

위의 알고리즘을 참고 하여 아래의 함수를 구현하시오.

• 1회전 후는 첫번째자리 한자리는 무조건 정렬이 된다.

public int[] selectionSort(int n, int[] arr)

풀이

public static int[] selectionSort(int n, int[] arr) {
		int minIndex, temp;
		
		for(int i = 0; i < n - 1; i++) {
			minIndex = i;	
			
			// 최솟값을 갖고있는 인덱스 찾기 
			for(int j = i + 1; j < n; j++) {
				if(arr[j] < arr[minIndex]) {
					minIndex = j;
				}
			}
			
			// 4. 자리바꿈
	        temp = arr[minIndex];
	        arr[minIndex] = arr[i];
	        arr[i] = temp;	       	
		}
		
		 return arr;
	}

삽입정렬(Insersion Sort) 이란?

삽입 정렬의 전체적인 과정은 이렇다. (오름차순을 기준으로 설명)

public int[] solution(int n, int[] arr)

1. 현재 타겟이 되는 숫자와 이전 위치에 있는 원소들을 비교한다. (첫 번째 타겟은 두 번째 원소부터 시작한다.)

2. 타겟이 되는 숫자가 이전 위치에 있던 원소보다 작다면 위치를 서로 교환한다.

3. 그 다음 타겟을 찾아 위와 같은 방법으로 반복한다.

풀이

int [] arr = {8,5,6,2,4};				
				
		for (int i = 1; i < arr.length; i++) {			
			
			int key = arr[i];  // 기준			
			int aux = i - 1;   // 비교할 대상						
			
			while (aux >= 0 && key < arr[aux]) {				
				arr[aux + 1] = arr[aux];   // 비교대상이 큰 경우 오른쪽으로 밀어냄				
				aux--;			
			}			
			
			arr[aux + 1] = key;  // 기준값 저장		
			}
		}