기술 면접 준비 (1) - Algorithm-1

작성일 | In |

모든 글은 다음 블로그를 참고하여 작성하였습니다.
https://gyoogle.dev/blog/

Bubble Sort

Java Code (Ascending)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void bubbleSort(int[] arr) {
    int temp = 0;
	for(int i = 0; i < arr.length; i++) {       // 1.
		for(int j= 1 ; j < arr.length-i; j++) { // 2.
			if(arr[j-1] > arr[j]) {             // 3.
                // swap(arr[j-1], arr[j])
				temp = arr[j-1];
				arr[j-1] = arr[j];
				arr[j] = temp;
			}
		}
	}
	System.out.println(Arrays.toString(arr));
}

GIF

bubble

시간 복잡도

  • O(n^2)

공간복잡도

  • O(n)

장점

  • 구현이 매우 간단하고, 소스코드가 직관적이다.

  • 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않다. => 제자리 정렬(in-place sorting)

  • 안정 정렬(Stable Sort) 이다.

단점

  • 시간복잡도가 최악, 최선, 평균 모두 O(n^2)으로, 굉장히 비효율적이다.

  • 정렬 돼있지 않은 원소가 정렬 됐을때의 자리로 가기 위해서, 교환 연산(swap)이 많이 일어나게 된다.

Selection Sort

Java Code (Ascending)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void selectionSort(int[] arr) {
    int indexMin, temp;
    for (int i = 0; i < arr.length-1; i++) {        // 1.
        indexMin = i;
        for (int j = i + 1; j < arr.length; j++) {  // 2.
            if (arr[j] < arr[indexMin]) {           // 3.
                indexMin = j;
            }
        }
        // 4. swap(arr[indexMin], arr[i])
        temp = arr[indexMin];
        arr[indexMin] = arr[i];
        arr[i] = temp;
  }
  System.out.println(Arrays.toString(arr));
}

GIF

selection

시간 복잡도

  • O(n^2)

공간복잡도

  • O(n)

장점

  • Bubble sort와 마찬가지로 알고리즘이 단순하다.

  • 정렬을 위한 비교 횟수는 많지만, Bubble Sort에 비해 실제로 교환하는 횟수는 적기 때문에 많은 교환이 일어나야 하는 자료상태에서 비교적 효율적이다.

  • Bubble Sort와 마찬가지로 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다. => 제자리 정렬(in-place sorting)

단점

  • 시간복잡도가 O(n^2)으로, 비효율적이다.

  • 불안정 정렬(Unstable Sort) 이다.

Insertion Sort

Java Code (Ascending)

1
2
3
4
5
6
7
8
9
10
11
12
13
void insertionSort(int[] arr)
{
   for(int index = 1 ; index < arr.length ; index++){ // 1.
      int temp = arr[index];
      int prev = index - 1;
      while( (prev >= 0) && (arr[prev] > temp) ) {    // 2.
         arr[prev+1] = arr[prev];
         prev--;
      }
      arr[prev + 1] = temp;                           // 3.
   }
   System.out.println(Arrays.toString(arr));
}

GIF

insertion

시간 복잡도

  • O(n^2), 최선의 경우 : O(N)

공간복잡도

  • O(n)

장점

  • 알고리즘이 단순하다.
  • 대부분의 원소가 이미 정렬되어 있는 경우, 매우 효율적일 수 있다.
  • 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다. => 제자리 정렬(in-place sorting)

  • 안정 정렬(Stable Sort) 이다.

  • Selection Sort나 Bubble Sort과 같은 O(n^2) 알고리즘에 비교하여 상대적으로 빠르다.

단점

  • 평균과 최악의 시간복잡도가 O(n^2)으로 비효율적이다.

  • Bubble Sort와 Selection Sort와 마찬가지로, 배열의 길이가 길어질수록 비효율적이다.

Quick Sort

Java Code (Ascending)

1
2
3
4
5
6
7
8
9
10
public void quickSort(int[] array, int left, int right) {
    if(left >= right) return;

    // 분할
    int pivot = partition();

    // 피벗은 제외한 2개의 부분 배열을 대상으로 순환 호출
    quickSort(array, left, pivot-1);  // 정복(Conquer)
    quickSort(array, pivot+1, right); // 정복(Conquer)
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int partition(int[] array, int left, int right) {
    /**
    // 최악의 경우, 개선 방법
    int mid = (left + right) / 2;
    swap(array, left, mid);
    */

    int pivot = array[left]; // 가장 왼쪽값을 피벗으로 설정
    int i = left, j = right;

    while(i < j) {
        while(pivot < array[j]) {
            j--;
        }
        while(i < j && pivot >= array[i]){
            i++;
        }
        swap(array, i, j);
    }
    array[left] = array[i];
    array[i] = pivot;

    return i;
}

GIF

quick

시간 복잡도

  • 평균, 최선의 경우 : O(nlog₂n), 비교 횟수 : log₂n
  • 최악의 경우 : O(n^2), 비교 횟수 : n

공간복잡도

  • O(n)

장점

  • 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐만 아니라, 한 번 결정된 피벗들이 추후 연산에서 제외되는 특성 때문에, 시간 복잡도가 O(nlog₂n)를 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다.
  • 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다.

단점

  • 불안정 정렬(Unstable Sort) 이다.
  • 정렬된 배열에 대해서는 Quick Sort의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다.

Merge Sort

Java Code (Ascending)

1
2
3
4
5
6
7
8
9
10
11
public void mergeSort(int[] array, int left, int right) {

    if(left < right) {
        int mid = (left + right) / 2;

        mergeSort(array, left, mid);
        mergeSort(array, mid+1, right);
        merge(array, left, mid, right);
    }

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public static void merge(int[] array, int left, int mid, int right) {
    int[] L = Arrays.copyOfRange(array, left, mid + 1);
    int[] R = Arrays.copyOfRange(array, mid + 1, right + 1);

    int i = 0, j = 0, k = left;
    int ll = L.length, rl = R.length;

    while(i < ll && j < rl) {
        if(L[i] <= R[j]) {
            array[k] = L[i++];
        }
        else {
            array[k] = R[j++];
        }
        k++;
    }

    // remain
    while(i < ll) {
        array[k++] = L[i++];
    }
    while(j < rl) {
        array[k++] = R[j++];
    }
}

시간 복잡도

  • O(nlogn)