(한번에보기)배열개념,정렬,검색 알아보자

이번 시간에는 참조형 자료형중 하나인 배열에 대해서 알아 보겠습니다. 배열은 여러방면에서 유용하게 사용되는 자료형입니다.

 1. 배열이란? 

- 동일한 자료형으로 구성된 연속된 자료의 집합

- 자바의 배열은 힙 메모리(레퍼런스 타입)를 할당

- 첨자는 0부터 시작

- 간단한 예시

- 배열 선언 : int[] data;

- 메모리 할당 : data = new int[10];

- 배열 요소의 이용 : data[0] = 10

- 배열의 데이터 개수는 length라는 속성으로 제공 = 배열명.length

- 일반 배열(정적 배열)의 장점 : 접근 방법이 쉽다.

- 일반 배열(정적 배열)의 단점 : ① 생성 시 크기를 결정하면 변경X

 ② 연속된 메모리 공간을 사용하므로 연속된 빈 공간이 없으면 생성X

③ 데이터를 정렬해두지 않으면 검색 속도가 느리다.

④ 데이터의 삽입과 삭제가 어렵다.

<예제 소스코드 - OneArray.class>

public class OneArray 
{
    public static void main(String[] args) 
    {
        // 배열 선언 및 초기화
        int [] ar = {10,20,30};
        
        for(int i=0; i<ar.length; i++)
        {
            System.out.println("ar[" + i + "]=" + ar[i]);
        }
    }
}
 

<결과>

 2. 다차원 배열 

- 2차원 배열

- 배열의 크기 : 행과 열로 구분해서 표현

- 배열의 선언 : 자료형 [][] 배열명; OR 자료형 배열명 [][];

- 배열의 생성(배열의 메모리 할당)

 - 배열명 = new 자료형[행][열];

 - Ex) int [][] a = new int[2][3];    // 2행 3열의 배열(2x3행열)

<예제 소스코드 - DoubleArray.class>

public class DoubleArray 
{
    public static void main(String[] args) 
    {
        // 2차원배열 선언과 동시에 초기화
        int[][] ar = { { 10, 20 }, { 30, 40 } };
        int i, j;
        
        // 행과 열을 출력하기위해 반복문 2
        for (i = 0; i < ar.length; i++) 
        {
            for (j = 0; j < ar[i].length; j++)
                System.out.print("  " + ar[i][j]);
            System.out.println();
        }
    }
}

<결과>

 3. 가변 배열 

- 자바는 배열을 참조형으로 처리하므로 가변 배열 선인이 가능

- 가변(可變) : 사물의 모양이나 성질이 바뀌거나 달라질 수 있음. 또는 사물의 모양이나 성질을 바꾸거나 달라지게 할 수 있음.

- Ex) int [][] var = new int[3][]

var[0] = new int[1]

var[1] = new int[2]

var[2] = new int[3]

<예제 소스코드 - VarialbeArray.class>

public class VariableArray 
{
    public static void main(String args)
    {
        // 가변 배열 선언
        int[][]ar = new int[3][];
        int i, j = 0;
        
        // 가변 배열 메모리 할당
        ar[0] = new int[1];
        ar[1] = new int[2];
        ar[2] = new int[3];
        
        // 배열 
        ar[0][0] = 10;
        ar[1][0] = 20;
        ar[1][1] = 30;
        ar[2][0] = 40;
        
        for(i = 0 ; i < ar.length ; i++)
        {
            for(j = 0 ; j < ar[i].length ; j++)
            {
                System.out.print("ar[" + i + "]" + "[" + j + "]=" + ar[i][j] + " ");
            }
            System.out.println();
        }
    }
}

<결과>

 4. 정렬 

- 정렬은 데이터를 순서대로 나열하는 것을 의미합니다.

⑴ 선택정렬(Selection Sort)

- 선택정렬은 첫 번째 자리부터 마지막에서 두 번째 자리까지 자신보다 뒤에 있는 모든 자리들과 비교해서 다음 자료가 작으면 2개의 요소의 자리를 변경해줍니다. 

<초기상태>

5

4

1

2

3

↓1번째 자리를 기준으로 2,3,4,5 번째 자리와 비교

<1Pass>

1

5

4

2

3

↓1번째 자리는 제외하고 2번째 자리를 기준으로 3,4,5 번째 자리와 비교

<2Pass>

1

2

5

4

3

↓3번째 자리를 기준으로 4,5 번째 자리와 비교

<3Pass>

1

2

3

5

4

↓4번째 자리를 기준으로 5 번째 자리와 비교

<4Pass>

1

2

3

4

5

<예제 소스코드 - SelectionSort.class>

public static void main(String args[])
{
        // 정렬할 배열 초기화
        int test[] = { 20, 30, 40, 50, 10 };
        int i, j, temp;
        
        System.out.println("정렬 전");
        
        // 정렬전 데이터 출력
        for(i = 0 ; i < 5 ; i++)
        {
            System.out.println((i + 1) + "번째 데이터" + test[i]);
        }
        
        // 선택 정렬
        for(i = 0 ; i < 4 ; i++)
        {
            for(j = i+1 ; j < 5 ; j++)
            {
                if(test[i] < test[j])
                {
                    temp = test[i];
                    test[i] = test[j];
                    test[j] = temp;
                }
            }
        }
        
            System.out.println("=====================");
             System.out.println("=====================");
            System.out.println("정렬 후");
        
        // 선택후     
        for( i = 0 ; i < 5 ; i++)
        {
            System.out.println((i+1) + "번째 데이터" + test[i]);
        }
        
}

<결과>

⑵ 버블정렬(Bubble Sort)

- 버블 정렬은 n개의 데이터가 있을 때 1부터 n-1번째 자료까지 n-1번 동안 다음 자료와 비교해가며 정렬하는 방법 입니다.

※빨간색칸은 정렬 대상, 파란색칸은 완료 된 원소

<초기상태> 

7

4

11

9

2

<1Pass과정>

4

7

11

9

2

4

7

11

9

2

4

7

9

11

2

4

7

9

2

11

<2Pass과정>

4

7

9

2

11

4

7

8

2

11

4

7

2

9

11

<3Pass과정>

4

7

2

9

11

4

2

7

9

11

<4Pass과정>

2

4

7

9

11

<예제 소스코드 - BubbleSort.class>

public class BubbleSort 
{
    public static void main(String[] args) 
    {
        // 정렬 할 배열 선언
        int test[] = { 20, 30, 40, 50, 10 };
        int i, j, temp, flag;
        System.out.println("정렬 전");
        for (i = 0; i < 5; i++)     // 정렬 전 배열 출력
        {
            System.out.println((i + 1) + "번째 데이터" + test[i]);
        }
        
        // 버블 정렬
        for (i = 0; i < 4; i++) 
        {
            flag = 0;
            for (j = 0; j < 4 - i; j++) 
            {
                if (test[j] < test[j + 1]) 
                {
                    temp = test[j];
                    test[j] = test[j + 1];
                    test[j + 1] = temp;
                    flag = 1;
                }
            }
 
            if (flag == 0) 
            {
                break;
            }
        }
        
        System.out.println("=====================");
        System.out.println("=====================");
        System.out.println("정렬 후");
        for (i = 0; i < 5; i++)     // 정렬 후 배열 
        {
            System.out.println((i + 1) + "번째 데이터" + test[i]);
        }
    }
}

<결과>

 5. 검색 

- 검색이란 말그대로 원하는 원소를 찾는 것 입니다.

⑴ 순차 검색(SequentialSearch)

- 데이터가 정렬되어 있지 않은 경우 첫 번째 데이터부터 마지막 데이터까지 모두 검색해서 찾는 방법입니다.

- 데이터가 많거나 찾고자 하는 데이터가 배열에 없는 경우가 많을 경우 매우 비효율적인 방ㅂ법입니다.

<초기상태> 

7

4

11

9

2

--------------------------------------------------------------------------------------------->

- 찾는 수가 11일때 하나하나 확인해 가며 11을 찾는 것이다.

<예제 소스코드 - SequentialSearch.class>

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class SequentialSearch 
{
    public static void main(String[] args) 
    {
        // 배열 초기화
        int ar[] = { 23, 47, 19, 63, 57, 26, 75, 73, 82, 89, 47, 11 };
        int i, num;
        int key = 0, index = 0;
        num = ar.length;    // 배열의 길이
        
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        System.out.print("찾고자 하는 숫자를 2자리로 입력하세요: ");
        
        try 
        {
            key = Integer.parseInt(in.readLine());            
        } catch (Exception e)    // 예외 처리 
        {
            System.out.println("입력 오류");
        }
        
        // 배열의 길이 만큼 반복
        for (i = 0; i < num; i++) 
        {
            // 키값과 벼열의 값이 같아질경우
            // i+1값이 인덱스로 저장
            if (ar[i] == key) 
            {
                index = i + 1;
            }
        }
        
        // 인덱스 0인경우 찾는 값이 없음
        if (index == 0) 
        {
            System.out.println("찾고자 하는 값이 없습니다.");
        }else    // 인덱스가 0이 아닐경우 위에 저장한 인덱스  
        {
            System.out.println("찾는 값은 " + index + "번째에 있습니다.");
        }
    }
}

<결과>

⑵ 이분 검색(Binary Search)

- 데이터가 정렬되어 있는 경우 중앙 값과 비교해서 작으면 왼쪽, 크면 오른쪽으로 이동해서 검색하는 방법입니다.

① low = 0, high = n(데이터 개수) - 1로 초기화

② 무한 반복문에서 low> high 이면 데이터가 없는것 -> break

③ 아닐시 middle = (low + high)/2를 해서 middle값 찾기

④ 검색 값과 data[middle]과 비교해서 같으면 출력후 break

⑤ 검색 값이 중앙값보다 크다면 low = middle + 1

⑥ 작다면 high = middle -1 을 해서 loop를 돌리면 됩니다.

<예제 소스코드 - BinarySearch.class>

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class BinarySearch 
{
    public static void main(String args[])
    {
        // 배열 초기화
        int data[] = { 11, 16, 21, 26, 35, 39, 47 };
        int k = 0, cnt = 0;
        int low = 0;
        int high = data.length - 1;
        int middle;
        
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        System.out.print("찾고자 하는 숫자를 2자리로 입력하세요: ");
        
        try
        {
            k = Integer.parseInt(in.readLine());
        }catch(Exception e) // 예외 처리
        {
            System.out.println("입력 오류");
        }
        
        // 무한 반복문 사용
        while (true)
        {
            if(low > high)    // low값이 high값 보다 커질시 데이터가 없음
            {
                System.out.println("검색 데이터가 없습니다.");
                break;
            }
            middle = ( low + high ) / 2; // 중앙값 구하기
            cnt++; // 몇번 만에 찾는지 확인하기위한 카운트 변수 증가
            
            System.out.println("비교값 : " + data[middle]);
            
            if( data[middle] == k )    // key값과 인덱스가 중앙값인 배열과 같을시 찾음
            {
                System.out.println( middle + 1 + "번쨰 위치 검색횟수 = " + cnt + "번" );
                break;
            }
            // 키값이 더 클시 low 값을 +1
            if( k > data[middle] )
            {
                low = middle + 1;
            }else    // 키값보다 작을시 high값을 중앙값-1
            {
                high = middle - 1;
            }
        }
    }
}
 

<결과>

이번 시간에는 배열과 더 나아가서 정렬과 검색을 간단한 예제를 통해 알아보았습니다.

출처: http://raccoonjy.tistory.com/13?category=744507