[코딩 인터뷰]개념과 알고리즘 - 정렬과 탐색

 

[ 널리 사용되는 정렬 알고리즘 ]

👀 버블 정렬 | 평균 및 최악 실행 시간: O(n^2), 메모리: O(1)

: 배열의 첫 원소부터 순차적으로 진행하며, 현재 원소가 그다음 원소의 값보다 크면 두 원소를 바꾸는 작업을 반복합니다. 이 과정을 완전히 정렬된 상태가 될 때까지 반복합니다.

JAVA(위키백과)

void bubbleSort(int[] arr) {
    int temp = 0;
	for(int i = 0; i < arr.length - 1; i++) {
		for(int j= 1 ; j < arr.length-i; j++) {
			if(arr[j]<arr[j-1]) {
				temp = arr[j-1];
				arr[j-1] = arr[j];
				arr[j] = temp;
			}
		}
	}
	System.out.println(Arrays.toString(arr));
}

 

👀 선택 정렬 | 평균 및 최악 실행 시간: O(n^2), 메모리: O(1)

 : 배열을 선형 탐색하며 가장 작은 원소를 배열 맨 앞 원소와 자리를 바꿉니다. 그다음에 두 번째로 작은 원소를 찾은 뒤 앞으로 보내줍니다. 이러한 작업을 모든 원소가 정렬될 때까지 반복합니다.

JAVA(위키백과)

void selectionSort(int[] list) {
    int indexMin, temp;

    for (int i = 0; i < list.length - 1; i++) {
        indexMin = i;
        for (int j = i + 1; j < list.length; j++) {
            if (list[j] < list[indexMin]) {
                indexMin = j;
            }
        }
        temp = list[indexMin];
        list[indexMin] = list[i];
        list[i] = temp;
    }
}

 

👀 병합 정렬 | 평균 및 최악 실행 시간: O(n log n), 메모리: 상황에 따라 다름

 : 배열을 절반씩 나누어 각각을 정렬한 다음 이 둘을 합하여 다시 정렬하는 방법입니다. 나눈 절반을 정렬할 때도 같은 알고리즘이 사용되고 결국에는 원소 한 개짜리 배열 두 개를 병합하게 됩니다.

JAVA

void mergesort(int[] array){
    int[] helper = new int[array.length];
    mergesort(array, helper, 0, array.length-1);
}

void mergesort(int[] array, int[] helper, int low, int high){
    if(low < high){
        int middle = (low + high) / 2;
        mergesort(array, helper, low, middle);    // 왼쪽 절반 정렬
        mergesort(array, helper, middle+1, high); // 오른쪽 절반 정렬
        merge(array, helper, low, middle, high);  // 병합
    }
}

void merge(int[] array, int[] helper, int low, int middle, int high){
    // 절반짜리 두 배열을 helper 배열에 복사합니다.
    for (int i=low; i<=high; i++){
        helper[i] = array[i];
    }
    
    int helperLeft = low;
    int helperRight = middle + 1;
    int current = low;
    
    // 왼쪽 절반과 오른쪽 절반을 비교하여 작은 원소를 원래 배열에 복사합니다.
    while(helperLeft <= middle && helperRight <= heigh){
        if(helper[helperLeft] <= helper[helperRight]){
            array[current] = helper[helperLeft];
            helperLeft++;
        }else{
            array[current] = helper[helperRight];
            helperRight++;
        }
        current++;
    }
    // 왼쪽 절반 배열에 남은 원소들을 원래 배열에 복사해 넣습니다.
    int remaining = middle - helperLeft;
    for(int i=0; i<=remaining; i++){
        array[current+i] = helper[helperLeft+i];
    }
}

 

👀 퀵 정렬 | 실행 시간: 평균 O(n log n), 최악 O(n^2), 메모리: O(log n)

 : 무작위로 선정된 한 원소를 사용하여 배열을 분할하는데, 선정된 원소보다 작은 원소들은 앞에, 큰 원소들은 뒤로 보냅니다. 배열 분할 작업은 연속된 스왑 연산을 통해 효율적으로 수행됩니다. 배열과 그 부분 배열을 반복적으로 분할해 나가면 결국에 배열은 정렬된 상태에 도달하게 됩니다.

JAVA(위키백과)

public void quickSort(int[] arr, int left, int right) {
    // base condition
    if (left >= right) {
        return;
    }
    int pivot = arr[right];
    
    int sortedIndex = left;
    for (int i = left; i < right; i++) {
        if (arr[i] <= pivot) {
            swap(arr, i, sortedIndex);
            sortedIndex++;
        }
    }
    swap(arr, sortedIndex, right);
    quickSort(arr, left, sortedIndex - 1);
    quickSort(arr, sortedIndex + 1, right);
}

private void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

 

👀 기수 정렬 | 실행 시간: O(kn)

 : 데이터가 정수처럼 유한한 비트로 구성되어 있는 경우에 사용됩니다. 각 자릿수를 순회해 나가면서 각 자리의 값에 따라 그룹을 나누고 정렬합니다. 이 작업을 배열 전체가 정렬될 때까지 모든 자릿수에 대해 반복합니다.

 

👀 탐색 알고리즘

: 방대한 데이터에서 목적에 맞는 데이터를 찾아내기 위한 알고리즘입니다.

탐색 알고리즘의 한가지

⭐ 이진 탐색 : 정렬된 배열에서 원소 x를 찾고자 할 때 사용됩니다. x를 중간에 위치한 원소와 비교한 뒤 x가 중간에 위치한 값보다 작다면 배열의 왼쪽 절반을 재탐색하고, 크다면 배열의 오른쪽 절반을 재탐색합니다. 이 과정을 x를 찾거나 부분배열의 크기가 0이 될 때까지 반복합니다.