정렬

정렬 알고리즘에는 많은 방식들이 있고, 각 정렬마다 시간복잡도가 다르다.

---

선택 정렬(Selection Sort)

선택 정렬(Selection Sort)은 데이터 정렬에서 기본적인 방식 중 하나로, 단순하면서도 비교적 이해하기 쉬운 방식으로 작동한다.

정렬 방식

선택 정렬은 제자리 정렬 알고리즘의 하나로, 순서는 다음과 같다.

1. 주어진 리스트 중에 최소값을 찾는다.
2. 그 값을 맨앞에 위치한 값과 교체한다.
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

특징

선택 정렬은 단순하게 구현할 수 있고, 추가적인 메모리 공간이 필요하지 않은 제자리 정렬이다. 그러나 정렬되어 있어도 모든 요소를 비교해야 하므로, 대규모 데이터셋에는 적합하지 않다.

예시 코드

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^2)
• 이유: 매 단계에서 남은 요소를 모두 비교해야 하기 때문에 모든 경우에 (O(n^2)) 시간이 소요된다.

  공간복잡도

• O(1)
• 이유: 선택 정렬도 제자리에서 작동하므로 추가 메모리를 필요로 하지 않는다. 배열 내부에서 가장 작은 값과 현재 위치 값을 직접 교환하기 때문에 추가 메모리 사용이 없다.

---

버블 정렬(Bubble Sort)

버블 정렬은 배열의 인접한 두 요소를 반복적으로 비교하며 큰 값을 뒤로 이동시키는 정렬 방식이다.

정렬 방식

1. 배열에서 인접한 두 요소를 선택해 비교한다.
2. 두 요소가 정렬되지 않았으면 교환한다.
3. 배열의 처음부터 끝까지 반복하여 순회한다.
4. 교환이 발생하지 않을 때 정렬이 완료된다.

특징

버블 정렬은 이해하기 쉽고 단순한 방식으로 구현 가능하지만, 많은 교환 연산과 비교 연산이 필요해 대규모 데이터에 비효율적이다.

예시 코드

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) (이미 정렬된 경우)
• 평균 및 최악: O(n^2)
• 이유: 거의 정렬된 경우에는 빠르게 종료되지만, 정렬이 되어 있지 않으면 모든 요소를 반복 비교해야 한다.

  공간복잡도

• O(1)
• 이유: 버블 정렬은 추가적인 배열이나 리스트가 필요하지 않고, 제자리 정렬(in-place sort) 방식이기 때문에 배열 내에서 직접 값들을 교환하여 정렬한다.

---

삽입 정렬(Insertion Sort)

삽입 정렬(Insertion Sort)은 리스트의 각 요소를 정렬된 부분에 삽입하는 방식으로 동작하는 정렬 알고리즘이다. 데이터가 거의 정렬된 경우 효율적으로 작동하며, 작고 정렬된 부분을 계속 유지하면서 새 요소를 적절한 위치에 추가하는 방식이다.

정렬 방식

1. 배열의 첫 번째 요소를 정렬된 상태로 간주한다.
2. 두 번째 요소부터 시작해, 이전 요소들과 비교하며 적절한 위치에 삽입한다.
3. 모든 요소가 삽입될 때까지 이 과정을 반복한다.

특징

삽입 정렬은 거의 정렬된 데이터에 대해서 매우 효율적이며, 안정 정렬(stable sort) 이므로 동일한 값의 상대적인 순서가 유지된다. 추가 메모리를 사용하지 않는 제자리 정렬(in-place sort) 로, 구현이 단순하고 작은 데이터셋에 적합하다.

예시 코드

void insertionSort(int[] arr) {
   for(int index = 1 ; index < arr.length ; index++){

      int temp = arr[index];
      int aux = index - 1;

      while( (aux >= 0) && ( arr[aux] > temp ) ) {

         arr[aux + 1] = arr[aux];
         aux--;
      }
      arr[aux + 1] = temp;
   }
}

시간복잡도

• 최선: O(n) (이미 정렬된 경우)
• 평균 및 최악: O(n^2)
• 이유: 이미 정렬된 데이터에 새 요소가 추가될 경우, 위치를 찾기 위한 비교가 거의 없으므로 O(n)의 시간이 걸린다. 그러나 정렬되지 않은 데이터에서는 각 요소를 위치에 삽입하기 위해 (O(n^2)) 비교가 필요하다.

공간복잡도

• O(1)
• 이유: 삽입 정렬은 정렬된 부분에 요소를 삽입하면서 진행하며, 배열 내에서 직접 위치를 변경하기 때문에 추가 메모리가 필요하지 않다. 제자리 정렬 방식이다.

---

퀵 정렬(Quick Sort)

퀵 정렬(Quick Sort)은 분할 정복(divide and conquer) 방식을 사용하는 매우 효율적인 정렬 알고리즘이다. 퀵 정렬은 데이터를 특정 값(피벗, pivot)을 기준으로 두 개의 부분으로 나누어 정렬하며, 평균적으로 높은 성능을 제공해 다양한 상황에서 널리 사용된다.

정렬 방식

1. 배열에서 하나의 요소를 피벗으로 선택한다.
2. 피벗을 기준으로 작은 값들은 왼쪽, 큰 값들은 오른쪽에 배치하여 배열을 분할한다.
3. 분할된 두 부분에서 각각 같은 과정을 재귀적으로 반복하여 정렬을 완료한다.

특징

퀵 정렬은 제자리 정렬(in-place sort)로 추가 메모리를 거의 사용하지 않으며, 데이터 분포에 따라 성능이 달라진다. 특히 피벗 선택이 정렬 성능에 중요한 영향을 미치므로, 임의의 피벗이나 중앙값 등을 선택하는 방법이 사용된다.

예시 코드

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(n log n)
• 최악: O(n^2)
• 이유: 이상적으로 배열이 매번 절반으로 나뉘면 O(n log n)의 복잡도가 되지만, 피벗 선택이 좋지 않아 분할이 한쪽으로 치우치면 최악의 경우 O(n^2)이 된다.

  공간복잡도

• 평균: O(log n)
• 최악: O(n)
• 이유: 퀵 정렬은 분할 정복 방식으로, 재귀 호출마다 스택 메모리를 사용하므로 평균적으로 O(log n)의 공간복잡도를 갖는다. 하지만 피벗 선택이 좋지 않아 분할이 비효율적으로 이루어질 경우 최대 O(n)까지 공간이 필요할 수 있다.

---

합병 정렬(Merge Sort)

합병 정렬(Merge Sort)은 분할 정복(divide and conquer) 방식을 사용하여 배열을 반복적으로 분할하고 병합하면서 정렬하는 알고리즘이다. 안정 정렬(stable sort) 이며, 모든 경우에서 일관된 시간 복잡도를 보장하기 때문에 효율적인 정렬 알고리즘으로 평가된다.

정렬 방식

1. 배열을 절반으로 나누어 더 이상 나눌 수 없을 때까지 분할한다.
2. 분할된 각 배열을 재귀적으로 정렬한다.
3. 정렬된 배열들을 병합하여 전체 배열을 완성한다.

특징

합병 정렬은 안정 정렬로, 동일한 값의 순서가 유지된다. 또한 분할과 병합 과정에서 추가 메모리가 필요하므로 제자리 정렬(in-place sort) 이 아니다. 정렬 대상의 크기가 커지더라도 성능이 일정하게 유지되기 때문에 대규모 데이터 정렬에 적합하다.

예시 코드

/// merge sort range : [low ~ high]
void mergeSort(int A[], int low, int high, int B[]){
    // 1. base condition
    if(low >= high) return;

    // 2. divide
    int mid = (low + high) / 2;

    // 3. conquer
    mergeSort(A, low, mid, B);
    mergeSort(A, mid+1, high, B);

    // 4. combine
    int i=low, j=mid+1, k=low;
    for(;k<=high;++k){
        if(j > high ) B[k] = A[i++];
        else if(i > mid) B[k] = A[j++];
        else if(A[i] <= A[j]) B[k] = A[i++];
        else B[k] = A[j++];
    }

    // 5. copy
    for(i=low;i<=high;++i) A[i] = B[i];
}

시간복잡도

• O(n log n)
• 이유: 배열이 절반씩 나뉘고 각 단계에서 병합할 때 (O(n))의 시간이 소요되므로, 전체 시간복잡도는 (O(n \log n))이 된다.

  공간복잡도

• O(n)
• 이유: 합병 정렬은 분할된 배열을 병합하는 과정에서 추가적인 배열이 필요하다. 각 단계에서 분할된 배열을 저장하고 병합하기 위해 O(n)만큼의 추가 공간을 사용하므로, 제자리 정렬이 아니다.

힙 정렬(Heap Sort)

힙 정렬(Heap Sort)은 힙(heap) 자료구조를 기반으로 한 정렬 알고리즘으로, 완전 이진 트리를 사용해 최대값이나 최소값을 빠르게 찾는 것이 특징이다. 이 알고리즘은 주로 최대 힙을 사용하며, 정렬을 위해 힙 특성을 유지하면서 요소들을 정렬한다.

정렬 방식

1. 최대 힙 구성: 배열을 힙 구조로 만든다. 최대 힙에서는 부모 노드가 항상 자식 노드보다 큰 값을 가지므로, 루트에는 항상 가장 큰 값이 위치하게 된다.
2. 정렬: 루트 요소(최대값)를 배열의 마지막 위치와 교환한 후 힙 크기를 줄인다. 그리고 나머지 배열에 대해 힙 구조를 재구성하여 가장 큰 값이 다시 루트에 오도록 만든다. 이 과정을 배열이 완전히 정렬될 때까지 반복한다.

특징

• 제자리 정렬(in-place sort): 힙 정렬은 추가적인 배열이 필요하지 않아 메모리 사용이 효율적이다.
• 안정 정렬이 아님: 동일한 값의 상대적인 순서가 유지되지 않기 때문에 안정 정렬이 아니다.
• 최대 힙과 최소 힙: 주로 최대 힙을 사용하지만, 최소 힙을 사용하여 오름차순 또는 내림차순 정렬을 수행할 수도 있다.

예시 코드

public class Heap {
	private int[] element; //element[0] contains length
	private static final int ROOTLOC = 1;
	private static final int DEFAULT = 10;

	public Heap(int size) {
		if(size>DEFAULT) {element = new int[size+1]; element[0] = 0;}
		else {element = new int[DEFAULT+1]; element[0] = 0;}
	}

	public void add(int newnum) {

		if(element.length <= element[0] + 1) {
			int[] elementTemp = new int[element[0]*2];
			for(int x = 0; x < element[0]; x++) {
				elementTemp[x] = element[x];
			}
			element = elementTemp;
		}
		element[++element[0]] = newnum;
		upheap();
	}

	public int extractRoot() {
		int extracted = element[1];
		element[1] = element[element[0]--];
		downheap();
		return extracted;
	}

	public void upheap() {
		int locmark = element[0];
		while(locmark > 1 && element[locmark/2] > element[locmark]) {
			swap(locmark/2, locmark);
			locmark /= 2;
		}
	}

	public void downheap() {
		int locmark = 1;
		while(locmark * 2 <= element[0])
		{
			if(locmark * 2 + 1 <= element[0]) {
				int small = smaller(locmark*2, locmark*2+1);
				if(element[small] >= element[locmark]) break;
				swap(locmark,small);
				locmark = small;
			}
			else {
			    if(element[locmark * 2] >= element[locmark]) break;
				swap(locmark, locmark * 2);
				locmark *= 2;
			}
		}
	}

	public void swap(int a, int b) {
		int temp = element[a];
		element[a] = element[b];
		element[b] = temp;
	}

	public int smaller(int a, int b) {
		return element[a] < element[b] ? a : b;
	}
}

시간복잡도

• O(n log n)
• 이유: 힙을 만드는 데 O(n) 시간이 걸리며, 힙에서 요소를 하나씩 꺼내는 데 O(log n)의 시간이 필요하다. 이를 모든 요소에 대해 반복하기 때문에 전체 시간복잡도는 O(nlogn)이 된다.

공간복잡도

• O(1)
• 이유: 추가 배열이나 메모리 공간 없이 배열 내에서 직접 요소를 교환하며 정렬을 수행하므로 제자리 정렬로 간주된다.