kungfugay's Blog

public class BubbleSort {
    public static void main(String[] args) {
        bubbleSort();
    }

    static void bubbleSort() {
        int[] arr = createIntArray(10000);

        long startTime = System.currentTimeMillis();
        // 현재 시간 기준의 Milli seconds

        for (int i=0; i<arr.length; i++) {
            for (int j=0; j<arr.length-1; j++) {
                if (arr[j] > arr[j+1]) {    // 부등호 뒤집으면? 내림차순
                    swap(arr, j, j+1);
                }
            }
        }

        long endTime = System.currentTimeMillis();

        System.out.println(Arrays.toString(arr));
        System.out.printf("소요시간: %s 밀리초\n", endTime - startTime);
    }
}

import java.util.Random;

public class TestUtil {
    
    public static int[] createIntArray(int size) {
        int[] arr = new int[size];
        Random random = new Random();

        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(size);
        }
        return arr;
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

static int binarySearch(int[] arr, int target) {
    // 투 포인터
    int left = 0;
    int right = arr.length - 1;

    // 종료 조건: 포인터끼리 만날 때까지 (모두 탐색함)
    while (left <= right) {
        int mid = (left + right) / 2;       // 중간 위치 설정
        if (arr[mid] == target) return mid; // 반환 조건: mid가 target이 될 때 반환함

        // mid의 위치를 기준으로 포인터를 옮김
        if (target < arr[mid]) {
            right = mid -1;
        } else if (target > arr[mid]) {
            left = mid + 1;
        }
    }

    // 디폴트 반환: 모든 데이터를 탐색했음에도 배열 내에 target이 존재하지 않음
    return -1;
}

// Test Run
public static void main(String[] args) {
    int[] arr = {1,3,5,9,10,11,14,29};
    System.out.println(binarySearch(arr, 3));
}

// 선형 탐색 (기본)
static int seqSearch(int[] arr, int target) {
    int idx = 0;    // 반환할 인덱스 변수 (0부터 탐색 시작)

    // 반복문 1회 -> 2개의 조건문 연산
    while (true) {
        // 종료조건: idx가 arr의 끝(=arr.length-1)을 초과하면 
        if ( idx == arr.length ) return -1;
        // 반환조건: arr의 값이 target과 일치하면 idx를 반환
        if ( arr[idx] == target ) return idx;
        idx++;
    }
}

// 선형 탐색 (보초법)
static int seqSearchSentinel(int[] arr, int target) {
    // 반환조건: arr의 마지막 요소가 target이라면, 바로 lastIdx를 반환
    int lastIdx = arr.length - 1;
    if (arr[lastIdx] == target) return lastIdx;

    // 위의 조건에 맞지 않는다면, 이하의 과정을 진행
    // 배열의 마지막 인덱스 위치에 target을 넣음 (보초)
    arr[lastIdx] = target;

    // 종료 조건 1번(인덱스 범위 검사)이 필요 없어지고, 탐색할 데이터의 크기가 1 줄어듦
    // 즉, 반복문 1회 -> 조건문 비교 연산 1회
    int idx = 0;
    while (true) {
        if (arr[idx] == target) {
            // 반환조건: 전체 탐색에서 딱 1번만 실행됨
            return (idx < lastIdx) ? idx : -1;
        }
        idx++;
    }
}

// Test Run
public static void main(String[] args) {
    int index = seqSearch(new int[]{1,6,12,4,76,23,411}, 4);
    System.out.println(index);
}