2020년 10월 15일

정렬

삽입 정렬

삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 삽입하는 알고리즘이며, 배열이 길어질수록 효율이 떨어지지만 구현이 간단하다. 선택 정렬이나 거품 정렬과 같은 알고리즘에 비해 빠르다.

삽입정렬 위키백과

int[] arr = {2, 5, 4, 1, 3};

for(int i = 1; i < arr.length; i++){
    System.out.println("비교 주체 : " + arr[i]);
    for(int j = i - 1; j >= 0; j--){
        if(arr[j+1] < arr[j]) {
            int temp = arr[j+1];
            arr[j+1] = arr[j];
            arr[j] = temp;
        }
    }
}

버블 정렬

버블(거품) 정렬은 두 인접한 원소를 검사하여 정렬한다. 속도는 느리지만 코드가 단순하고, 이미 정렬된 배열에 새로운 데이터를 추가해 재정렬 할 경우의 속도는 가장 빠르다.

버블정렬 위키백과

// 버블 정렬은 배열의 뒤쪽부터 정렬이 완성된다.
int[] arr = {2, 5, 4, 1, 3};

for(int i = 0; i < arr.length-1; i++){
    System.out.println(i + "회차");
    for(int j = 0; j < (arr.length -1) - i; j++) {
        if(arr[j+1] < arr[j]) {
            int temp = arr[j+1];
            arr[j+1] = arr[j];
            arr[j] = temp;
            System.out.println(Arrays.toString(arr));
        }
    }
}
 System.out.println("결과 : " + Arrays.toString(arr));

배열 중복 제거하기

// 중복된 값 입력 받지 않기
int[] arr = new[5];

for(int i = 0; i < arr.length; i++){
    System.out.print(i + "번 인덱스 값 입력 : ");
    arr[i] = sc.nextInt();
    for(int j = 0; j < i; j++){
        if(arr[i] = arr[j]) {
            System.out.println("이미 입력된 값입니다.");
            i--;
            break; // 중복된 값을 찾았으니 더 검사할 필요가 없으니 안 쪽 for문을 빠져나감
        }
    }
}

배열 복사

얕은 복사

객체의 주소 값만 가져와 참조형 변수에 저장하고 하나의 객체를 두 변수가 참조하는 것.

일반 변수의 경우 값을 복사하려면 다음과 같이 코드를 작성하면 된다.

int a = 10;
int b = a;

배열의 경우는 참조형이므로 arr[]에 담긴 값이 주소값이라 위와 같이 복사를 하면 다음과 같은 형태로 복사가 된다.

int[] arr = {1, 1, 2, 3, 5, 8, 13};
int[] copyArr = arr;

copyArr[0] = 100;

System.out.println("arr 배열 : " + Arrays.toString(arr));
System.out.println("copyArr 배열 : " + Arrays.toString(copyArr));

/* 출력
arr 배열 : [100, 1, 2, 3, 5, 8, 13]
copyArr 배열 : [100, 1, 2, 3, 5, 8, 13]
*/

이렇게 얕은 복사를 한 후 복사한 배열의 값을 변경하면, 같은 객체를 참조하고 있기 때문에 원본 배열의 값도 변경된다.

깊은 복사

새로운 배열 객체를 생성하여 기존 배열의 데이터를 복사하는 것.

깊은 복사는 for문 등을 사용해서 값을 복사한다. 주의할 점은 깊은 복사를 위한 배열 생성 시 해당 배열의 크기는 기존 배열의 크기보다 크거나 같아야한다.

//for문을 사용한 깊은 복사
int[] arr = {1, 1, 2, 3, 5, 8, 13};
int[] copyArr = new int[arr.length];

for(int i = 0; i < arr.length; i++){
    copy[i] = arr[i];
}

// Java에서 지원하는 기능을 이용한 깊은 복사
// System.arraycopy(원본배열명, 원본복사시작인덱스, 복사배열명, 복사배열에저장할 인덱스, 복사길이);
System.arraycopy(arr, 0, copyArr, 0, arr.length);

얕은 복사 + 깊은 복사로 배열의 크기 수정하기

// 배열은 한 번 선언한 크기의 배열을 변경할 수 없다.
// 배열의 크기를 변경하고 싶으면 얕은 복사와 깊은 복사를 사용해야 함.

// 정수를 입력받아 배열 요소에 각각 저장
// 단, 기존 배열 크기 이상의 값을 입력할 경우
// 배열의 크기를 2배 늘려서 값을 저장
//(0 입력 시 값 저장 종료 후 출력)

Scanner sc = new Scanner(System.in);
int[] arr = new int[3];

int i = 0;
while(true){
    System.out.print("arr[" + i + "] 입력 ");
    int input = sc.nextInt();
    
    if(input == 0){
        break;
    }

    if(i >= arr.length){
        int[] newArr = new int[arr.length * 2];
        // 깊은 복사 진행
        // 기존 배열의 내용을 크기가 늘어난 배열에 복사
        System.arraycopy(arr, 0, newArr, 0, arr.length);

        // 얕은 복사 진행
        // 기존 배열을 참조하던 변수에 새로운 배열의 주소를 복사
        arr = newArr;
    }
    arr[i] = input;
    i++;
}

for(int j = 0; j < arr.length; j++){
    if(arr[j] == 0){
        break;
    }
    System.out.print(arr[j]+ " ");
} 

2차원 배열

자료형이 같은 1차원 배열의 묶음으로 배열 안에 다른 배열이 존재
2차원 배열은 할당된 공간마다 인덱스 번호 두 개를 부여한다. 앞 번호는 행, 뒷 번호는 열을 의미한다.

// 배열 선언
int[][] arr;
int arr[][];
int[] arr[];

// 배열 할당
int[][] arr = new int[행크기][열크기];
int arr[][] = new int[행크기][열크기];
int[] arr[] = new int[행크기][열크기];

// for문을 이용한 초기화
for(int i = 0; i < arr.length; i++){
    for(int j = 0; j < arr[i].length; j++){
        arr[i][j] = j;
    }
}

// 선언과 동시에 초기화
int[][] arr = { {10, 20, 30}, {4, 5, 6}, {19, 17, 21} };

// 2차원 배열에 저장된 값 합계 구하기
int sum = 0;
for(int i = 0; i < arr.length; i++){
    for(int j = 0; j < arr[i].length; j++){
        sum += arr[i][j];
    }
}

System.out.println("합계 : " + sum);
System.out.println("평균 : " + (double)sum / (arr.length * arr[0].length) )