배열 삽입의 모든 것

배열에 삽입 작업은 총 3가지의 방법이 있습니다.

1. 배열의 끝에 요소를 삽입하기
2. 배열의 중간 위치에 요소를 삽입하기
3. 정렬된 배열에 요소 삽입하기

배열의 끝에 요소 삽입하는 방법

정렬되지 않은 배열에서는 요소가 배치될 위치에 신경 쓸 필요가 없기 때문에 정렬된 배열에 비해 삽입 작업이 더 빠릅니다.

public class InsertArray {
	public static void main(String[] args) {
		int capacity = 3;
		int[] arr = new int[capacity];
		int n = insertArr(arr, 0, 40, capacity);
		n = insertArr(arr, n, 20, capacity);
		n = insertArr(arr, n, 50, capacity);
		n = insertArr(arr, n, 30, capacity);
		
		for(int i = 0 ;i < n ; i++) {
			System.out.println(arr[i]);
		}
	}
	
	static int insertArr(int arr[], int n, int key, int capacity) {
		if(n >= capacity) return n;
		arr[n] = key;
		return n+1;
	}
}

배열이 가득차있으면 n를 리턴하고 아니면 삽입 후 n+1를 해서 리턴합니다.

 

배열의 중간 위치에 요소 삽입하는 방법

원하는 위치의 요소를 삽입 후 오른쪽에 있는 요소들을 한칸씩 이동하면서 삽입 작업을 하면 됩니다.

public class InserArrayPos {

	public static void main(String[] args) {
		int arr[] = new int[3];
		arr[0] = 5;
		arr[1] = 2;
		int n = 2;
		int x = 3, pos = 1;
		insertArr(arr,n,x,pos);
		
		for(int i = 0 ;i < 3 ; i++) {
			System.out.println(arr[i]);
		}
	}
	
	static void insertArr(int arr[], int n, int x, int pos) {
		for(int i = n - 1; i >= pos; i--) {
			arr[i + 1] = arr[i];
		}
		arr[pos] = x;
	}
}

 

정렬된 배열에서 삽입하는 방법

정렬된 배열에서는 이진 검색을 이용하여 주어진 요소의 가능한 위치를 검색한 후 삽입 작업을 수행하고 오른쪽 요소를 이동시킵니다.

public class insertArraySort {

	static int insertSorted(int arr[], int n, int key, int capacity) {
		if(n >= capacity) return n;
		
		int i;
		for(i = n - 1; i >= 0 && arr[i] > key; i--) {
			arr[i+1] = arr[i];
		}
		arr[i+1] = key;
		return n+1;
	}
	
	public static void main(String[] args) {
		int capacity = 5;
		int arr[] = new int[capacity];
		arr[0] = 12;
		arr[1] = 14;
		arr[2] = 16;
		arr[3] = 18;
		int n = 4;
		int key = 13;
		n = insertSorted(arr, n, key, capacity);
		for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
	}
}

key로 들어간 요소보다 큰 값이 있으면 오른쪽으로 이동시킨 후 정렬된 자리에 삽입합니다.