🦊 5. Sorting

5. Sorting

버블 정렬 (bubble sort)

• 평균 및 최악의 경우 O(n^2)
• 메모리 사용 O(1)

배열의 첫 원소부터 순차 실행.

현재 원소가 그다음 원소의 값보다 크면 두 원소를 바꾼다.

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;
			}
		}
	}
}

선택 정렬 (selection sort)

• 평균 및 최악의 경우 O(n^2
• 메모리 사용 O(1)

배열을 선형 탐색하며 가장 작은 원소를 배열의 맨 앞으로 보낸다.

그 다음에는 두 번째 작은 원소를 찾아 2번째 자리로 보낸다.

이를 모든 원소가 정렬될 때까지 반복한다.

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;
    }
}

병합 정렬 (merge sort)

• 평균 및 최악의 경우 O(n log n)
• 메모리 사용 상황에 따라 다름, 또는 O(n)

배열을 절반씩 나누어 각각을 정렬한 다음 이 둘을 합쳐서 다시 정렬한다.

나눈 절반을 정렬할 때도 같은 알고리즘이 사용되고 결국에는 원소 한 개짜리 배열 두 개를 병합한다.

병합을 처리하는 것이 가장 복잡하다.

병합 대상이 되는 배열의 두 부분을 임시 배열 helper 에 복사하고

왼쪽 절반의 시작 지점 helperLeft 와 오른쪽 절반의 시작 지점 helperRight 를 추적한다.

이후 helper 를 순회하며 두 배열에서 더 작은 값의 원소를 꺼내어 원래 배열에 복사해 넣는다.

두 배열 중 한 배열에 대한 순회가 끝난 경우, 다른 배열의 남은 부분을 원래 배열에 남김없이 복사해 넣고 작업을 마친다.

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); //오른쪽 절반 정렬
		sort(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 <= high) {
		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];
	}
}

오른쪽 절반에 대한 남은 원소들을 원래 배열로 다시 옮기는 코드가 존재하지 않는데,

그 이유는 오른쪽 원소들은 이미 원래 배열의 그 자리에 있기 때문이다.

퀵 정렬 (quick sort)

• 평균 O(n log n)

  최악 O(n^2)

• 메모리 사용 O(log n)

무작위로 선정된 한 원소를 사용하여 배열을 분할한다.

선정된 원소보다 작은 원소들은 앞으로, 큰 원소들은 뒤로 보낸다.

배열과 그 부분 배열을 반복적으로 분할해 나가면 결국 배열은 정렬된 상태에 도달한다.

배열 분할에 사용되는 원소가 중간값 medium 에 가까운 값이 되리라는 보장이 없기 때문에

최악의 경우 수행 시간이 O(n^2) 가 되기도 한다.

void quickSort(int[] arr, int left, int right) {
	int index = partition(arr, left, right);
	if (left < index - 1) { //왼쪽 절반 정렬
		quickSort(arr, left, index - 1);
	}
	if (index < right) { //오른쪽 절반 정렬
		quickSort(arr, index, right);
	}
}

int partition(int[] arr, int left, int right) {
	int pivot = arr[(left + right) / 2]; // 분할 기준 원소 선정
	while (left <= right) {
		while (arr[left] < pivot) left++; //왼쪽에서 오른쪽으로 옮겨야 하는 원소
		while (arr[right] > pivot) right--; //오른쪽에서 왼쪽으로 옮겨야 하는 원소

		// 원소를 스왑
		if (left <= right) {
			swap(arr, left, right); // 스왑
			left++;
			right--;
		}
	}
	return left;
}

기수 정렬 (radix sort)

• 실행 시간 O(kn)

기수 정렬은 데이터가 정수처럼 유한 비트로 구성되어 있는 경우 사용한다.

각 자릿수를 순회에 나가며 각 자리의 값에 따라 그룹을 나눈다.

기수 정렬은 O(kn) 의 복잡도를 지닌다. (n : 원소의 개수, k : 자릿수의 개수)