[JAVA] 정렬과 복사

[JAVA] 배열 연습

---

정렬

자바에서 취급하는 정렬은 대략 7가지 정도있다.

그 중 선택정렬/퀵정렬/버블정렬에 대한 내용이다.

---

선택 정렬

• 작은 값을 맨 앞으로 가져올 때 사용하는 정렬로, 퀵 정렬과 결과는 동일하다.

import java.util.Arrays;

public class arr_sort {

	public static void main(String[] args) {

		
		int[] arr = { 5, 23, 1 ,43, 200, 100 ,40};
		int temp;
		
		for(int i=0; i<arr.length-1; i++) {
			
			for(int j= i+1; j<arr.length; j++) {
				
				if(arr[j] < arr[i]) {
					temp = arr[j];
					arr[j] = arr[i];
					arr[i] = temp;
				}
			}
			System.out.println(Arrays.toString(arr));
			
		}
		System.out.println(Arrays.toString(arr));
	}

}

• 첫 번째 반복문에서는 배열 arr의 인접한 인덱스들끼리 비교하기 때문에 
• 배열의 크기만큼 반복하는 게 아닌, 크기보다 1작은 수 만큼 반복하게 된다.
• 두 번째 반복문에서는 첫 번째 인덱스와 나머지 인덱스들 전체를 비교하기 때문에
• 배열의 길이만큼 반복을 시켜준다.
• 그 이후, 첫 인덱스가 다음 인덱스보다 작을 때 위치를 변경시켜주는 소스를 구현한다.

---

퀵 정렬

• 퀵 정렬은 말 그대로 가장 빠른 속도로 정렬하는 구문으로, 선택 정렬과 결과 값이 동일하다.

int[] arr2 = {5,23,1,43,200,400,100};
Arrays.sort(arr2);
		
System.out.println(Arrays.toString(arr2));

• 위 소스코드와 같이 Arrays.sort를 사용하면 해당 배열 내의 인덱스들을 오름차순으로 정렬해준다. 

---

버블 정렬

• 버블정렬은 큰 값을 맨 앞으로 가져와 내림차순 순서대로 정렬해준다.]

int[] arr = {5,23,1,43,200,100,40};
		
for(int i =0; i<arr.length-1; i++) {
			
		for(int j=0; j<arr.length-i-1; j++) {
				
			if(arr[j] > arr[j+1]) {
					
				int temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;
					
			}
				
		}
			
	}

• 선택정렬과 거의 동일하게 인접한 인덱스들 간의 자리 교체가 필요하다 다만 차이점은
• 두번째 반복문에서 반복 횟 수를 i-1만큼 감소시켜줘야한다. 

---

복사

• 배열의 복사는 얕은 복사과 깊은 복사가 있다.
• 얕은 복사는 배열의 주소를 복사한다.
• 깊은 복사는 완전히 새로운 배열을 만들고 해당 값들을 모두 복사한다.

---

얕은 복사

int[] arr = {1,2,3,4,5};
int[] arr2 = arr;
		
arr2[0] = 100;
System.out.println(Arrays.toString(arr));
System.out.println(Arrays.toString(arr2));

• 첫 번째 배열의 arr을 두 번째 배열 arr2에 그대로 저장을 하면 얕은 복사가 성공한다.

---

깊은 복사

int[] newArr = new int[arr.length];
		
for(int i=0; i<newArr.length; i++) {
	newArr[i] = arr[i];
}
		
newArr[0] = 200;
		
System.out.println(Arrays.toString(newArr));

• 새로운 배열에 위 얕은 복사에서 구현한 arr 배열의 길이만큼 저장을 하여 새로운 배열을 만들어준다.
• 이후, 범위를 지정하여 배열의 인덱스를 생성을 해준다. 

배열의 끝에 값 추가하기

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
		
		int[] arr = {100,200,300,400,500};
		int value = 600;
		
		int[] arr2 = new int[arr.length + 1];
		
		for(int i=0; i<arr2.length-1; i++) {
			arr2[i] = arr[i];
		}
		
		arr2[arr2.length-1] = value;
		
		System.out.println(Arrays.toString(arr2));

	}

}

• 배열의 특성상 새로운 인덱스를 추가하는 것은 불가하지만 복사를 이용하여 새로운 배열에 값을 추가할 수 있다.
• 기존 arr 배열에 600을 추가하기 위해, 새로운 배열 arr2의 크기를 기존 arr배열의 크기보다 1큰 값을 넣어준다.
• 이후 arr 배열에서는 인덱스가 5개 들어있기 때문에 범위를 arr2.length-1의 크기만큼 반복을 하여 인덱스를 추가하고
• value 값을 반복문이 종료한 이후 5번 인덱스(0,1,2,3,4,5) 6번째 값에 추가해주기 위해, 전체 길이에서 -1을 한다.

---

배열 중간에 정수 추가하기

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {

		int[] a = {10,20,30,40,50};
		int[] b = new int[a.length+1];
		
		// 중간에 추가할 데이터
		int data = 100; // 추가할 값
		int target = 2; // 추가할 위치
		
		// 1. 배열을 옮겨담는다.
		// 2. 마지막부터 타켓까지 배열을 당긴다.
		// 3. 타켓의 데이터를 넣는다.
		
		for(int i=0; i<b.length-1; i++) {
			b[i] = a[i];
		}
		System.out.println("b 배열 : " + Arrays.toString(b));
		System.out.println();
		
		for(int i=b.length-1; i>target; i--) {
			b[i] = b[i-1];
		}
		
		b[target] = data;
		
		System.out.println("수정된 배열 : " + Arrays.toString(b));

	}

}

• 기본 배열 a 와 a배열의 길이보다 1큰 크기를 가진 배열이 주어진다.
• 배열 a의 인덱스를 배열 b의 인덱스에 복사를 해준다.
• b 배열의 인덱스를 뒤로 한칸씩 미루고, target의 지점에 data를 삽입해준다.
• 그러기 위해서는 b배열의 인덱스를 결정하는 반복문의 범위를 target까지 설정해준다. 
• 그리고 b배열의 target위치에 data를 저장하여 추가하면 된다.